существует алгоритм, который быстрее, чем двоичный поиск, для поиска в отсортированных значениях массива?
в моем случае, у меня есть отсортированные значения (могут быть любые значения типа) в массиве A, мне нужно вернуть n, если значение, которое я искал, находится в диапазоне A[n] and A[n+1]
Вы можете сделать лучше, чем O (log n), если значения являются целыми числами, и в этом случае наилучшим наихудшим временем выполнения, которое вы можете достичь, с точки зрения n, является O (sqrt (log n)). В противном случае нет возможности бить O (log n), если в входной последовательности нет шаблонов. Существует два подхода, используемых для извлечения O (log n) в случае целых чисел.
Сначала вы можете использовать y-fast деревья, которые работают, сохраняя в хэш-таблице все префиксы, для которых вы храните хотя бы одно целое с этим префиксом. Это позволяет выполнить двоичный поиск, чтобы найти длину самого длинного совпадающего префикса. Это позволяет вам найти преемника элемента, для которого вы ищете во времени 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
Затем вы можете попробовать что-то вроде метода Ньютона и так далее. Эти типы алгоритмов часто сходятся быстрее, чем двоичный поиск, когда они работают, но я не знаю того, который гарантированно сходится для всех входных данных.
Если значения в списке распределены равномерно, вы можете попробовать взвешенный раскол вместо двоичного разделения, например. если желаемое значение составляет треть пути от текущего нижнего предела до текущего значения, тогда вы можете попробовать элемент, который также является третьим. Это может сильно пострадать в списках, где значения сгруппированы, хотя.
Да и нет. Да, поиск выполняется быстрее, чем в обычном поиске. Но я считаю, что они все еще O (lg N), только с более низкой константой.
Вы хотите минимизировать время, затрачиваемое на поиск элемента. Как правило, желательно использовать меньшее количество шагов, и один из способов приблизиться к этому - максимизировать ожидаемое количество элементов, которые будут устранены на каждом шаге. При делении пополам всегда устраняется ровно половина элементов. Вы можете сделать это лучше, если вы знаете что-то о распределении элементов. Но алгоритм выбора элемента раздела, как правило, сложнее, чем выбор средней точки, и эта дополнительная сложность может привести к сбою любой экономии времени, которую вы ожидаете получить от использования меньшего количества шагов.
Действительно, в такой ситуации лучше атаковать эффекты второго порядка, такие как локальность кэша, чем алгоритм поиска. Например, при повторном бинарном поиске одни и те же элементы (первый, второй и третий квартили) используются ОЧЕНЬ часто, поэтому размещение их в одной строке кэша может значительно превосходить произвольный доступ к списку.
Разделение каждого уровня на 4 или 8 равных секций (вместо 2) и выполнение линейного поиска через них также может быть быстрее, чем поиск пополам, поскольку линейный поиск не требует вычисления раздела, а также имеет меньшее количество данных зависимостей, которые могут вызывать кэш-киоски.
Но все они все еще O (lg N).
Как насчет следующего алгоритма? он называется экспоненциальным поиском и является одним из вариантов бинарного поиска. http://en.m.wikipedia.org/wiki/Exponential_search
Поиск элемента k в отсортированном массиве A размера n. Lookup A [2 ^ 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. (оба stpes находятся в log idx). В худшем случае, algo находится в O (log idx), если k является одним из самых больших элементов A или больше, чем любой элемент A. Мультипликативная константа больше, чем для двоичного поиска, но алгоритм будет работать быстрее для очень больших массивов и при поиске данных, которые относятся к началу массива.
Мне нравится иметь представление о минимальном размере n, где этот алгоритм становится предпочтительнее двоичного поиска, но я не знаю.
Вы всегда можете помещать их в хеш-таблицу, тогда поиск будет O (1). Это будет интенсивность памяти, хотя, и если вы будете продолжать добавлять элементы, хэш-таблицу, возможно, придется перевернуть. Re-bucketing - O (n), но он будет амортизироваться до O (1). Это существенно зависит от того, можете ли вы позволить себе это пространство и потенциальные промахи в кэше.
Прежде всего, измерить, прежде чем делать оптимизацию.
Вам действительно нужно оптимизировать этот поиск?
Если так, то, во-вторых, сначала подумайте об алгоритмической сложности. Например. можете ли вы использовать дерево (например, std::map, скажем) вместо массива? Если это так, это зависит от относительной частоты вложений/удалений в сравнении с поисками, но предпосылка наличия отсортированного массива под рукой указывает на то, что обыски часто происходят по сравнению с изменениями набора данных, так что было бы целесообразно сделать небольшую дополнительную работу для вставки/удаления, делая каждый поиск намного быстрее, а именно логарифмическое время.
Если вы обнаружите, что время поиска - это узкое место, которое требует адресации, и нет, невозможно изменить представление данных, а список короток, тогда линейный поиск будет, как правило, более быстрым, потому что он меньше работает для сравнения.
В противном случае, если список длиннее, и никакое конкретное распределение значений не известно или не принято, и значения не могут рассматриваться как числовые, а потребление памяти должно быть постоянным (исключая, например, построение хеш-таблицы) тогда двоичный поиск создает 1 бит информации для сравнения и, вероятно, лучше всего подходит для первого поиска.
Приветствия и hth.
В двоичном поиске вы разбиваете список на два "подсписок", и вы только выполняете поиск в подсписке, который может содержать значение. В зависимости от размера вашего массива вы можете увидеть ускорение, если вы разделите массив на более чем два сращения.
Вы можете определить, в какой области массива вы должны искать, указав индекс, который вы ищете в первую очередь. Как в телефонной книге большого города, где вы можете видеть снаружи, где вам нужно начать поиск. (У меня проблемы с выражением моей идеи в тексте, и я еще не нашел ссылку на английском языке, что объясняет это лучше).
Если у вас есть огромное количество чисел для поиска, и по какой-то случайности они сортируются по-разному, вы можете сделать это в O (n + m), где m - количество найденных чисел. В основном только ваш типичный алгоритм слияния с небольшим изменением записи, значение которого каждый проверенный номер будет вставлен раньше, если он должен быть вставлен в массив.
Вы всегда можете обменять пространство... И время других операций. Предполагая, что все ваши элементы являются постоянными размерами p бит, вы можете создать массивный массив, который хранит для каждого возможного значения, который вы могли бы найти, индекс следующего большего значения, хранящегося в настоящее время. Этот массив должен быть бит 2 ^ p * lg (n), где n - это сохраненные числовые значения. Каждая вставка или удаление O (2 ^ p), но обычно около 2 ^ p/n, потому что вам нужно пройти обновление всех этих индексов.
Но ваш поиск теперь O (1)!
ОК, хорошо, это не очень практично. Но разделение входа на блоки аналогичным образом могло бы уменьшить константу перед вашим журналом. Возможно.
Хотя в общем случае вы не можете сделать лучше, чем O (log N), вы можете хотя бы оптимизировать это, тем самым значительно уменьшая константу пропорциональности перед O (log N).
Если вам нужно выполнить несколько поиска в одном массиве, они могут быть векторизованы с использованием расширений SIMD, что приведет к дальнейшему сокращению затрат на вычисления.
В частности, если вы имеете дело с массивами чисел с плавающей запятой, которые удовлетворяют определенным свойствам, то есть есть способы создать специальный индекс, который затем позволяет искать массив в O (1).
Все вышеперечисленные аспекты обсуждаются с результатами теста в: Cannizzo, 2015, Быстрая и векторная альтернатива двоичному поиску в O (1), применимая к широкой области сортированных массивов чисел с плавающей запятой Документ поставляется с исходным кодом на github.