Comments 54
Неужели написать бенчмарк для этого примера кода дольше, чем статью?
Я не специалист в них, поэтому могу не учесть множество факторов и прийти к ошибочным выводам. Например, я понятия не имею, на каком железе должен был запускаться код Ричарда — и не понимаю, насколько в данном случае это может повлиять на результат.
Так если вы не пишете и не проектируете код – вам не нужен и результат бенчмарка :-)
(вообще код немного пишу, но не в продакшн, а для себя — на моих масштабах можно всё делать линейно и не париться, да :))
1) Бинпоиск быстрее. Он не прав
2) Линейный поиск быстрее. Но он быстрее совсем не значительно, но каждый программист, который это читает задается вопросом «да что тут вообще происходит, господи». Даже если эта секция действительно супер-мега-очень критическая и этот мили-выигрыш решает, нужно написать комментарий об этом. Желательно капслоком. Вообще на всех подозрительных оптимизациях так делать необходимо, иначе ущерба больше, чем пользы
И комментарий нужен если человек действительно задумывался о таких тонкостях, а не просто влепил первый попавшийся алгоритм, успешно решающий задачу. Например, «требований к скорости нет, так что линейный поиск использован ради сопровождаемости» или «на такой-то машине этот способ работает на 0.1% лучше бинарного».
Зависит, наверное, от размеров и способа доступа к элементам.
Но если те же инты в векторе — то я бы до ~50 элементов, а то и больше (конкретное решение надо принимать по результатам бенчей в наиболее вероятном окружении) остался бы в линейном алгоритме.
(у линейного поиска есть ещё преимущество в этом случае: ему совсем не критично условие сортированности массива входных данных).
(в примере статьи вообще странное… Вроде список (list), а доступ при этом по индексу. Если там в самом деле список (не вектор), то в нём самом Get(idx) уже легко может подразумевать линейный поиск где-то под капотом. И в этом случае (раз уж всё изначально так) проще взять next() вместо get(idx), и просто добавить своих критериев.
Идея в том что выше мы пофиксим бинарный поиск для APE-кодека, чтобы он всегда разбивал подмассив на равновероятные части, а не равные по длине.
. (Уже ответили ниже)
Worst-case complexity работает для любого распределения.— это как? Наихудший случай есть зачастую специально подобранный единичный пример.
Вообще, по коду много других вопросов возникает. element не обязан быть совместим по типам с содержимым сортированного листа. И для них вполне может быть определён только equals, а не compare. Собственнло, и compare тоже может быть таким, что не совпадает с compare по которому список отсортирован.
А можно причинами поинтересоваться?
И что такое современные процессоры, какой архитектуры?
Что-то я не уверен, что на десятках элементов выгоднее довольно приличное количество переходов вместо линейного прохода.
Но это чисто теоретически, а вы, видимо, знаете практику хотя бы для 64-битных интов.
Линейный доступ выигрывает из-за эффективного использования кэша за счет префетчинга и из-за отсутствия сбоев конвеера за счет эффективного предсказания переходов. Но если идет поиск постоянно в одном наборе данных небольшого размера, то скорее всего он и так будет закэширован.
Если речь идет о простых типах, тех же интах, то, как я написал, тут выигрыш у бинарного поиска начинается где то на сотнях элементов. Логарифм 100 — будет в районе 7, т.е. сравнений будет как минимум раз в 10 меньше при бинарном поиске, для 200 меньше уже в 20 раз и т.д. Т.е. линейный поиск должен быть во столько раз эффективнее на одно сравнение чтобы выигрывать. Ну видимо где то в этом районе сейчас граница и проходит. Потому что по опыту получаются именно такие размерности, когда бинарный поиск начинает выигрывать.
Если же говорить о более сложных типах — строках или каких то классах, имеющих свою сложную функцию сравнения, то само время выполнения функции сравнения становится уже сравнимым с оверхедом от отсутствия кэширования/сбоев конвейера и эффективность линейного поиска на одну операцию сравнения становится выше уже не в десятки, а в несколько раз или даже просто на несколько процентов. Поэтому в этом случае граница и смещается в область десятков элементов, а не сотен.
Вообще, все эти оценки производительности (О-нотация) асимптотические. То есть, это оценка производительности, когда число итерации стремиться к бесконечности.
А для малых массивов, линейный поиск будет категорично быстрее. Просто из за того что у алгоритма банально меньше инструкции.
Кстати, то же самое и даже в большей мере верно и для сортировки. Для маленьких массивов сортировка пузырьком быстрее из за простотой кода. Это известный факт, который используют например чтобы ускорить другие методы сортировки, используя метод пузырьком когда размер сортируемого отрезка меньше некоторой границы.
Там операция а+б может занимать, и часто занимает, больше инструкций, чем операция «сходи попить кофе».
Если же говорить о языках с вменяемыми трансляторами, не испорченными параноидальными видениями миражей NULL pointer в пустыне Сахара, являющихся адептам секты «священного кода» в полночь, то операция shift right уменьшающая скалярное значение в два раза занимает ровно 6 инструкций процессора и ни одной больше, операция сложения занимает 3. То есть если только выбор не ограничен 2-мя соседними значениями, то бинарный поиск уже выиграл.
операция shift right уменьшающая скалярное значение в два раза занимает ровно 6 инструкций процессора и ни одной больше, операция сложения занимает 3.— это откуда?
— test.c
#include <stdio.h>
int main()
{
int i = 8;
i = i + 8;
i = i >> 1;
}
—
Транслируете в выполнимый в Вашем любимом трансляторе.
Стартуете под трассировкой.
Включаете опцию «трассировать инструкции машинного кода»
И читаете выполненные операции, пошагово.
Открываете спецификации компании Intel по выполнению машинных инструкций.
Если что — то не соответствует, буду благодарен и с удовольствием отвечу на любые нарекания или пожелания улучшений.
Открываете спецификации компании Intel по выполнению машинных инструкций.Процессоры делает не только Intel.
Интел в данном случае приведен по единственной причине, в отличие от множества других производителей фирма опубликовала и сделала доступным для всех техническую документацию по данному вопросу.
Взял, проверил. Разумеется, данный код будет работать только без оптимизаций — оптимизация выкинет всю работу с i нафиг; надо оформлять тогда во что-то другое, не в main, и чтобы результат i возвращался. И вижу:
main: pushq %rbp movq %rsp, %rbp movl $8, -4(%rbp) addl $8, -4(%rbp) sarl -4(%rbp) movl $0, %eax popq %rbp ret
Как видим, и сложение, и сдвиг заняли ровно 1 инструкцию.
Хорошо, делаем отдельной функцией с оптимизацией:
int foo(int i) { i = i + 8; i = i >> 1; return i; }
Получаем:
_foo: leal 8(%rdi), %eax sarl %eax ret
Снова одна инструкция.
Так что у вас за компилятор такой безумный? У меня обычный GCC 7.4.0.
Или вы под «инструкциями» имели в виду микрооперации после разложения в тот внутренний RISC, на котором работает x86? Всё равно не сходится, неоткуда взять 6 микроопераций на сдвиг.
Операции на регистрах на современных процессорах с системой команд AMD64 выполняются за такт или меньше. Считать такты не зная ни языка ассемблера, ни устройство современных процессоров — глупо.
Но не тот, а поведения.
Продолжайте…
А может все проще, и потом окажется, что там LinkedList был. Бинарный поиск получится O(n log n).
Как это сделали в MS.
Суть в том, что накладные расходы (инициализация таблицы) пропорциональны размеру найденного числа. Так что для больших чисел не так важно, нашли линейно или бинпоиском, а для маленьких — линейный будет сильно быстрее.
То есть может оказаться, что линейный поиск в среднем медленнее, но в силу каких-то обстоятельств будет разумнее в использовании. Например, потому что лучше теряется в каких-то дополнительных расходах и меньше портит частные случаи.
Эм, сравнивается element
и sortedList.get(index)
, разве нет?
Не, это последствие того, что все сложные типы являются ссылочными. Не спец по Java, но думаю ваш вариант вполне себе валиден, просто будет сравнивать не значения, а ссылки
Что интересно, эвристика (по вашей ссылке) для отсортированного вектора
if (val == ikey) return x;
if (val >= ikey) break;
скорее вредит производительности линейного поиска: цикл только с проверкой на равенство работает быстрее, а добавляя эту эвристику, получаем на маленьких векторах результаты, близкие к бинарному поиску.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <Windows.h>
const size_t VECSIZE = 10;
const size_t MAXVALUE = 64;
const size_t NUM_VECTORS = 10000;
size_t linsearch(int* arr, size_t size, int val)
{
for (size_t i = 0; i < size; i++)
if (arr[i] == val) return i;
return (size_t)-1;
}
size_t linsearch2(int* arr, size_t size, int val)
{
for (size_t i = 0; i < size; i++) {
if (arr[i] == val) return i;
if (arr[i] > val) break;
}
return (size_t)-1;
}
size_t binsearch(int* arr, size_t size, int val)
{
size_t low = 0, high = size;
while (low < high) {
size_t med = (low + high)/2;
if (val == arr[med]) return med;
if (val < arr[med]) high = med; else low = med+1;
}
return (size_t)-1;
}
int compare_ints(const void* a, const void* b)
{
const int *arg1 = static_cast<const int*>(a);
const int *arg2 = static_cast<const int*>(b);
return *arg1 - *arg2;
}
int* prepare(size_t size)
{
int* result = new int[size];
for (size_t i = 0; i < size; i++)
result[i] = rand() % MAXVALUE;
qsort(result, size, sizeof(result[0]), compare_ints);
return result;
}
int main()
{
int** p = new int*[NUM_VECTORS];
for (size_t i = 0; i < NUM_VECTORS; i++)
p[i] = prepare(VECSIZE);
int* search = new int[NUM_VECTORS];
for (size_t i = 0; i < NUM_VECTORS; i++) {
int val = rand() % MAXVALUE;
search[i] = val;
size_t s1 = binsearch(p[i], VECSIZE, val);
size_t s2 = linsearch(p[i], VECSIZE, val);
size_t s3 = linsearch2(p[i], VECSIZE, val);
if (s1 != (size_t)-1 && p[i][s1] != val
|| s2 != (size_t)-1 && p[i][s2] != val
|| s3 != (size_t)-1 && p[i][s3] != val
|| ((s1 == (size_t)-1 || s2 == (size_t)-1 || s3 == (size_t)-1) && (s1 != s2 || s2 != s3)))
{
printf("failed!");
return 1;
}
}
uint64_t c0; QueryPerformanceCounter((LARGE_INTEGER*)&c0);
size_t x1 = 0;
for (size_t i = 0; i < NUM_VECTORS; i++) {
if (binsearch(p[i], VECSIZE, search[i]) != (size_t)-1) x1++;
}
uint64_t c1; QueryPerformanceCounter((LARGE_INTEGER*)&c1);
size_t x2 = 0;
for (size_t i = 0; i < NUM_VECTORS; i++) {
if (linsearch(p[i], VECSIZE, search[i]) != (size_t)-1) x2++;
}
uint64_t c2; QueryPerformanceCounter((LARGE_INTEGER*)&c2);
size_t x3 = 0;
for (size_t i = 0; i < NUM_VECTORS; i++) {
if (linsearch2(p[i], VECSIZE, search[i]) != (size_t)-1) x3++;
}
uint64_t c3; QueryPerformanceCounter((LARGE_INTEGER*)&c3);
if (x1 != x2 || x2 != x3) {
printf("failed!!");
return 1;
}
printf("bin: %lld\n", c1-c0);
printf("lin: %lld\n", c2-c1);
printf("lne: %lld\n", c3-c2);
delete[] search;
for (size_t i = 0; i < NUM_VECTORS; i++)
delete[] p[i];
delete[] p;
return 0;
}
bin: 423
lin: 214
lne: 404
Само-собой, код должен был заменён на нормальный перед сдачей на ревью или, в крайнем случае, отклонён ревьювером с просьбой заменить на нормальный. Если этот код попал в продакшн — то это ошибка не Ричарда, а сеньйоров\тимлида\менеджера компании Хули.
Ну, я взял и сделал некоторые тесты. Выходит, что если поиск в 32 битовом массиве, то линейный поиск быстрее при размерах массива меньше чем 8 элементов. Примерно до размер в 10 элементов идут наравне и после этого бинарный поиск всегда быстрее.
Выглядит примерно так: (время по Y в мкс за 1 000 000 повторении)
include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 0
include "%lib%/freshlib.asm"
MAX_ARRAY_SIZE = 20
REPEAT_TEST = 1000000
uglobal
array rd MAX_ARRAY_SIZE
tstart dd ?
timelin dd ?
timebin dd ?
endg
start:
InitializeAll
xor ecx, ecx
.init_array:
mov [array+4*ecx], ecx
inc ecx
cmp ecx, MAX_ARRAY_SIZE
jne .init_array
xor ebx, ebx
inc ebx
mov ecx, $0fffffff
.heat1:
dec ecx
jnz .heat1
.size_loop:
stdcall GetFineTimestamp
mov [tstart], eax
mov ecx, REPEAT_TEST
xor esi, esi
.lin_repeat:
dec ecx
js .end_lin_repeat
; here esi is the value searched and ebx is the size of the array.
; ecx is the current repeat counter, preserve it!
inc esi
xor eax, eax
cmp esi, ebx
cmovae esi, eax
.search_lin:
cmp [array+4*eax], esi
je .lin_repeat ; element found
inc eax
cmp eax, ebx
jb .search_lin
jmp .lin_repeat ; element not found (not possible!)
.end_lin_repeat:
stdcall GetFineTimestamp
xchg eax, [tstart]
sub eax, [tstart]
neg eax
mov [timelin], eax
mov ecx, REPEAT_TEST
xor esi, esi
.bin_repeat:
dec ecx
js .end_bit_repeat
; here esi is the value searched and ebx is the size of the array.
; ecx is the current repeat counter, preserve it!
xor edi, edi ; start
mov edx, ebx
dec edx
inc esi
cmp esi, ebx
cmovae esi, edi
.loop_bin:
cmp edi, edx
ja .bin_repeat ; element not found (not possible!)
lea eax, [edi+edx]
shr eax, 1 ; middle.
cmp esi, [array+4*eax]
je .bin_repeat ; element found!
jb .move_end
; move the start of the interval
lea edi, [eax+1]
jmp .loop_bin
.move_end:
lea edx, [eax-1]
jmp .loop_bin
.end_bit_repeat:
stdcall GetFineTimestamp
xchg eax, [tstart]
sub eax, [tstart]
neg eax
mov [timebin], eax
; Output comma separated values.
stdcall NumToStr, ebx, ntsDec or ntsSigned
mov edx, eax
stdcall StrCat, edx, txt ", "
stdcall NumToStr, [timelin], ntsDec or ntsSigned
stdcall StrCat, edx, eax
stdcall StrDel, eax
stdcall StrCat, edx, txt ", "
stdcall NumToStr, [timebin], ntsDec or ntsSigned
stdcall StrCat, edx, eax
stdcall StrDel, eax
stdcall StrCat, edx, <txt 13, 10>
stdcall FileWriteString, [STDOUT], edx
stdcall StrDel, edx
inc ebx
cmp ebx, MAX_ARRAY_SIZE
jbe .size_loop
FinalizeAll
stdcall TerminateAll, 0
Если данные упорядочены, то зачастую есть более быстрый способ поиска, чем деление данных пополам. Т.е. ищем среди наибольших членов (или наименьших).
Поскольку данные упорядочены, то вероятность нахождения нужного элемента может сильно отличаться от равномерной. Построим пример, в котором линейный поиск (т.е. поиск по порядку: 1,2,3, ...)
Пусть в некоем упорядоченном множестве вероятность того, что первый член (элемент) есть искомый равна 50%.
Описание: «голова змеи» и её «хвост»: голова — 1й член, хвост — все остальные.
«голова змеи» <-> 50% вероятности
«хвост» <-> 50% вероятности
Перейдём к следующему элементу, отбросив рассмотренный первый. Повторим предыдущие действия, т.ч. опять будет «голова змеи» и её «хвост», и опять вероятности 1/2 и 1/2.
Итого получим бесконечный ряд вероятностей 1/2 + 1/4 + 1/8 + ..., его сумма равна 1.
В 50% случаев хватит первого члена, в 75% — первых двух, и т.д.
Понятно, что вероятности могут спадать и быстрее.
Таким образом, есть бесконечное количество случаев, в которых линейный поиск выгоднее. И количество элементов также может быть любым (от 1 до +∞).
Бинарный поиск обычно выгоднее. В частных случаях может быть что угодно.
В данном случае получается почти бинарный поиск с делением множества пополам на равновероятные части.
Ричард тогда работал на интернет-гиганта Hooli— шутка для знающих русский язык? Доменное имя hooli.com работает.
Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного