Поиск по индексу элемента в массиве

Question

Предположим, у нас есть массив объектов, и я хочу, чтобы найти индекс конкретного объекта в списке, в общем, я хотел бы использовать метод

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; 
} 

Однако , существует ли более быстрый способ сделать это только с помощью пакета java.lang?

Answer 1

Если вы что-нибудь о порядке данных не знаю, не существует более эффективный алгоритм, это теоретический оптимальный. Вы можете - используя некоторые трюки - сделать это на несколько процентов быстрее. Например:

• кэш длина массива
• выполнить немедленное возвращение вместо того, чтобы break (разрывы, когда дело доходит до исполнения, не считаются эффективными, что).
• Использовать o.equals вместо arr[i].equals. Умные компиляторы могут кэшировать vtableo.

Но, скорее всего, компилятор уже может получить некоторые из самих оптимизаций.

более эффективный алгоритм, таким образом, вероятно:

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; 
} 

Хотя разница не будет столь огромным. Если один tests обеих реализаций, разница:

//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 

(есть разница в какой метод вы звоните первым из-за кэширования). Дело в том, что разница не такая огромная и может быть изменена вызовами ОС, другими задачами серверов. Таким образом, можно смело сказать, что мы говорим о миллисекундах в реальной разнице в производительности.

Если, однако, данные приказал (по некоторым отношениям) вы можете выполнить binary search.

Если вы хотите выполнить несколько поисков, вы можете сначала вставить элементы в HashSet<T>. У этого HashSet<T> есть средний взгляд на O (1) (с учетом хорошей хэширования).

Answer 2

Если вы ищете эффективность в процессорном времени, это так же хорошо, как и получается. Если вы ищете меньшее количество строк коды вы можете попробовать

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

или аналогичный ...

Answer 3

Если коллекция упорядочены вы можете использовать бинарный поиск, который является довольно простым алгоритмом поиска.

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

Вот пример Java:

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

Answer 4

Вы можете использовать одну строку кода, как указано выше. Вот некоторая информация.

Array.indexOf()

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