Быстрее, чем двоичный поиск упорядоченного списка

Question

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

в моем случае у меня есть отсортированные значения (могут быть значения любого типа) в массиве AМне нужно вернуть n, если значение, которое я искал, находится в диапазоне A[n] and A[n+1]

Answer 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).

Оптимальный компромисс между этими двумя структурами данных происходит, когда logw = sqrt (log n), давая время работы O (sqrt (log n)).

Подробнее об этом см. в лекциях 12 и 13 курса Эрика Демейна: http://courses.csail.mit.edu/6.851/spring07/lec.html

Answer 2

Одна из возможностей - рассматривать это как поиск корней функции.По сути, поиск:

a[i] <= i <= a[i + 1]

эквивалентен:

a[i] - i <= 0 <= a[i + 1] - i

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

http://en.wikipedia.org/wiki/Root-finding_algorithm

Answer 3

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

Answer 4

А как насчет следующего алгоритма? это называется Экспоненциальный поиск и является одним из вариантов бинарного поиска. 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. (оба stpes находятся в log idx). В худшем случае, алгоритм находится в O (log idx), если k находится среди самых больших элементов A или больше, чем любой элемент A. Мультипликативная константа больше, чем для бинарного поиска, но алгоритм будет работать быстрее для очень больших массивы и при поиске данных, которые к началу массива.

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

Answer 5

Да и нет. Да, есть поиски, которые в среднем быстрее, чем поиск пополам. Но я считаю, что они все еще O (LG N), просто с более низкой константой.

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

Действительно, в такой проблеме лучше атаковать эффекты второго порядка, такие как локальность кэша, чем алгоритм поиска. Например, при повторном бинарном поиске одни и те же несколько элементов (первый, второй и третий квартили) используются ОЧЕНЬ часто, поэтому размещение их в одной строке кэша может значительно превзойти произвольный доступ в список.

Разделение каждого уровня, скажем, на 4 или 8 равных секций (вместо 2) и выполнение линейного поиска по ним также может быть быстрее, чем поиск по разделам, потому что линейный поиск не требует вычисления раздела, а также содержит меньше данных зависимости, которые могут привести к остановке кэша.

Но все это по-прежнему О (LG N).

Answer 6

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

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

В частности, если вы имеете дело с массивами чисел с плавающей запятой, которые удовлетворяют определенным свойствамкроме того, существуют способы построения специального индекса, который затем позволяет искать массив в O (1).

Все вышеперечисленные аспекты обсуждаются с результатами теста в: Cannizzo, 2015, Fast and VectorizableАльтернатива двоичному поиску в O (1), применимая к широкому домену отсортированных массивов чисел с плавающей запятой Статья поставляется с исходным кодом на github .

Answer 7

Прежде всего, измерьте перед выполнением оптимизации.

Вам действительно нужно оптимизировать этот поиск?

Если это так, то, во-вторых, сначала подумайте об алгоритмической сложности,Например, вы можете использовать дерево (например, std::map) вместо массива?Если это так, то это зависит от относительной частоты вставок / удалений по сравнению с поиском, но предпосылка наличия отсортированного массива указывает на то, что поиски являются частыми по сравнению с изменениями в наборе данных, так что имеет смысл выполнить небольшую дополнительную работу длявставки / удаления, что делает каждый поиск намного быстрее, а именно - логарифмическое время.

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

В противном случае, если список длиннее, а конкретное распределение значений не известно или не предполагается, а значения не могутследует рассматривать как числовое, а потребление памяти должно быть постоянным (скажем, исключая создание хеш-таблицы), тогда двоичный поиск производит 1 бит информации на сравнение и, вероятно, является лучшим, что вы можете сделать для первого поиска.

Ура & hth.

Answer 8

Вы всегда можете поместить их в хеш-таблицу, тогда поиск будет O (1). Это будет занимать много памяти, и если вы продолжите добавлять элементы, хэш-таблицу, возможно, придется переформатировать. Повторное ведение - это O (n), но оно амортизируется до O (1). По сути, это зависит от того, можете ли вы позволить себе это место, и возможный промах кеша.

Answer 9

Если у вас есть огромное количество чисел, которые можно найти, и по какой-то случайности они ТАКЖЕ отсортированы, вы можете сделать это в O (n + m), где m - количество чисел, которые нужно найти.По сути, это просто ваш типичный алгоритм слияния, с небольшими изменениями, чтобы записать, какое значение каждое проверенное число будет вставлено ранее, если бы оно было вставлено в массив.другие операции.Предполагая, что все ваши элементы имеют постоянный размер p бит, вы можете создать массив, который будет хранить для каждого возможного значения, которое вы можете искать, индекс следующего большего значения, сохраненного в данный момент.Этот массив должен быть 2 ^ p * lg (n) бит, где n - это сохраненные числовые значения.Каждая вставка или удаление - O (2 ^ p), но обычно около 2 ^ p / n, потому что вам нужно обновить все эти индексы.

Но ваш поиск теперь O (1)!

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

Answer 10

В бинарном поиске вы разбиваете список на два «подсписка» и ищете только тот подсписок, который может содержать значение.В зависимости от того, насколько велик ваш массив, вы можете увидеть ускорение, если разделите массив на более чем два сплайса.искать в первую очередь.Как в телефонной книге большого города, где вы можете увидеть снаружи, где вы должны начать поиск.(У меня проблемы с выражением моей идеи в тексте, и я пока не нашел ссылки на английском языке, которая объясняет это лучше).