Джо правильно заявляет в своем ответе , что можно ожидать, что метод двоичного поиска будет быстрее, чем Select, который, кажется, просто выполняет линейный поиск, даже если список отсортирован:
ClearAll[selectTiming]
selectTiming[length_, iterations_] := Module[
{lst},
lst = Sort[RandomInteger[{0, 100}, length]];
(Do[Select[lst, # == 2 &, 1], {i, 1, iterations}] // Timing //
First)/iterations
]
(я произвольно установил порог 2 для демонстрационных целей).
Однако функция BinarySearch в Combinatorica a) не подходит (она возвращаетэлемент, который соответствует запрошенному, но не первый (самый левый), что задает вопрос.
Чтобы получить крайний левый элемент, который больше порога, с учетом упорядоченного списка, мы можемвыполните рекурсивно:
binSearch[lst_,threshold_]:= binSearchRec[lst,threshold,1,Length@lst]
(*
return position of leftmost element greater than threshold
breaks if the first element is greater than threshold
lst must be sorted
*)
binSearchRec[lst_,threshold_,min_,max_] :=
Module[{i=Floor[(min+max)/2],element},
element=lst[[i]];
Which[
min==max,max,
element <= threshold,binSearchRec[lst,threshold,i+1,max],
(element > threshold) && ( lst[[i-1]] <= threshold ), i,
True, binSearchRec[lst,threshold,min,i-1]
]
]
или итеративно:
binSearchIterative[lst_,threshold_]:=Module[
{min=1,max=Length@lst,i,element},
While[
min<=max,
i=Floor[(min+max)/2];
element=lst[[i]];
Which[
min==max, Break[],
element<=threshold, min=i+1,
(element>threshold) && (lst[[i-1]] <= threshold), Break[],
True, max=i-1
]
];
i
]
Рекурсивный подход понятнее, но я остановлюсь на итеративном.
Чтобы проверить его скорость,
ClearAll[binSearchTiming]
binSearchTiming[length_, iterations_] := Module[
{lst},
lst = Sort[RandomInteger[{0, 100}, length]];
(Do[binSearchIterative[lst, 2], {i, 1, iterations}] // Timing //
First)/iterations
]
, который выдает
, поэтому намного быстрее и с лучшими характеристиками масштабирования.
На самом деле его не нужно компилироватьно я все равно.
В сВ таком случае, не используйте Select для длинных списков.
На этом мой ответ завершен.Далее следуют некоторые комментарии о выполнении бинарного поиска вручную или с помощью пакета Combinatorica.
Я сравнил скорость (скомпилированной) короткой процедуры для выполнения бинарного поиска с BinarySearch из Combinatorica.Обратите внимание, что это не делает то, что задает вопрос (и не делает BinarySearch из Combinatorica);код, который я привел выше, делает.
Бинарный поиск может быть реализован итеративно как
binarySearch = Compile[{{arg, _Integer}, {list, _Integer, 1}},
Module[ {min = 1, max = Length@list,
i, x},
While[
min <= max,
i = Floor[(min + max)/2];
x = list[[i]];
Which[
x == arg, min = max = i; Break[],
x < arg, min = i + 1,
True, max = i - 1
]
];
If[ 0 == max,
0,
max
]
],
CompilationTarget -> "C",
RuntimeOptions -> "Speed"
];
, и теперь мы можем сравнить это и BinarySearch с Combinatorica.Обратите внимание, что a) список должен быть отсортирован b) это не вернет первый соответствующий элемент, но a соответствующий элемент.
lst = Sort[RandomInteger[{0, 100}, 1000000]];
Давайте сравнимдве процедуры двоичного поиска.Повторяю 50000 раз:
Needs["Combinatorica`"]
Do[binarySearch[2, lst], {i, 50000}] // Timing
Do[BinarySearch[lst, 2], {i, 50000}] // Timing
(*
{0.073437, Null}
{4.8354, Null}
*)
Так что рукописный быстрее.Теперь, поскольку на самом деле бинарный поиск просто посещает 6-7 точек в списке для этих параметров (например, что-то вроде {500000, 250000, 125000, 62500, 31250, 15625, 23437}), очевидно, что разница просто накладная;возможно BinarySearch является более общим, например, или не скомпилировано.