company_banner

Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного


    Думаю, на Хабре есть любители сериала «Кремниевая долина» (Silicon Valley). На этой неделе там впервые за все шесть сезонов крупно показали код — разумеется, сразу хочется обсудить его здесь.


    Желая унизить главного героя Ричарда Хендрикса, его бывший начальник показывает на совещании фрагмент его старого кода. Там к уже отсортированным данным применён линейный поиск — так что задача будет выполнена, но выглядит это очень неэффективно.


    Сам Ричард не спорит с тем, что код плохой. Однако среди зрителей сериала у его решения внезапно нашлись защитники, и теперь мне интересно, что об их позиции думает Хабр.


    Известный нам фрагмент кода Ричарда выглядит так:


    int index = 0;
    while (!element.equals(sortedList.get(index))
        && sortedList.size() > ++index);
    return index < sortedList.size() ? index : -1;

    Здесь линейный поиск обращается поочерёдно к каждому элементу какого-то уже отсортированного списка, пока не доберётся до нужного. Как правило, на сортированных данных предпочитают бинарный поиск, который каждый раз делит множество пополам, отбрасывая неподошедшую половину целиком (потому что с ростом объёма данных количество итераций у линейного возрастает куда быстрее, чем у бинарного). Но в сабреддите /r/SiliconValleyHBO появился следующий комментарий:


    «Хочу немного позанудствовать и укажу, что "ошибка" Ричарда в использовании линейного поиска вместо бинарного по сортированным данным на самом деле в очень многих случаях оказывается более производительной. При гигантских датасетах (думаю, порог на миллионах элементов) бинарный поиск быстрее. Но в целом, если ваш датасет не гигантский, линейный поиск будет лучше кэшироваться процессором, лучше подходит для branch predictor, а ещё ваш алгоритм может быть векторизован. Линейный поиск требует больше итераций, но каждая из них безумно быстрее, чем итерация бинарного поиска. Это контринтуитивно и противоречит всему, чему вас учили в вузе, но это так.

    Вот этот доклад очень интересный и показывает некоторые поразительные результаты реальных замеров производительности».

    И другие участники треда поддержали комментатора: да, это в теории все итерации равноценны, а на реальном железе с реальными оптимизациями всё совсем иначе. Мол, создатель сериала Майк Джадж работал в Долине ещё в 80-х, когда все эти L1-кэши и branch prediction ещё особо не заявили о себе, так что поведение CPU было куда ближе к идеальной модели — вот в сериале такой пример и приведён.


    Для меня, как и говорится в комментарии, это всё звучит контринтуитивно, но стало интересно разобраться, мог ли Ричард быть прав. Конечно, мешает, что в сериале дан не весь контекст: например, мы понятия не имеем, по какому объёму данных он итерировался. С одной стороны, Ричард тогда работал на интернет-гиганта Hooli, где наверняка приходится иметь дело с миллионами записей, но с другой, это был его первый рабочий день, и его могли не бросать сразу на миллионы. Поставим вопрос так: даже если для большинства задач в Hooli бинарный поиск явно будет лучше, вероятен ли вариант, что для своих условий Ричард принял правильное решение, и другие персонажи напрасно над ним смеются, не зная контекста?


    Чтобы понять, открыл доклад, на который ссылались на Reddit. Как и обещали, он оказался интересным (неудивительно, учитывая, что это доклад Андрея Александреску), но посмотрев часть и прокликав остальное, я не увидел там сравнительных замеров бинарного и линейного поиска.


    Зато вспомнил, что на нашей конференции DotNext тот же Александреску тоже говорил о производительности. Открыл текстовую версию его доклада, которую мы сделали для Хабра, и поискал по слову «линейный». Оказалось, в числе прочего там как раз приведён пример любопытного сценария, в котором этот поиск окажется куда эффективнее бинарного (поиск совпадающих элементов двух множеств в том случае, когда эти множества идентичны) — но это очень конкретный случай, по такому не сделать общий вывод «линейный поиск недооценён».


    Погуглил, что современные интернеты говорят по этому поводу — но в основном нашёл ответы на Stack Overflow, где просто пишут «используйте бинарный, итераций меньше». Нашлись и случаи, где пытались побенчмаркать, но тоже не выглядящие для меня очень убедительными.


    Тут, конечно, напрашивается вариант «надо побенчмаркать лично, чтобы увидеть всё самому на реальном железе».


    Но если за все мои посещения DotNext я чему-то и научился у двух разбирающихся в перформансе Андреев (Александреску и Акиньшина), так это осознанию того, как часто люди бенчмаркают неправильно и сколько всего не учитывают. Поэтому доверие к случайным интернет-постам с бенчмарками у меня невысокое, а к себе ещё ниже.


    К счастью, на Хабре есть люди, понимающие куда больше меня (например, тот же Андрей DreamWalker Акиньшин, который про бенчмаркинг целую книгу написал). Поэтому, если вы разбираетесь в теме — расскажите, пожалуйста, в комментариях, как всё на самом деле. До какого размера данных линейный подход всё ещё может быть хорошим выбором? Насколько вероятно, что Ричард сделал всё правильно, даже если потом он сам не готов это отстаивать?


    А если сведущих комментаторов не найдётся — придётся мне на следующем DotNext приковать Акиньшина к батарее и заставить бенчмаркать.

    JUG Ru Group
    435.32
    Конференции для программистов и сочувствующих. 18+
    Share post

    Comments 48

      +23

      Неужели написать бенчмарк для этого примера кода дольше, чем статью?

        –3
        Похоже, вы эффективно используете время и знаете, что можно гораздо быстрее написать комментарий, если перед этим не читать статью :) Иначе вы прочитали бы прямо в ней, почему я не пишу бенчмарки.

        Я не специалист в них, поэтому могу не учесть множество факторов и прийти к ошибочным выводам. Например, я понятия не имею, на каком железе должен был запускаться код Ричарда — и не понимаю, насколько в данном случае это может повлиять на результат.
          +8

          Так если вы не пишете и не проектируете код – вам не нужен и результат бенчмарка :-)

            +4
            Мне нужно знать, был ли прав мой любимый персонаж!

            (вообще код немного пишу, но не в продакшн, а для себя — на моих масштабах можно всё делать линейно и не париться, да :))
              +3
              Он был не прав. Рассмотрим два случая:
              1) Бинпоиск быстрее. Он не прав
              2) Линейный поиск быстрее. Но он быстрее совсем не значительно, но каждый программист, который это читает задается вопросом «да что тут вообще происходит, господи». Даже если эта секция действительно супер-мега-очень критическая и этот мили-выигрыш решает, нужно написать комментарий об этом. Желательно капслоком. Вообще на всех подозрительных оптимизациях так делать необходимо, иначе ущерба больше, чем пользы
                +1
                Пожалуй, соглашусь. Меня смутила единодушность комментаторов на Reddit — подумал, может, на такое смотрят уже без вопроса «да что тут вообще происходит», а я всё пропустил. Но насколько вижу по Хабру, по-прежнему с вопросом.
                  0
                  Вы не учитываете, что комментировать надо неочевидные вещи. А линейный поиск — штука куда более очевидная, чем бинарный. Иначе говоря, любой человек поймет, что этот кусок кода делает, и с этой точки зрения линейный поиск предпочтительнее даже если не дает выигрыша в скорости. Мы же не знаем какую задачу он решал и что было в приоритете — эффективность или сопровождаемость.
                  И комментарий нужен если человек действительно задумывался о таких тонкостях, а не просто влепил первый попавшийся алгоритм, успешно решающий задачу. Например, «требований к скорости нет, так что линейный поиск использован ради сопровождаемости» или «на такой-то машине этот способ работает на 0.1% лучше бинарного».
          +16
          Главная проблема таких примеров — в них ищутся инты. Поиск интов в контейнере не такая частая задача (хотя, конечно, встречается). Гораздо чаще приходится искать строчки или какие-то пользовательские типы, которые довольно быстро перестают влезать в кеш или вообще обращаются к выделенной где-то памяти. И тут бин поиск начинает выигрывать довольно быстро.
            +2
            Код ошибочный, не работает на пустом списке.
              +2
              Мы же не знаем контекста — может, там перед этим проверка на пустоту?) Ну, в любом случае, высмеивали в сериале не это.
                0
                Если get может возвращать, например, nil и equals может работать с нулевым элемнтом, то будет работать и с пустым списком. Но это так, попытка защитить код из сериала.
                +13
                Один из примеров, где линейный поиск в отсортированном массиве оказался по факту в среднем быстрее бинарного, мне встретился в APE-кодеке, а именно, в диапазонном декодере (комментарий в строке 447 неверен). Фишка в том, что оценка «N/2 просмотренных элементов» для среднего времени выполнения линейного поиска основана на предположении, что входные данные таковы, что каждый из элементов массива имеет одинаковую вероятность быть найденным. В APE-кодеке это не так. Там массив из 22 элементов, но начальный нужен с вероятностью более 30%, а один из шести начальных — с вероятностью более 80%, поэтому замена линейного поиска на двоичный замедляет кодек.
                  0

                  Зависит, наверное, от размеров и способа доступа к элементам.
                  Но если те же инты в векторе — то я бы до ~50 элементов, а то и больше (конкретное решение надо принимать по результатам бенчей в наиболее вероятном окружении) остался бы в линейном алгоритме.
                  (у линейного поиска есть ещё преимущество в этом случае: ему совсем не критично условие сортированности массива входных данных).


                  (в примере статьи вообще странное… Вроде список (list), а доступ при этом по индексу. Если там в самом деле список (не вектор), то в нём самом Get(idx) уже легко может подразумевать линейный поиск где-то под капотом. И в этом случае (раз уж всё изначально так) проще взять next() вместо get(idx), и просто добавить своих критериев.

                    +1
                    Это джава. С большой вероятностью там ArrayList.
                    +2
                    Я утрирую, но что если для APE-кодека известна эвристика, скажем, что «вероятность встретить искомый элемент в первой трети подмассива суммарной вероятности встретить во второй и третей третях»? Если так, то можно заставить бинарный поис разбивать подмассив не «пополам» а на «1:2», что должно как минимум улучшить производительность относительно стандартного бинарного поиска.

                    Идея в том что выше мы пофиксим бинарный поиск для APE-кодека, чтобы он всегда разбивал подмассив на равновероятные части, а не равные по длине.
                      +2
                      Если вам известно распределение вероятностей на конечном (и таком малом) числе элементов, то ничто не мешает написать специальный алгоритм, который обгонит любой алгоритм общего вида. И к слову, O-оценки для алгоритмов делаются для случая наихудших входных данных, т.е. вообще без предположений на распределение.
                        0
                        ага, комментрий klirichek как раз о том, что известно что-то о распределении вероятностей.
                          0

                          . (Уже ответили ниже)

                            0
                            Предполагая случай наихудших входных данных, мы неявно вводим ограничения на распределение.
                              0
                              Нет. Worst-case complexity работает для любого распределения. Average-case complexity — не для любого. Если вам непонятно почему — повторите определение O-большого.
                                0
                                Worst-case complexity работает для любого распределения.
                                — это как? Наихудший случай есть зачастую специально подобранный единичный пример.
                                  0
                                  O-оценка — это оценка сверху. Если вы знаете что алгоритм работает быстрее C*n*log(n) для самых худших входных данных размера n, то вы знаете что алгоритм будет работать быстрее C*n*log(n) для любых данных размера n с любым распределением. При использовании Average-case compexity такого утверждения вы сделать не можете.
                          +1

                          Вообще, по коду много других вопросов возникает. element не обязан быть совместим по типам с содержимым сортированного листа. И для них вполне может быть определён только equals, а не compare. Собственнло, и compare тоже может быть таким, что не совпадает с compare по которому список отсортирован.

                            0
                            Бинарный поиск на современных процессорах выигрывает уже на сотнях элементов. Это для простых типов. При увеличении размера элемента или увеличении сложности функции сравнения, бинарный поиск становится еще эффективнее. В общем случае бинарный поиск выгоднее уже на десятках элементов.
                              0

                              А можно причинами поинтересоваться?
                              И что такое современные процессоры, какой архитектуры?
                              Что-то я не уверен, что на десятках элементов выгоднее довольно приличное количество переходов вместо линейного прохода.
                              Но это чисто теоретически, а вы, видимо, знаете практику хотя бы для 64-битных интов.

                                0
                                Имеются ввиду процессоры, обладающие кэшами различного уровня и конвейером.
                                Линейный доступ выигрывает из-за эффективного использования кэша за счет префетчинга и из-за отсутствия сбоев конвеера за счет эффективного предсказания переходов. Но если идет поиск постоянно в одном наборе данных небольшого размера, то скорее всего он и так будет закэширован.
                                Если речь идет о простых типах, тех же интах, то, как я написал, тут выигрыш у бинарного поиска начинается где то на сотнях элементов. Логарифм 100 — будет в районе 7, т.е. сравнений будет как минимум раз в 10 меньше при бинарном поиске, для 200 меньше уже в 20 раз и т.д. Т.е. линейный поиск должен быть во столько раз эффективнее на одно сравнение чтобы выигрывать. Ну видимо где то в этом районе сейчас граница и проходит. Потому что по опыту получаются именно такие размерности, когда бинарный поиск начинает выигрывать.
                                Если же говорить о более сложных типах — строках или каких то классах, имеющих свою сложную функцию сравнения, то само время выполнения функции сравнения становится уже сравнимым с оверхедом от отсутствия кэширования/сбоев конвейера и эффективность линейного поиска на одну операцию сравнения становится выше уже не в десятки, а в несколько раз или даже просто на несколько процентов. Поэтому в этом случае граница и смещается в область десятков элементов, а не сотен.
                                  +1

                                  Я в курсе теории и того, что логарифм растёт намного медленнее, чем линейная функция.


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

                              +1

                              Вообще, все эти оценки производительности (О-нотация) асимптотические. То есть, это оценка производительности, когда число итерации стремиться к бесконечности.


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


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

                                0
                                Для объектных языков высокого уровня ( java ) понятие «количество инструкций» бессмысленно.
                                Там операция а+б может занимать, и часто занимает, больше инструкций, чем операция «сходи попить кофе».
                                Если же говорить о языках с вменяемыми трансляторами, не испорченными параноидальными видениями миражей NULL pointer в пустыне Сахара, являющихся адептам секты «священного кода» в полночь, то операция shift right уменьшающая скалярное значение в два раза занимает ровно 6 инструкций процессора и ни одной больше, операция сложения занимает 3. То есть если только выбор не ограничен 2-мя соседними значениями, то бинарный поиск уже выиграл.
                                  +1
                                  операция shift right уменьшающая скалярное значение в два раза занимает ровно 6 инструкций процессора и ни одной больше, операция сложения занимает 3.
                                  — это откуда?
                                    0
                                    Самое простое, это проверить. Пишете в любимом редакторе следующий код на С

                                    — test.c
                                    #include <stdio.h>

                                    int main()
                                    {
                                    int i = 8;
                                    i = i + 8;
                                    i = i >> 1;
                                    }

                                    Транслируете в выполнимый в Вашем любимом трансляторе.
                                    Стартуете под трассировкой.
                                    Включаете опцию «трассировать инструкции машинного кода»
                                    И читаете выполненные операции, пошагово.
                                    Открываете спецификации компании Intel по выполнению машинных инструкций.
                                    Если что — то не соответствует, буду благодарен и с удовольствием отвечу на любые нарекания или пожелания улучшений.
                                      0
                                      Открываете спецификации компании Intel по выполнению машинных инструкций.
                                      Процессоры делает не только Intel.
                                        0
                                        Влияние имени производителя на количество булевых операций на чипе для выполнения инструкции не больше, чем влияние имени производителя на количество колес автомобиля.
                                        Интел в данном случае приведен по единственной причине, в отличие от множества других производителей фирма опубликовала и сделала доступным для всех техническую документацию по данному вопросу.
                                0

                                А может все проще, и потом окажется, что там LinkedList был. Бинарный поиск получится O(n log n).

                                  +1
                                  В таком случае list.get(index) работает за O(n) и обсуждаемый алгоритм за O(n^2).
                                  +1
                                  Достаточно известный пример — выбор простого числа для размера хэш-таблицы.
                                  Как это сделали в MS.
                                  Суть в том, что накладные расходы (инициализация таблицы) пропорциональны размеру найденного числа. Так что для больших чисел не так важно, нашли линейно или бинпоиском, а для маленьких — линейный будет сильно быстрее.
                                  То есть может оказаться, что линейный поиск в среднем медленнее, но в силу каких-то обстоятельств будет разумнее в использовании. Например, потому что лучше теряется в каких-то дополнительных расходах и меньше портит частные случаи.
                                    0
                                    Непонятно, с чем сравнивают element.equals. Ведь там всего один аргумент.
                                      +1

                                      Эм, сравнивается element и sortedList.get(index), разве нет?

                                        0
                                        Видимо да. Это ваша Java странная для постороннего взгляда. В любом другое языке нагляднее было бы (element==sortedList.get(index))
                                          0

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

                                            0
                                            Нет, это просто чистое ООП.

                                            В любом другое языке нагляднее было бы (element==sortedList.get(index))
                                            — нет, не в любом. Пример: Eiffel.
                                      0
                                      Похожий подход применяется, например в имплементации структуры данных RoaringBitmap на Java, когда в отсортированном массиве поиск начинают сначала бинарным поиском, а потом, когда все элементы попадают в кеш-линию процессора, просто линейно ищут: github.com/RoaringBitmap/RoaringBitmap/blob/master/RoaringBitmap/src/main/java/org/roaringbitmap/Util.java#L373
                                        0
                                        Сделал несколько измерений, по моим тестам для поиска в массиве 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
                                          0
                                          Я бы наверное не использовал rand(), а использовал худший вариант для поиска. Например просто последний элемент массива. В таком случае возможно линейный поиск начнёт проигрывать раньше.
                                        +1
                                        Вряд ли Ричард писал этот код в первый день (на новом рабочем месте, в стрессовом состоянии) исходя из логики преимущества векторизации и предсказания ветвления. Скорее всего он получил большую задачу, одним из шагов которой был поиск. Ричард написал простенький поиск — просто чтобы он работал хотя бы как-то и служил «заглушкой» на время написания остальной части задачи. Это нормальная практика, так вполне допустимо делать.

                                        Само-собой, код должен был заменён на нормальный перед сдачей на ревью или, в крайнем случае, отклонён ревьювером с просьбой заменить на нормальный. Если этот код попал в продакшн — то это ошибка не Ричарда, а сеньйоров\тимлида\менеджера компании Хули.
                                          +1

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


                                          Выглядит примерно так: (время по Y в мкс за 1 000 000 повторении)
                                          image


                                          Код (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
                                            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 работает.
                                              +1

                                              Это и есть бинарный поиск. Кто сказал, что деление должно быть в середине? Нет, деление должно быть на две части. А в середине или нет, не имеет значения.

                                            Only users with full accounts can post comments. Log in, please.