Алгоритмы поиска в Java

Введение Поиск - одно из наиболее распространенных действий, выполняемых в обычных бизнес-приложениях. Это включает в себя выборку некоторых данных, хранящихся в структурах данных, таких как массивы, список, карта и т. Д. Чаще всего эта операция поиска определяет скорость отклика приложения для конечного пользователя. В этой статье давайте рассмотрим некоторые стратегии поиска, которые можно использовать для различных сценариев. Мы также реализуем их на Java и проанализируем их производительность с некоторыми из них.

Вступление

Поиск - одно из самых распространенных действий, выполняемых в обычных бизнес-приложениях. Это включает в себя выборку некоторых данных, хранящихся в структурах данных, таких как Arrays , List , Map и т. Д. Чаще всего эта операция поиска определяет скорость отклика приложения для конечного пользователя.

В этой статье давайте рассмотрим некоторые стратегии поиска, которые можно использовать для различных сценариев. Мы также реализуем их на Java и проанализируем их производительность с некоторыми хорошо известными параметрами, такими как сложность времени и пространства .

Линейный поиск

Линейный или последовательный поиск - это простейший алгоритм поиска. Хотя это, безусловно, самый простой, он определенно не самый распространенный из-за своей неэффективности. Это алгоритм грубой силы. Он очень редко используется в производстве и в большинстве случаев уступает другим алгоритмам.

Линейный поиск не имеет предварительных условий для состояния базовой структуры данных.

Объяснение

Линейный поиск включает в себя последовательный поиск элемента в данной структуре данных до тех пор, пока либо элемент не будет найден, либо не будет достигнут конец структуры.

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

Выполнение

Теперь посмотрим, как реализовать линейный поиск в Java:

 public static int linearSearch(int arr[], int elementToSearch) { 
 
 for (int index = 0; index < arr.length; index++) { 
 if (arr[index] == elementToSearch) 
 return index; 
 } 
 return -1; 
 } 

Чтобы проверить это, мы будем использовать простой массив целых чисел:

 int index = linearSearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67); 
 print(67, index); 

С помощью простого вспомогательного метода для печати результата:

 public static void print(int elementToSearch, int index) { 
 if (index == -1){ 
 System.out.println(elementToSearch + " not found."); 
 } 
 else { 
 System.out.println(elementToSearch + " found at index: " + index); 
 } 
 } 

Выход:

 67 found at index: 8 

Сложность времени

Здесь мы последовательно перебираем весь набор из N элементов, чтобы определить местоположение искомого элемента. Наихудший случай для этого алгоритма будет, если элемент, который мы ищем, будет последним элементом в массиве.

В этом случае мы выполним итерацию N раз, прежде чем найдем элемент.

Следовательно, временная сложность линейного поиска составляет O (N) .

Космическая сложность

Для этого типа поиска требуется только одна единица памяти для хранения искомого элемента. Это не имеет отношения к размеру входного массива.

Следовательно, пространственная сложность линейного поиска равна O (1) .

Приложения

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

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

Бинарный поиск

Двоичный или логарифмический поиск - один из наиболее часто используемых алгоритмов поиска, в первую очередь из-за его быстрого времени поиска.

Объяснение

Этот вид поиска использует методологию «разделяй и властвуй» и требует предварительной сортировки набора данных.

Он делит входную коллекцию на равные половины и на каждой итерации сравнивает целевой элемент с элементом посередине.

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

Вот почему важно иметь отсортированную коллекцию для двоичного поиска.

Поиск прекращается, когда firstIndex (наш указатель) проходит мимо lastIndex (последнего элемента), что означает, что мы просмотрели весь массив, а элемент отсутствует.

Есть два способа реализовать этот алгоритм - итеративный и рекурсивный .

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

Выполнение

Итеративный

Давайте сначала посмотрим на итеративный подход:

 public static int binarySearch(int arr[], int elementToSearch) { 
 
 int firstIndex = 0; 
 int lastIndex = arr.length - 1; 
 
 // termination condition (element isn't present) 
 while(firstIndex <= lastIndex) { 
 int middleIndex = (firstIndex + lastIndex) / 2; 
 // if the middle element is our goal element, return its index 
 if (arr[middleIndex] == elementToSearch) { 
 return middleIndex; 
 } 
 
 // if the middle element is smaller 
 // point our index to the middle+1, taking the first half out of consideration 
 else if (arr[middleIndex] < elementToSearch) 
 firstIndex = middleIndex + 1; 
 
 // if the middle element is bigger 
 // point our index to the middle-1, taking the second half out of consideration 
 else if (arr[middleIndex] > elementToSearch) 
 lastIndex = middleIndex - 1; 
 
 } 
 return -1; 
 } 

Мы можем использовать такой алгоритм:

 int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67); 
 print(67, index); 

Выход:

 67 found at index: 5 
Рекурсивный

А теперь посмотрим на рекурсивную реализацию:

 public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) { 
 
 // termination condition 
 if (lastElement >= firstElement) { 
 int mid = firstElement + (lastElement - firstElement) / 2; 
 
 // if the middle element is our goal element, return its index 
 if (arr[mid] == elementToSearch) 
 return mid; 
 
 // if the middle element is bigger than the goal element 
 // recursively call the method with narrowed data 
 if (arr[mid] > elementToSearch) 
 return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch); 
 
 // else, recursively call the method with narrowed data 
 return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch); 
 } 
 
 return -1; 
 } 

Разница в рекурсивном подходе заключается в том, что мы вызываем сам метод после получения нового раздела. В итеративном подходе всякий раз, когда мы определяем новый раздел, мы изменяем первый и последний элементы и повторяем процесс в том же цикле.

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

Мы можем использовать этот алгоритм так:

 int index = binarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67); 
 print(67, index); 

Выход:

 67 found at index: 5 

Сложность времени

Поскольку двоичный поиск делит массив на половину каждый раз, когда его временная сложность равна O (log (N)) . Эта временная сложность является заметным улучшением временной сложности O (N) линейного поиска.

Космическая сложность

Для этого поиска требуется только одна единица пространства для хранения искомого элемента. Следовательно, его пространственная сложность O (1) .

Если двоичный поиск реализован рекурсивно, он должен сохранить вызов метода в стеке. В худшем случае для этого может потребоваться O (log (N)) пространства.

Приложения

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

Двоичный поиск также реализован в API Java в методе Arrays.binarySearch

Поиск по образцу Knuth Morris Pratt

Как видно из названия, это алгоритм поиска закономерностей в заданном тексте. Этот алгоритм был разработан Дональдом Кнутом, Воаном Праттом и Джеймсом Моррисом, отсюда и название.

Объяснение

В этом поиске сначала компилируется данный шаблон. Компилируя его, мы пытаемся найти префикс и суффикс строки шаблона. Это помогает нам в случае несоответствия - мы не будем искать следующее совпадение с начала индекса.

Вместо этого мы пропускаем ту часть текстовой строки, которую уже сравнили, и начинаем сравнивать после этой части. Мы определяем эту часть, зная префикс и суффикс, поэтому мы уверены, какая часть уже сравнивается, и ее можно безопасно пропустить.

В результате этого пропуска мы можем сэкономить много сравнений, и KMP работает быстрее, чем наивный алгоритм грубой силы.

Выполнение

Создадим метод compilePatternArray() , который в дальнейшем будет использоваться алгоритмом поиска KMP:

 public static int[] compilePatternArray(String pattern) { 
 int patternLength = pattern.length(); 
 int len = 0; 
 int i = 1; 
 int[] compliedPatternArray = new int[patternLength]; 
 compliedPatternArray[0] = 0; 
 
 while (i < patternLength) { 
 if (pattern.charAt(i) == pattern.charAt(len)) { 
 len++; 
 compliedPatternArray[i] = len; 
 i++; 
 } else { 
 if (len != 0) { 
 len = compliedPatternArray[len - 1]; 
 } else { 
 compliedPatternArray[i] = len; 
 i++; 
 } 
 } 
 } 
 System.out.println("Compiled Pattern Array " + Arrays.toString(compliedPatternArray)); 
 return compliedPatternArray; 
 } 

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

Скомпилированный массив сохраняет позицию индекса предыдущего вхождения текущего символа в массив шаблонов.

Реализуем сам алгоритм:

 public static List<Integer> performKMPSearch(String text, String pattern) { 
 int[] compliedPatternArray = compilePatternArray(pattern); 
 
 int textIndex = 0; 
 int patternIndex = 0; 
 
 List<Integer> foundIndexes = new ArrayList<>(); 
 
 while (textIndex < text.length()) { 
 if (pattern.charAt(patternIndex) == text.charAt(textIndex)) { 
 patternIndex++; 
 textIndex++; 
 } 
 if (patternIndex == pattern.length()) { 
 foundIndexes.add(textIndex - patternIndex); 
 patternIndex = compliedPatternArray[patternIndex - 1]; 
 } 
 
 else if (textIndex < text.length() && pattern.charAt(patternIndex) != text.charAt(textIndex)) { 
 if (patternIndex != 0) 
 patternIndex = compliedPatternArray[patternIndex - 1]; 
 else 
 textIndex = textIndex + 1; 
 } 
 } 
 return foundIndexes; 
 } 

Здесь мы начнем с последовательного сравнения символов в шаблоне и текстовом массиве. Мы продолжаем двигаться вперед, пока не получим совпадение шаблонов и текстовых массивов. Таким образом, если мы достигаем конца массива шаблонов при сопоставлении, это означает, что мы нашли вхождение шаблона в тексте.

Однако, если мы обнаруживаем несоответствие при сравнении двух массивов, мы перемещаем индекс массива символов шаблона на значение в compiledPatternArray() а также переходим к следующему символу в текстовом массиве. Здесь поиск KMP превосходит метод грубой силы, поскольку он не сравнивает текстовые символы более одного раза в случае несоответствия.

Попробуем запустить алгоритм:

 String pattern = "AAABAAA"; 
 String text = "ASBNSAAAAAABAAAAABAAAAAGAHUHDJKDDKSHAAJF"; 
 
 List<Integer> foundIndexes = KnuthMorrisPrathPatternSearch.performKMPSearch(text, pattern); 
 
 if (foundIndexes.isEmpty()) { 
 System.out.println("Pattern not found in the given text String"); 
 } else { 
 System.out.println("Pattern found in the given text String at positions: " + .stream().map(Object::toString).collect(Collectors.joining(", "))); 
 } 

В тексте шаблона AAABAAA наблюдается и кодируется в массиве шаблонов следующий шаблон:

  • Шаблон A (Single A) повторяется в индексе 1 и снова в 4.
  • Образец AA (Double A) повторяется в индексе 2 и снова в индексе 5.
  • Шаблон AAA (3 A) повторяется с индексом 6.

Давайте посмотрим на результат, чтобы подтвердить наше обсуждение:

 Compiled Pattern Array [0, 1, 2, 0, 1, 2, 3] 
 Pattern found in the given text String at positions: 8, 14 

Описанный нами паттерн ясно показан нам в массиве собранного паттерна в выходных данных.

С помощью этого скомпилированного массива алгоритм поиска KMP может искать заданный образец в тексте, не возвращаясь в текстовый массив.

Сложность времени

Этот алгоритм должен сравнить все элементы в заданном тексте, чтобы найти шаблон. Время, необходимое для этого, составляет O (N) . Для компиляции строки шаблона нам нужно посетить каждый символ в шаблоне, и это еще O (M) итераций.

Таким образом, общее время, которое займет этот алгоритм, будет O (M + N) .

Космическая сложность

Нам нужно O (M) пространство для хранения скомпилированного шаблона для данного шаблона размера M

Приложения

Этот алгоритм особенно используется в текстовых инструментах для поиска шаблонов в текстовых файлах.

Перейти к поиску

Объяснение

Этот поиск похож на двоичный поиск, но вместо того, чтобы прыгать вперед и назад, мы будем прыгать только вперед. Имейте в виду, что Jump Search также требует сортировки коллекции.

В поиске с переходом мы перескакиваем на интервал sqrt(arraylength) вперед, пока не дойдем до элемента, большего, чем текущий элемент или конца массива. При каждом прыжке записывается предыдущий шаг.

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

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

Выполнение

 public static int jumpSearch(int[] integers, int elementToSearch) { 
 
 int arrayLength = integers.length; 
 int jumpStep = (int) Math.sqrt(integers.length); 
 int previousStep = 0; 
 
 while (integers[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) { 
 previousStep = jumpStep; 
 jumpStep += (int)(Math.sqrt(arrayLength)); 
 if (previousStep >= arrayLength) 
 return -1; 
 } 
 while (integers[previousStep] < elementToSearch) { 
 previousStep++; 
 if (previousStep == Math.min(jumpStep, arrayLength)) 
 return -1; 
 } 
 
 if (integers[previousStep] == elementToSearch) 
 return previousStep; 
 return -1; 
 } 

Мы начинаем с jumpstep из размера квадратного корня из длины массива и продолжаем двигаться вперед с тем же размером, пока не найдем элемент, равный или больший, чем элемент, который мы ищем.

Итак, сначала мы обращаемся к элементу с integers[jumpStep] , затем с integers[2jumpStep] , integers[3jumpStep] и так далее. Мы также сохраняем предыдущий посещенный элемент в переменной previousStep

Как только мы находим такое значение, что integers[previousStep] < elementToSearch < integers[jumpStep] , мы выполняем линейный поиск между integers[previousStep] и integers[jumpStep] или элементом, большим, чем elementToSearch .

Мы можем использовать такой алгоритм:

 int index = jumpSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67); 
 print(67, index); 

Выход:

 67 found at Index 5 

Сложность времени

Поскольку на каждой итерации мы перескакиваем на sqrt(arraylength) , временная сложность этого поиска составляет O (sqrt (N)) .

Космическая сложность

Сложность этого поиска составляет O (1), так как требуется только одна единица пространства для хранения искомого элемента.

Заявление

Этот поиск используется вместо двоичного поиска, когда возврат назад обходится дорого. С этим ограничением сталкиваются, когда мы используем вращающуюся среду, например приводы, когда поиск вперед выполняется легко, но многократный прыжок в измененном направлении обходится дорого.

Интерполяционный поиск

Объяснение

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

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

Поиск с интерполяцией использует формулы интерполяции, чтобы найти наиболее вероятное место, где элемент может быть найден в массиве. Однако, чтобы эти формулы были эффективными, массив поиска должен быть большим, иначе он будет работать как линейный поиск:

Выполнение

 public static int interpolationSearch(int[] integers, int elementToSearch) { 
 
 int startIndex = 0; 
 int lastIndex = (integers.length - 1); 
 
 while ((startIndex <= lastIndex) && (elementToSearch >= integers[startIndex]) && 
 (elementToSearch <= integers[lastIndex])) { 
 // using interpolation formulae to find the best probable position for this element to exist 
 int pos = startIndex + (((lastIndex-startIndex) / 
 (integers[lastIndex]-integers[startIndex]))* 
 (elementToSearch - integers[startIndex])); 
 
 if (integers[pos] == elementToSearch) 
 return pos; 
 
 if (integers[pos] < elementToSearch) 
 startIndex = pos + 1; 
 
 else 
 lastIndex = pos - 1; 
 } 
 return -1; 
 } 

Мы можем использовать этот алгоритм так:

 int index = interpolationSearch(new int[]{1,2,3,4,5,6,7,8}, 6); 
 print(67, index); 

Выход:

 6 found at Index 5 

Давайте посмотрим, как формулы интерполяции творит чудеса, чтобы найти 6 :

 startIndex = 0 
 lastIndex = 7 
 integers[lastIndex] = 8 
 integers[startIndex] = 1 
 elementToSearch = 6 

Теперь применим эти значения к формулам для оценки индекса элемента поиска:

$$
индекс = 0 + (7-0) / (8-1) * (6-1) = 5
$

Элемент с integers[5] равен 6, это тот элемент, который мы искали. Как мы видим здесь, индекс для элемента рассчитывается всего за один шаг, поскольку данные распределены равномерно.

Сложность времени

Наилучшая временная сложность для этого алгоритма составляет O (log log N), но в худшем случае, то есть когда элементы не распределены равномерно, она сравнима с временной сложностью линейного поиска, которая составляет O (N) .

Космическая сложность

Этому алгоритму также требуется только одна единица пространства для хранения искомого элемента. Следовательно, его пространственная сложность O (1) .

Заявление

Этот поиск полезен, когда данные равномерно распределены, как номера телефонов в каталоге.

Экспоненциальный поиск

Объяснение

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

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

Излишне говорить, что для того, чтобы это работало, коллекцию нужно отсортировать.

Выполнение

 public static int exponentialSearch(int[] integers, int elementToSearch) { 
 
 if (integers[0] == elementToSearch) 
 return 0; 
 if (integers[integers.length - 1] == elementToSearch) 
 return integers.length; 
 
 int range = 1; 
 
 while (range < integers.length && integers[range] <= elementToSearch) { 
 range = range * 2; 
 } 
 
 return Arrays.binarySearch(integers, range / 2, Math.min(range, integers.length), elementToSearch); 
 } 

Мы можем использовать этот алгоритм так:

 int index = exponentialSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67); 
 print(67, index); 

Вот как работает алгоритм:

Мы пытаемся найти элемент, который больше искомого. Мы делаем это, чтобы минимизировать диапазон элементов, которые мы ищем. Мы увеличиваем диапазон, умножая его на 2, и снова проверяем, достигли ли мы элемента, большего, чем элемент, который мы ищем, или конца массива. Как только одно из этих достижений достигнуто, мы выходим из цикла. Затем мы выполняем двоичный поиск с startIndex как range/2 и lastIndex как range .

В нашем случае это значение диапазона достигается в 8, а элемент в integers[8] - 95. Итак, диапазон, в котором мы выполняем двоичный поиск, равен:

 startIndex = range/2 = 4 
 
 lastIndex = range = 8 

При этом вызов двоичного поиска становится:

 Arrays.binarySearch(integers, 4, 8, 6); 

Выход:

 67 found at Index 5 

Здесь важно отметить, что мы можем ускорить умножение на 2, используя оператор сдвига влево range << 1 вместо оператора *

Сложность времени

Наихудшая временная сложность для этого типа поиска составляет O (log (N)) .

Космическая сложность

Этот алгоритм требует O (1) пространства для хранения искомого элемента, если базовый алгоритм двоичного поиска является итеративным.

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

Приложения

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

Поиск Фибоначчи

Объяснение

Поиск Фибоначчи использует подход «разделяй и властвуй», в котором мы неравномерно разделяем элементы в соответствии с рядами Фибоначчи. Этот поиск требует сортировки массива.

В отличие от двоичного поиска, где мы делим элементы на равные половины, чтобы уменьшить диапазон массива - в поиске Фибоначчи мы пытаемся использовать сложение или вычитание, чтобы получить меньший диапазон.

Помните, что формула ряда Фибоначчи:

$$
Фибо (N) = Фибо (N-1) + Фибо (N-2)
$

Первые два числа в этой серии - это Fibo(0) = 0 и Fibo(1) = 1 . Итак, согласно этой формуле, ряд выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... Здесь следует отметить следующие интересные наблюдения:

Fibo(N-2) составляет примерно Fibo(N)

Fibo(N-1) составляет примерно Fibo(N)

Поэтому, когда мы используем числа Фибоначчи для разделения диапазона, он разделяется в том же соотношении, что и выше.

Выполнение

Давайте посмотрим на реализацию, чтобы получить более четкое представление:

 public static int fibonacciSearch(int[] integers, int elementToSearch) { 
 
 int fibonacciMinus2 = 0; 
 int fibonacciMinus1 = 1; 
 int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; 
 int arrayLength = integers.length; 
 
 while (fibonacciNumber < arrayLength) { 
 fibonacciMinus2 = fibonacciMinus1; 
 fibonacciMinus1 = fibonacciNumber; 
 fibonacciNumber = fibonacciMinus2 + fibonacciMinus1; 
 } 
 
 int offset = -1; 
 
 while (fibonacciNumber > 1) { 
 int i = Math.min(offset+fibonacciMinus2, arrayLength-1); 
 
 if (integers[i] < elementToSearch) { 
 fibonacciNumber = fibonacciMinus1; 
 fibonacciMinus1 = fibonacciMinus2; 
 fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; 
 offset = i; 
 } 
 
 else if (integers[i] > elementToSearch) { 
 fibonacciNumber = fibonacciMinus2; 
 fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2; 
 fibonacciMinus2 = fibonacciNumber - fibonacciMinus1; 
 } 
 
 else return i; 
 } 
 
 if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch) 
 return offset+1; 
 
 return -1; 
 } 

Мы можем запустить этот алгоритм так:

 int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67); 
 print(67, index); 

Вот как работает алгоритм:

Он начинается с нахождения числа в ряду Фибоначчи, наиболее близкого к длине массива, но превышающего его. Это происходит, когда значение fibonacciNumber равно 13, что чуть больше, чем длина массива - 10.

Затем мы сравниваем элементы массива и на основе этого сравнения предпринимаем одно из следующих действий:

  • Сравните элемент для поиска с элементом в fibonacciMinus2 и верните индекс, если значение совпадает.
  • Если elementToSearch больше текущего элемента, мы перемещаемся на один шаг назад в ряду Фибоначчи и соответственно меняем значения fibonacciNumber , fibonacciMinus1 и fibonacciMinus2 . Смещение сбрасывается до текущего индекса.
  • Если elementToSearch меньше текущего элемента, мы перемещаемся на два шага назад в ряду фибоначчи и соответственно меняем значения fibonacciNumber , fibonacciMinus1 и fibonacciMinus2 .

Выход:

 67 found at Index 5 

Сложность времени

Наихудшая временная сложность этого поиска составляет O (log (N)) .

Космическая сложность

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

Это требование места не увеличивается с размером входного массива. Следовательно, мы можем сказать, что пространственная сложность поиска Фибоначчи равна O (1) .

Приложения

Этот поиск используется, когда разделение является дорогостоящей операцией для ЦП. Такие алгоритмы, как двоичный поиск, обычно не работают, поскольку они используют деление для разделения массива.

Еще одно преимущество этого поиска - когда элементы входного массива не помещаются в ОЗУ. В таких ситуациях локализованный объем операций, выполняемых этим алгоритмом, помогает ему работать намного быстрее.

API коллекций Java

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

Массивы

Массивы в Java можно искать с помощью одного из методов java.util.BinarySearch Бинарный поиск в версии Open JDK использует итеративную форму поиска.

Давайте быстро посмотрим, как мы можем использовать этот метод:

 int[] integers = {3, 22, 27, 47, 57, 67, 89, 91, 95, 99}; 
 
 int elementToSearch = 67; 
 
 int index = java.util.Arrays.binarySearch(integers, elementToSearch); 

Выход:

 67 found at Index 5 

Интерфейс списка

Интерфейс списка имеет в основном два метода, которые можно использовать для поиска: indexOf() и contains() .

Метод indexOf() возвращает индекс элемента, если он существует в списке, или -1 если он не существует.

Метод contains() возвращает true или false зависимости от существования элемента. Он внутренне вызывает метод indexOf() .

Интерфейс списка использует последовательный поиск для выполнения поиска по индексу, поэтому его временная сложность составляет O(N) .

Давайте попробуем выполнить поиск в List :

 java.util.List<Integer> integers = new java.util.ArrayList<>(); 
 integers.add(3); 
 integers.add(22); 
 integers.add(27); 
 integers.add(47); 
 integers.add(57); 
 integers.add(67); 
 integers.add(89); 
 integers.add(91); 
 integers.add(95); 
 integers.add(99); 
 
 int elementToSearch = 67; 
 
 int index = integers.indexOf(elementToSearch); 

Выход:

 67 found at Index 5 

Точно так же, если нас не интересует индекс, а нужно только знать, существует ли элемент в списке или нет, мы можем использовать метод contains() :

 integers.contains(67) 

Выход:

 true 

Интерфейс карты

Карта представляет собой структуру данных пары ключ-значение. Интерфейс Map в Java использует поиск на основе HashBased Binary Search Tree .

Класс java.util.HashMap использует хеш-значение key для хранения элементов на карте. Получение элемента из карты с использованием правильных ключей к хешу и хорошего алгоритма хеширования (так, чтобы не возникало коллизий) - это O(1) .

Другая реализация интерфейса Map - это java.util.TreeMap , который внутренне использует красно-черное дерево, которое является типом самобалансирующегося двоичного дерева поиска. Элементы, добавленные в это дерево, автоматически сохраняются в отсортированном виде по дереву.

Временная сложность поиска в двоичном дереве составляет O(log(N)) .

Давайте посмотрим, как мы можем искать элемент на карте:

 java.util.Map<Integer, String> integers = new java.util.HashMap<>(); 
 integers.put(3,"three"); 
 integers.put(22,"twentytwo"); 
 integers.put(27,"twentyseven"); 
 integers.put(47,"fortyseven"); 
 integers.put(57,"fiftyseven"); 
 integers.put(67,"sixtyseven"); 
 integers.put(89,"eightynine"); 
 integers.put(91,"ninetyone"); 
 integers.put(95,"ninetyfive"); 
 integers.put(99,"ninetynine"); 
 
 String value = integers.get(67); 
 
 System.out.println("the value at key 67 is: " + value); 

Мы создали карту с ключом как целое число и значением как это целое число в словах. Затем мы ищем ключ и получаем целое число в виде слов на выходе.

Здесь важно отметить, что карта не будет хранить повторяющиеся ключи. Если мы попытаемся вставить повторяющееся значение, оно перезапишет существующий ключ и значение новым.

Выход:

 the value at key 67 is: sixtyseven 

Map также содержит метод containsKey() который можно использовать для определения, существует ли данный ключ или нет:

 integers.containsKey(67); 

Установленный интерфейс

Структура Set используется для хранения уникальных элементов. Интерфейс Set по сути является оболочкой над Map описанным выше, и хранит элементы в Key of the Map .

Как и в случае с Map он использует Binary поиск и поиск Hash-based

 java.util.Set<Integer> integers = new java.util.HashSet<>(); 
 integers.add(3); 
 integers.add(22); 
 integers.add(27); 
 integers.add(47); 
 integers.add(57); 
 integers.add(67); 
 integers.add(89); 
 integers.add(91); 
 integers.add(95); 
 integers.add(99); 
 
 int elementToSearch = 67; 
 
 boolean isNumberExists = integers.contains(elementToSearch); 
 
 if (isNumberExists) 
 System.out.println(elementToSearch + " exists in the set"); 
 else 
 System.out.println(elementToSearch + " does not exist in the set"); 

Set нет индекса, и поэтому операция поиска contains() возвращает true или false зависимости от существования искомого элемента.

В этом случае, поскольку элемент существует в наборе, мы получаем следующий результат:

 67 exists in the set 

Сравнение времени алгоритма поиска

При этом часто бывает полезно запустить все эти алгоритмы несколько раз, чтобы понять, как они работают.

Давайте 573400 элемент 573400 в отсортированном массиве, заполненном миллионом целых чисел.

Вот результаты алгоритмов:


время (нс) Линейный Двоичный (итеративный) Двоичный (рекурсивный) Прыгать Интерполяция Экспоненциальный Фибоначчи Первый забег 5 229 901 23 014 14 928 125 647 18 661 49 762 13 373 Второй прогон 8 436 389 24 570 14 306 329 046 18 349 206 820 21 770 Третий пробег 7 207 909 24 569 23 326 585 005 19 593 106 054 23 325 Четвертый забег 5 888 615 33 589 27 057 218 327 23 015 111 341 25 813 Пятый заезд 3 002 466 20 216 46 962 132 800 15 861 65 311 20 216 Шестой пробег 6 896 901 12 440 26 124 212 107 7 465 106 054 38 254 Седьмой забег 6 916 495 59 714 13 373 210 241 15 240 126 891 13 684 Восьмерка 6 781 828 22 393 46 962 159 235 10 575 83 972 26 436 Девятый забег 6 917 116 11 507 18 660 265 911 28 302 130 002 12 751 Десятый забег 3 811 085 41 053 89 259 302 922 26 436 183 184 25 192


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

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

Заключение

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

В этой статье мы рассмотрели, как работают различные алгоритмы поиска и при каких обстоятельствах они идеально подходят. Мы также рассмотрели, как Java использует различные алгоритмы поиска во встроенном API коллекций.

Как всегда, вы можете найти исходный код алгоритмов, описанных в этой статье, здесь .

comments powered by Disqus

Содержание