Комментарии 54
Неужели написать бенчмарк для этого примера кода дольше, чем статью?
Похоже, вы эффективно используете время и знаете, что можно гораздо быстрее написать комментарий, если перед этим не читать статью :) Иначе вы прочитали бы прямо в ней, почему я не пишу бенчмарки.
Я не специалист в них, поэтому могу не учесть множество факторов и прийти к ошибочным выводам. Например, я понятия не имею, на каком железе должен был запускаться код Ричарда — и не понимаю, насколько в данном случае это может повлиять на результат.
Я не специалист в них, поэтому могу не учесть множество факторов и прийти к ошибочным выводам. Например, я понятия не имею, на каком железе должен был запускаться код Ричарда — и не понимаю, насколько в данном случае это может повлиять на результат.
Так если вы не пишете и не проектируете код – вам не нужен и результат бенчмарка :-)
Мне нужно знать, был ли прав мой любимый персонаж!
(вообще код немного пишу, но не в продакшн, а для себя — на моих масштабах можно всё делать линейно и не париться, да :))
(вообще код немного пишу, но не в продакшн, а для себя — на моих масштабах можно всё делать линейно и не париться, да :))
Он был не прав. Рассмотрим два случая:
1) Бинпоиск быстрее. Он не прав
2) Линейный поиск быстрее. Но он быстрее совсем не значительно, но каждый программист, который это читает задается вопросом «да что тут вообще происходит, господи». Даже если эта секция действительно супер-мега-очень критическая и этот мили-выигрыш решает, нужно написать комментарий об этом. Желательно капслоком. Вообще на всех подозрительных оптимизациях так делать необходимо, иначе ущерба больше, чем пользы
1) Бинпоиск быстрее. Он не прав
2) Линейный поиск быстрее. Но он быстрее совсем не значительно, но каждый программист, который это читает задается вопросом «да что тут вообще происходит, господи». Даже если эта секция действительно супер-мега-очень критическая и этот мили-выигрыш решает, нужно написать комментарий об этом. Желательно капслоком. Вообще на всех подозрительных оптимизациях так делать необходимо, иначе ущерба больше, чем пользы
Пожалуй, соглашусь. Меня смутила единодушность комментаторов на Reddit — подумал, может, на такое смотрят уже без вопроса «да что тут вообще происходит», а я всё пропустил. Но насколько вижу по Хабру, по-прежнему с вопросом.
Вы не учитываете, что комментировать надо неочевидные вещи. А линейный поиск — штука куда более очевидная, чем бинарный. Иначе говоря, любой человек поймет, что этот кусок кода делает, и с этой точки зрения линейный поиск предпочтительнее даже если не дает выигрыша в скорости. Мы же не знаем какую задачу он решал и что было в приоритете — эффективность или сопровождаемость.
И комментарий нужен если человек действительно задумывался о таких тонкостях, а не просто влепил первый попавшийся алгоритм, успешно решающий задачу. Например, «требований к скорости нет, так что линейный поиск использован ради сопровождаемости» или «на такой-то машине этот способ работает на 0.1% лучше бинарного».
И комментарий нужен если человек действительно задумывался о таких тонкостях, а не просто влепил первый попавшийся алгоритм, успешно решающий задачу. Например, «требований к скорости нет, так что линейный поиск использован ради сопровождаемости» или «на такой-то машине этот способ работает на 0.1% лучше бинарного».
Главная проблема таких примеров — в них ищутся инты. Поиск интов в контейнере не такая частая задача (хотя, конечно, встречается). Гораздо чаще приходится искать строчки или какие-то пользовательские типы, которые довольно быстро перестают влезать в кеш или вообще обращаются к выделенной где-то памяти. И тут бин поиск начинает выигрывать довольно быстро.
Код ошибочный, не работает на пустом списке.
Один из примеров, где линейный поиск в отсортированном массиве оказался по факту в среднем быстрее бинарного, мне встретился в APE-кодеке, а именно, в диапазонном декодере (комментарий в строке 447 неверен). Фишка в том, что оценка «N/2 просмотренных элементов» для среднего времени выполнения линейного поиска основана на предположении, что входные данные таковы, что каждый из элементов массива имеет одинаковую вероятность быть найденным. В APE-кодеке это не так. Там массив из 22 элементов, но начальный нужен с вероятностью более 30%, а один из шести начальных — с вероятностью более 80%, поэтому замена линейного поиска на двоичный замедляет кодек.
Зависит, наверное, от размеров и способа доступа к элементам.
Но если те же инты в векторе — то я бы до ~50 элементов, а то и больше (конкретное решение надо принимать по результатам бенчей в наиболее вероятном окружении) остался бы в линейном алгоритме.
(у линейного поиска есть ещё преимущество в этом случае: ему совсем не критично условие сортированности массива входных данных).
(в примере статьи вообще странное… Вроде список (list), а доступ при этом по индексу. Если там в самом деле список (не вектор), то в нём самом Get(idx) уже легко может подразумевать линейный поиск где-то под капотом. И в этом случае (раз уж всё изначально так) проще взять next() вместо get(idx), и просто добавить своих критериев.
Я утрирую, но что если для APE-кодека известна эвристика, скажем, что «вероятность встретить искомый элемент в первой трети подмассива суммарной вероятности встретить во второй и третей третях»? Если так, то можно заставить бинарный поис разбивать подмассив не «пополам» а на «1:2», что должно как минимум улучшить производительность относительно стандартного бинарного поиска.
Идея в том что выше мы пофиксим бинарный поиск для APE-кодека, чтобы он всегда разбивал подмассив на равновероятные части, а не равные по длине.
Идея в том что выше мы пофиксим бинарный поиск для APE-кодека, чтобы он всегда разбивал подмассив на равновероятные части, а не равные по длине.
Если вам известно распределение вероятностей на конечном (и таком малом) числе элементов, то ничто не мешает написать специальный алгоритм, который обгонит любой алгоритм общего вида. И к слову, O-оценки для алгоритмов делаются для случая наихудших входных данных, т.е. вообще без предположений на распределение.
ага, комментрий klirichek как раз о том, что известно что-то о распределении вероятностей.
. (Уже ответили ниже)
Предполагая случай наихудших входных данных, мы неявно вводим ограничения на распределение.
Нет. Worst-case complexity работает для любого распределения. Average-case complexity — не для любого. Если вам непонятно почему — повторите определение O-большого.
Worst-case complexity работает для любого распределения.— это как? Наихудший случай есть зачастую специально подобранный единичный пример.
O-оценка — это оценка сверху. Если вы знаете что алгоритм работает быстрее C*n*log(n) для самых худших входных данных размера n, то вы знаете что алгоритм будет работать быстрее C*n*log(n) для любых данных размера n с любым распределением. При использовании Average-case compexity такого утверждения вы сделать не можете.
Вообще, по коду много других вопросов возникает. element не обязан быть совместим по типам с содержимым сортированного листа. И для них вполне может быть определён только equals, а не compare. Собственнло, и compare тоже может быть таким, что не совпадает с compare по которому список отсортирован.
Бинарный поиск на современных процессорах выигрывает уже на сотнях элементов. Это для простых типов. При увеличении размера элемента или увеличении сложности функции сравнения, бинарный поиск становится еще эффективнее. В общем случае бинарный поиск выгоднее уже на десятках элементов.
А можно причинами поинтересоваться?
И что такое современные процессоры, какой архитектуры?
Что-то я не уверен, что на десятках элементов выгоднее довольно приличное количество переходов вместо линейного прохода.
Но это чисто теоретически, а вы, видимо, знаете практику хотя бы для 64-битных интов.
Имеются ввиду процессоры, обладающие кэшами различного уровня и конвейером.
Линейный доступ выигрывает из-за эффективного использования кэша за счет префетчинга и из-за отсутствия сбоев конвеера за счет эффективного предсказания переходов. Но если идет поиск постоянно в одном наборе данных небольшого размера, то скорее всего он и так будет закэширован.
Если речь идет о простых типах, тех же интах, то, как я написал, тут выигрыш у бинарного поиска начинается где то на сотнях элементов. Логарифм 100 — будет в районе 7, т.е. сравнений будет как минимум раз в 10 меньше при бинарном поиске, для 200 меньше уже в 20 раз и т.д. Т.е. линейный поиск должен быть во столько раз эффективнее на одно сравнение чтобы выигрывать. Ну видимо где то в этом районе сейчас граница и проходит. Потому что по опыту получаются именно такие размерности, когда бинарный поиск начинает выигрывать.
Если же говорить о более сложных типах — строках или каких то классах, имеющих свою сложную функцию сравнения, то само время выполнения функции сравнения становится уже сравнимым с оверхедом от отсутствия кэширования/сбоев конвейера и эффективность линейного поиска на одну операцию сравнения становится выше уже не в десятки, а в несколько раз или даже просто на несколько процентов. Поэтому в этом случае граница и смещается в область десятков элементов, а не сотен.
Линейный доступ выигрывает из-за эффективного использования кэша за счет префетчинга и из-за отсутствия сбоев конвеера за счет эффективного предсказания переходов. Но если идет поиск постоянно в одном наборе данных небольшого размера, то скорее всего он и так будет закэширован.
Если речь идет о простых типах, тех же интах, то, как я написал, тут выигрыш у бинарного поиска начинается где то на сотнях элементов. Логарифм 100 — будет в районе 7, т.е. сравнений будет как минимум раз в 10 меньше при бинарном поиске, для 200 меньше уже в 20 раз и т.д. Т.е. линейный поиск должен быть во столько раз эффективнее на одно сравнение чтобы выигрывать. Ну видимо где то в этом районе сейчас граница и проходит. Потому что по опыту получаются именно такие размерности, когда бинарный поиск начинает выигрывать.
Если же говорить о более сложных типах — строках или каких то классах, имеющих свою сложную функцию сравнения, то само время выполнения функции сравнения становится уже сравнимым с оверхедом от отсутствия кэширования/сбоев конвейера и эффективность линейного поиска на одну операцию сравнения становится выше уже не в десятки, а в несколько раз или даже просто на несколько процентов. Поэтому в этом случае граница и смещается в область десятков элементов, а не сотен.
Вообще, все эти оценки производительности (О-нотация) асимптотические. То есть, это оценка производительности, когда число итерации стремиться к бесконечности.
А для малых массивов, линейный поиск будет категорично быстрее. Просто из за того что у алгоритма банально меньше инструкции.
Кстати, то же самое и даже в большей мере верно и для сортировки. Для маленьких массивов сортировка пузырьком быстрее из за простотой кода. Это известный факт, который используют например чтобы ускорить другие методы сортировки, используя метод пузырьком когда размер сортируемого отрезка меньше некоторой границы.
Для объектных языков высокого уровня ( java ) понятие «количество инструкций» бессмысленно.
Там операция а+б может занимать, и часто занимает, больше инструкций, чем операция «сходи попить кофе».
Если же говорить о языках с вменяемыми трансляторами, не испорченными параноидальными видениями миражей NULL pointer в пустыне Сахара, являющихся адептам секты «священного кода» в полночь, то операция shift right уменьшающая скалярное значение в два раза занимает ровно 6 инструкций процессора и ни одной больше, операция сложения занимает 3. То есть если только выбор не ограничен 2-мя соседними значениями, то бинарный поиск уже выиграл.
Там операция а+б может занимать, и часто занимает, больше инструкций, чем операция «сходи попить кофе».
Если же говорить о языках с вменяемыми трансляторами, не испорченными параноидальными видениями миражей 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 по выполнению машинных инструкций.
Если что — то не соответствует, буду благодарен и с удовольствием отвечу на любые нарекания или пожелания улучшений.
— test.c
#include <stdio.h>
int main()
{
int i = 8;
i = i + 8;
i = i >> 1;
}
—
Транслируете в выполнимый в Вашем любимом трансляторе.
Стартуете под трассировкой.
Включаете опцию «трассировать инструкции машинного кода»
И читаете выполненные операции, пошагово.
Открываете спецификации компании Intel по выполнению машинных инструкций.
Если что — то не соответствует, буду благодарен и с удовольствием отвечу на любые нарекания или пожелания улучшений.
Открываете спецификации компании Intel по выполнению машинных инструкций.Процессоры делает не только Intel.
Влияние имени производителя на количество булевых операций на чипе для выполнения инструкции не больше, чем влияние имени производителя на количество колес автомобиля.
Интел в данном случае приведен по единственной причине, в отличие от множества других производителей фирма опубликовала и сделала доступным для всех техническую документацию по данному вопросу.
Интел в данном случае приведен по единственной причине, в отличие от множества других производителей фирма опубликовала и сделала доступным для всех техническую документацию по данному вопросу.
> Самое простое, это проверить. Пишете в любимом редакторе следующий код на С
Взял, проверил. Разумеется, данный код будет работать только без оптимизаций — оптимизация выкинет всю работу с i нафиг; надо оформлять тогда во что-то другое, не в main, и чтобы результат i возвращался. И вижу:
Как видим, и сложение, и сдвиг заняли ровно 1 инструкцию.
Хорошо, делаем отдельной функцией с оптимизацией:
Получаем:
Снова одна инструкция.
Так что у вас за компилятор такой безумный? У меня обычный GCC 7.4.0.
Или вы под «инструкциями» имели в виду микрооперации после разложения в тот внутренний RISC, на котором работает x86? Всё равно не сходится, неоткуда взять 6 микроопераций на сдвиг.
Взял, проверил. Разумеется, данный код будет работать только без оптимизаций — оптимизация выкинет всю работу с 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 выполняются за такт или меньше. Считать такты не зная ни языка ассемблера, ни устройство современных процессоров — глупо.
Операции на регистрах на современных процессорах с системой команд AMD64 выполняются за такт или меньше. Считать такты не зная ни языка ассемблера, ни устройство современных процессоров — глупо.
А может все проще, и потом окажется, что там LinkedList был. Бинарный поиск получится O(n log n).
Достаточно известный пример — выбор простого числа для размера хэш-таблицы.
Как это сделали в MS.
Суть в том, что накладные расходы (инициализация таблицы) пропорциональны размеру найденного числа. Так что для больших чисел не так важно, нашли линейно или бинпоиском, а для маленьких — линейный будет сильно быстрее.
То есть может оказаться, что линейный поиск в среднем медленнее, но в силу каких-то обстоятельств будет разумнее в использовании. Например, потому что лучше теряется в каких-то дополнительных расходах и меньше портит частные случаи.
Как это сделали в MS.
Суть в том, что накладные расходы (инициализация таблицы) пропорциональны размеру найденного числа. Так что для больших чисел не так важно, нашли линейно или бинпоиском, а для маленьких — линейный будет сильно быстрее.
То есть может оказаться, что линейный поиск в среднем медленнее, но в силу каких-то обстоятельств будет разумнее в использовании. Например, потому что лучше теряется в каких-то дополнительных расходах и меньше портит частные случаи.
Непонятно, с чем сравнивают element.equals. Ведь там всего один аргумент.
Эм, сравнивается element и sortedList.get(index), разве нет?
Видимо да. Это ваша Java странная для постороннего взгляда. В любом другое языке нагляднее было бы (element==sortedList.get(index))
Похожий подход применяется, например в имплементации структуры данных RoaringBitmap на Java, когда в отсортированном массиве поиск начинают сначала бинарным поиском, а потом, когда все элементы попадают в кеш-линию процессора, просто линейно ищут: github.com/RoaringBitmap/RoaringBitmap/blob/master/RoaringBitmap/src/main/java/org/roaringbitmap/Util.java#L373
Сделал несколько измерений, по моим тестам для поиска в массиве int быстрее линейный поиск для размера массива до 40 элементов, дальше выигрывает бинарный. Впрочем, отставание бинарного поиска не более чем в 2 раза, поэтому можно не заморачиваться оптимизацией маленьких векторов.
Что интересно, эвристика (по вашей ссылке) для отсортированного вектора
скорее вредит производительности линейного поиска: цикл только с проверкой на равенство работает быстрее, а добавляя эту эвристику, получаем на маленьких векторах результаты, близкие к бинарному поиску.
Что интересно, эвристика (по вашей ссылке) для отсортированного вектора
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 повторении)
Код (FASM/FreshLib)
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 до +∞).
Бинарный поиск обычно выгоднее. В частных случаях может быть что угодно.
В данном случае получается почти бинарный поиск с делением множества пополам на равновероятные части.
Если данные упорядочены, то зачастую есть более быстрый способ поиска, чем деление данных пополам. Т.е. ищем среди наибольших членов (или наименьших).
Поскольку данные упорядочены, то вероятность нахождения нужного элемента может сильно отличаться от равномерной. Построим пример, в котором линейный поиск (т.е. поиск по порядку: 1,2,3, ...)
Пусть в некоем упорядоченном множестве вероятность того, что первый член (элемент) есть искомый равна 50%.
Описание: «голова змеи» и её «хвост»: голова — 1й член, хвост — все остальные.
«голова змеи» <-> 50% вероятности
«хвост» <-> 50% вероятности
Перейдём к следующему элементу, отбросив рассмотренный первый. Повторим предыдущие действия, т.ч. опять будет «голова змеи» и её «хвост», и опять вероятности 1/2 и 1/2.
Итого получим бесконечный ряд вероятностей 1/2 + 1/4 + 1/8 + ..., его сумма равна 1.
В 50% случаев хватит первого члена, в 75% — первых двух, и т.д.
Понятно, что вероятности могут спадать и быстрее.
Таким образом, есть бесконечное количество случаев, в которых линейный поиск выгоднее. И количество элементов также может быть любым (от 1 до +∞).
Бинарный поиск обычно выгоднее. В частных случаях может быть что угодно.
В данном случае получается почти бинарный поиск с делением множества пополам на равновероятные части.
Ричард тогда работал на интернет-гиганта Hooli— шутка для знающих русский язык? Доменное имя hooli.com работает.
Think of RandomAccess
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного