есть ли алгоритм, который быстрее, чем двоичный поиск, для поиска в отсортированных значениях массива?
в моем случае у меня есть отсортированные значения (могут быть значения любого типа) в массиве A, мне нужно вернуть n, если значение, которое я искал, находится в диапазоне A[n] and A[n+1]
Вы можете сделать лучше, чем O (log n), если значения являются целыми числами, и в этом случае наилучшее время работы в худшем случае, которое вы можете достичь, с точки зрения n, равно O (sqrt (log n)). В противном случае невозможно превзойти O (log n), если во входной последовательности нет шаблонов. Есть два подхода, которые используются для того, чтобы превзойти O (log n) в случае целых чисел.
Во-первых, вы можете использовать y-быстрые деревья, которые работают, сохраняя в хеш-таблице все префиксы, для которых вы сохраняете хотя бы одно целое число с этим префиксом. Это позволяет вам выполнить двоичный поиск, чтобы найти длину самого длинного совпадающего префикса. Это позволяет вам найти преемника элемента, который вы ищете, за время O (log w), где w - количество бит в слове. Есть некоторые детали, которые нужно поработать, чтобы сделать эту работу и использовать только линейное пространство, но они не так уж плохи (см. Ссылку ниже).
Во-вторых, вы можете использовать деревья слияния, в которых используются битовые приемы, позволяющие выполнять сравнения w ^ O (1) всего за постоянное количество инструкций, что дает время выполнения O (log n / log w).
Оптимальный компромисс между этими двумя структурами данных происходит, когда log w = sqrt (log n), что дает время выполнения O (sqrt (log n)).
Подробнее об этом см. Лекции 12 и 13 курса Эрика Демейна: http://courses.csail.mit.edu/6.851/spring07/lec.html
Одна из возможностей - рассматривать это как поиск корней функции. В основном, нахождение:
a[i] <= i <= a[i + 1]
Эквивалентно:
a[i] - i <= 0 <= a[i + 1] - i
Тогда вы могли бы попробовать что-то вроде метода Ньютона и так далее. Такие алгоритмы часто сходятся быстрее, чем бинарный поиск, когда они работают, но я не знаю ни одного, который гарантированно сходился бы для всех входных данных.
http://en.wikipedia.org/wiki/Root-finding_algorithm
Если значения в списке распределены равномерно, вы можете попробовать взвешенное разделение вместо двоичного, например если желаемое значение составляет треть пути от текущего нижнего предела до текущего значения, вы можете попробовать элемент, который также составляет треть пути. Это может сильно пострадать в списках, где значения сгруппированы.
И да и нет. Да, есть поисковые запросы, которые в среднем быстрее, чем поиск с разделением пополам. Но я считаю, что они все еще O (lg N), только с более низкой константой.
Вы хотите свести к минимуму время, затрачиваемое на поиск элемента. Обычно желательно использовать меньше шагов, и один из способов приблизиться к этому - максимизировать ожидаемое количество элементов, которые будут удалены на каждом шаге. При делении пополам всегда удаляется ровно половина элементов. Вы можете добиться большего, если знаете что-то о распределении элементов. Но алгоритм выбора элемента раздела обычно более сложен, чем выбор средней точки, и эта дополнительная сложность может подавить любую экономию времени, которую вы ожидали получить за счет меньшего количества шагов.
На самом деле, в такой задаче лучше атаковать эффекты второго порядка, такие как локальность кеша, чем алгоритм поиска. Например, при повторном бинарном поиске одни и те же элементы (первый, второй и третий квартили) используются ОЧЕНЬ часто, поэтому их размещение в одной строке кэша может быть намного лучше, чем произвольный доступ к списку.
Разделение каждого уровня, скажем, на 4 или 8 равных частей (вместо 2) и выполнение линейного поиска по ним также может быть быстрее, чем поиск с разделением пополам, потому что линейный поиск не требует вычисления раздела, а также имеет меньше зависимостей данных, которые могут вызвать срыв кеша.
Но все это по-прежнему O (lg N).
А как насчет следующего алгоритма? он называется экспоненциальным поиском и представляет собой одну из разновидностей бинарного поиска. http://en.m.wikipedia.org/wiki/Exponential_search
Поиск элемента k в отсортированном массиве A размера n. Ищите A [2 ^ i] для i = 0, 1, 2, ..., пока вы не выйдете за позицию k в A., затем выполните двоичный поиск в части массива слева (меньше), чем i.
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
Этот алгоритм будет работать на O (log idx), где idx - это индекс k в A. (оба stpe находятся в log idx). В худшем случае алгоритм находится в O (log idx), если k входит в число самых больших элементов A или больше любого элемента A. Мультипликативная константа больше, чем для двоичного поиска, но алгоритм будет работать быстрее для очень больших массивы и при поиске данных в начале массива.
Я хотел бы иметь некоторое представление о минимальном размере n, при котором этот алгоритм становится предпочтительнее бинарного поиска, но я не знаю.
Прежде всего, измерьте, прежде чем проводить оптимизацию.
Вам действительно нужно оптимизировать этот поиск?
Если так, то, во-вторых, сначала подумайте об алгоритмической сложности. Например. можно ли использовать дерево (например, std::map) вместо массива? Если это так, то это зависит от относительной частоты вставок / удалений по сравнению с поисками, но предпосылка наличия отсортированного массива под рукой указывает на то, что поиски выполняются часто по сравнению с изменениями набора данных, поэтому было бы разумно проделать небольшую дополнительную работу для вставки / удаления, что значительно ускоряет каждый поиск, а именно логарифмическое время.
Если вы обнаружите, что время поиска действительно является узким местом, требующим решения, и нет, изменение представления данных невозможно, а список короткий, то линейный поиск, как правило, будет быстрее, поскольку он требует меньше работы на сравнение.
В противном случае, если список длиннее, и никакое конкретное распределение значений не известно или не предполагается, и значения не могут рассматриваться как числовые, а потребление памяти должно быть постоянным (например, исключая создание хэш-таблицы), тогда двоичный поиск дает 1 бит информации за одно сравнение и, вероятно, это лучшее, что вы можете сделать для первого поиска.
Ура & hth.
Вы всегда можете поместить их в хеш-таблицу, тогда поиск будет O (1). Однако это будет интенсивно использовать память, и, если вы продолжите добавлять элементы, может потребоваться повторное преобразование хэш-таблицы. Повторное ведение ведра - это O (n), но оно будет амортизировано до O (1). По сути, это зависит от того, можете ли вы позволить себе это пространство, и от возможных промахов в кеше.
Хотя в общем случае вы не можете добиться большего, чем O (log N), вы можете, по крайней мере, оптимизировать это, тем самым значительно уменьшив константу пропорциональности перед O (log N).
Если вам нужно выполнить несколько поисков в одном массиве, их можно векторизовать с помощью расширений SIMD, что еще больше снизит стоимость вычислений.
В частности, если вы имеете дело с массивами чисел с плавающей запятой, которые удовлетворяют определенным свойствам, тогда есть способы создать специальный индекс, который затем позволяет искать массив в O (1).
Все вышеперечисленные аспекты обсуждаются с результатами тестирования в: Cannizzo, 2015, Быстрая и векторизуемая альтернатива двоичному поиску в O (1) Применимо к широкой области отсортированных массивов чисел с плавающей запятой Документ поставляется с исходным кодом на github.
Об этом упоминалось в разных комментариях, но я думаю, что естественным и простым ответом на этот конкретный вопрос (любой тип, значения в массиве) был бы поиск с интерполяцией:
Вместо вычисления средней точки поиск с интерполяцией оценивает положение целевого значения с учетом самого низкого и самого высокого элементов в массиве, а также длины массива. Он работает на том основании, что во многих случаях средняя точка - не лучший вариант. Например, если целевое значение близко к самому высокому элементу в массиве, оно, скорее всего, будет расположено рядом с концом массива.
Цитата из: https://en.wikipedia.org/wiki/Binary_search_algorithm
Основная страница: https://en.wikipedia.org/wiki/Interpolation_search
При условии равномерного распределения он может приближаться к O(log log N)
Поскольку в наши дни процессоры настолько быстрые по сравнению с доступом к памяти (программа для ОЗУ, как вы когда-то делали для диска), вычисления индекса / сравнения, вероятно, будут дешевыми по сравнению с каждой выборкой данных. Также можно немного повысить производительность с помощью линейного поиска, когда поиск будет достаточно сужен (используя локальность памяти / кеша).
При бинарном поиске вы разбиваете список на два «подсписка» и выполняете поиск только в подсписке, который может содержать значение. В зависимости от размера вашего массива вы можете увидеть ускорение, если разделите массив на более чем два соединения.
Вы можете определить, в какой области массива вам нужно выполнить поиск, сохраняя индекс, который вы ищете в первую очередь. Как в телефонной книге большого города, где видно со стороны, откуда нужно начинать поиск. (Мне трудно выразить свою идею в тексте, и я еще не нашел ссылку на английском, которая лучше объясняет это).
Если вам нужно найти огромное количество чисел и по какой-то случайности они ТАКЖЕ сортируются, вы можете сделать это за O (n + m), где m - количество чисел, которые нужно найти. В основном это ваш типичный алгоритм слияния с небольшими изменениями, чтобы записать, какое значение каждое проверяемое число будет вставлено раньше, если оно будет вставлено в массив.
Всегда можно обменять пространство ... И время других операций. Предполагая, что все ваши элементы имеют постоянный размер p бит, вы можете создать массивный массив, в котором для каждого возможного значения, которое вы могли бы найти, будет храниться индекс следующего большего значения, хранящегося в настоящее время. В этом массиве должно быть 2 ^ p * lg (n) бит, где n - сохраненные числовые значения. Каждая вставка или удаление - это O (2 ^ p), но обычно около 2 ^ p / n, потому что вам нужно обновить все эти индексы.
Но ваш поиск теперь O (1)!
Ладно, ладно, это непрактично. Но разделение ввода на блоки аналогичным образом могло бы уменьшить константу перед вашим журналом. Возможно.
