1

Suppose we have an array of objects and I want to find the index of a specific object in the list, in general I would use the method

public static int findIndex(Object[] arr, Object o) {
    int index = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i].equals(o)) {
            index = i;
            break;
        }
    }
    return index;
}

However, is there a faster way to do this only using the java.lang package?

user3749872
  • 77
  • 5
  • what do you mean by more efficient way ? what is efficient to you? there is a lazy evaluation in Java 8 but when I bench marked it with your approach , your approach was faster. – Kick Buttowski Feb 17 '15 at 20:03
  • Let me rephrase: A method which works faster than the one above! Thanks – user3749872 Feb 17 '15 at 20:04
  • look for findfirst in Java 8 and compare it with your approach , you see yours is faster as far as I tested – Kick Buttowski Feb 17 '15 at 20:05
  • You could do it in fewer lines, but not faster, unless you know something about the array contents. – khelwood Feb 17 '15 at 20:05
  • There are many searching algorithms but they all have their assumptions. For instance if your list would be sorted you could use bisection. – Pshemo Feb 17 '15 at 20:06

4 Answers4

2

If you don't know anything about the order of the data, there is no more efficient algorithm, this is the theoretical optimum. You can - using some tricks - make it a few percent faster. For instance:

  • cache the length of the array
  • perform an immediate return instead of a break (breaks are, when it comes to performance, considered not to be that efficient).
  • Use o.equals instead of arr[i].equals. Smart compilers can cache the vtable of o.

But it is likely a compiler can already derive some of the optimizations itself.

A more efficient algorithm is thus probably:

public static int findIndex(Object[] arr, Object o) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        if (o.equals(arr[i])) {
            return i;
        }
    }
    return -1;
}

Although the difference will not be that huge. If one tests both implementations, the difference is:

//question first
findIndex (question): 4s 209 469 827
findIndex (answer):   4s 078 955 465
//answer first
findIndex (question): 4s 256 345 171
findIndex (answer):   4s 488 112 895

(there is a difference in which method you call first because of caching). Point is that the difference is not that huge and can be altered by OS calls, other servers tasks. So one can safely say we speak about milliseconds in real performance difference.

If however the data is ordered (by some order relation) you can perform binary search.

In case you want to do multiple lookups, you can first insert the elements in in a HashSet<T>. This HashSet<T> has an average lookup of O(1) (given a good hashing function).

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • 1
    Speaking of HashSet, it's also worth mentioning that fairly robust and efficient hash table structures can be easily developed using no other packages than java.lang if speed is such a major concern. One such example is [SeparateChainingST](http://algs4.cs.princeton.edu/34hash/SeparateChainingHashST.java.html) from *Algorithms* 4th Edition. It imports the LinkedList package, but only as a lazy means of returning the set of keys as an iterable. You could easily craft your own minimalist generic queue which implements the iterable interface. – Dyndrilliac Feb 17 '15 at 20:31
1

if you are looking for efficiency in CPU time, this is as good as it gets. If you are looking for fewer lines of code you could try 

theIndex = Arrays.asList(arr).indexOf(o);

or similar...

Henry Crutcher
  • 2,137
  • 20
  • 28
0

If the collection is ordered you can use binary search, which is a rather simple searching algorithm.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Here is a Java example:

http://www.programmingsimplified.com/java/source-code/java-program-for-binary-search

Robin
  • 1,927
  • 3
  • 18
  • 27
-1

You can use one line of code as stated above. Here is some info too.

array.indexOf()

http://www.tutorialspoint.com/java/java_string_indexof.htm

Eric
  • 11
  • 1