Бинарный поиск в Эрланге за время lg (n)

Question

Я искал возможные обходные пути для выполнения бинарного поиска в Erlang и нашел http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ Но мне было интересно, работает ли решение в блоге в O (LG N). Теперь, так как повторение для двоичного поиска: T (n) = T (n / 2) + c, что дает мне время выполнения O (lg n).

Поскольку в массиве C у вас есть возможность доступа к любому элементу за O (1) времени. Но в erlang, если доступ к середине списка занимает cn времени, тогда бинарный поиск выполняется за общее линейное время так же плохо, как и линейный поиск.

Я наткнулся на списки: nth / 2 BIF для поиска n-го элемента в списке, но я не уверен относительно времени его выполнения.

Есть комментарии?

Answer 1

Существует несколько структур данных, которые обеспечивают доступ O (1) в Erlang: таблицы ETS, кортежи и двоичные файлы.

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

Кортежи разрешают O (1) доступ с element/2, но их изменение имеет определенные издержки (именно поэтому модуль массива использует деревья кортежей).

Тогда у вас есть двоичные файлы (<<1,2,3,4,5>>), которые допускают нечто похожее на арифметику указателей, как в следующем примере:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>.
<<"abcdefgh">>
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted.
<<"abcdefgh">>
3> X.
<<"d">>

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

Лучше всего будет использовать список значений, отсортировать его, а затем использовать list_to_tuple/1 для перемещения по нему с помощью element/2.

Однако я настоятельно рекомендую использовать дерево для поиска; Скорее всего, было бы намного проще использовать модуль gb_tree для построения сбалансированного дерева и все еще получать O (log N) поиск.

Answer 2

nth - это O (n).Используйте модуль массива для структуры данных с постоянным доступом (массив как в C - почти).