Упрощаем бинарный поиск в Excel — реализация Double VLOOKUP Trick с помощью UDF

    Добавлю в копилку статей Хабра о Бинарном поиске еще одну. Речь пойдет о кастомной реализации, может быть полезно всем, кто часто использует в работе ВПР для сравнения больших списков или для поиска данных в больших массивах.

    Предыстория


    Все началось с того, что я открыл для себя т.н. Double-TRUE VLOOKUP trick (трюк с двойным использованием ВПР и ИСТИНА в 4-м параметре). Развернутое описание алгоритма можно найти в статье Charles Williams «Why 2 VLOOKUPS are better than 1 VLOOKUP» (в конце статьи).

    Поняв принцип работы и открыв для себя, что этот подход может быть в тысячи раз быстрее обычного линейного поиска (ВПР с 4-м параметром ЛОЖЬ), я начал продумывать варианты раскрыть его возможности. В ходе реализации получилось несколько годных инструментов для контекстной рекламы, один из которых я еще продолжаю улучшать, и уже посвятил проекту пару статей на Хабре. Чтиво рекомендуется SEO-специалистам и специалистам по контекстной рекламе (сразу оговорюсь, по ссылкам в статьях уже устаревшие версии, последняя версия условно 6.0, ссылки на скачивание всех версий, включая самую свежую, будут в конце этой статьи):

    » Анализ больших семантических ядер, или «Робот-распознаватель»
    » Лемматизация в Excel, или «Робот-распознаватель 3.0

    Так вот, несмотря на невероятную скорость работы этих файлов (невероятную для Excel), их создание потребовало использования таких же невероятно длинных мегаформул как одной из составляющих работы макросов (в последней из вышеуказанных статей приведен пример — формула на 3215 символов). И всему виной сложный синтаксис функции.

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

    Синтаксис выглядит так:
    Если(ВПР(искомое; массив;1; ИСТИНА)<искомое;""; ВПР(искомое; массив;n; ИСТИНА))

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

    Вместо «ИСТИНА» в 4-м параметре можно использовать «1» для номинального сокращения длины формул, это не меняет их сути.

    Если озвучить ход работы формулы, будет нижеследующее:

    «Если бинарный поиск ключа по первому столбцу массива возвращает значение, меньшее, чем сам ключ, возвращаем пустую строку. Иначе — возвращаем результат бинарного поиска ключа со смещением n».

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

    Напомню, на карту поставлен прирост скорости, исчисляющийся трех-четырехзначными числами. Если подходить чисто математически — на массиве в 2^20 строк обычный бинарный поиск будет делать ~10 вычислений, формула выше — около 20, в то время, как линейный поиск — ~500.000, т.е. прирост формулы выше — в 25.000 раз. Если голые цифры не впечатляют, более красноречивое эквивалентное сравнение — 1 секунда против ~7 часов.

    На практике прирост не столь существенный (в конце статьи ссылка на статью, где сравнивались разные способы). Это во многом связано с затратами процессорного времени на дополнительные процедуры, которые выполняет программа (например, запись значений в ячейки). НО прирост по-прежнему критически значимый (~4000 раз).

    Но одновременно с этим мы имеем сложный, совершенно неюзабельный синтаксис. Не всем смертным дался ВПР, что говорить о комбинациях 2х ВПР с ЕСЛИ.

    Вопрос со сложным синтаксисом я решил с помощью VBA — написал UDF (user-defined function, пользовательская функция), которая прячет под капот наши условные конструкции, оставляя нам привычный синтаксис всем известного ВПР.

    Код UDF:

    Public Function БИНПОИСК(a, b As Range, c As Integer) As String
    If Application.VLookup(a, b.Columns(1), 1, True) = a Then
        БИНПОИСК = Application.VLookup(a, b, c, True)
    Else
        БИНПОИСК = ""
    End If
    End Function

    Чтобы использовать функцию в вашем Excel файле, нужно добавить в текущую книгу модуль, в который добавить вышеуказанный код, или скачать по ссылке файл-пример, в котором это уже сделано за вас.

    Функция принимает на вход 3 параметра, синтаксис аналогичен обычному ВПР, за исключением 4-го параметра, т.к. он не нужен: (искомое; массив; номер столбца).

    Так на выходе мы получили функцию с привычным синтаксисом и привычным поведением, но со скоростью, в десятки-сотни-тысячи раз быстрее обычного ВПР, в зависимости от длины массива. С единственным ограничением — функция работает корректно только на массиве, сортированном от меньшего к большему. Зачастую последний момент не является непреодолимым препятствием.

    Пользуйтесь, комментируйте. Буду рад улучшениям в алгоритм и похожие идеи реализации.
    Работаю над оптимизацией поиска на Python, на текущий момент быстрее стандартного поиска по словарю не нашел, буду рад комментариям и по этой части.

    Ссылки


    » Статья про трюк с двойным ВПР «Почему 2 ВПР лучше, чем 1»
    » Сравнение разных способов поиска, включая «трюк с двойным впр»
    » Последняя версия «Робота-Распознавателя» и все предыдущие, и некоторые другие инструменты для контекстной рекламы, включая предмет этой статьи, по одной ссылке.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 25
    • +1
      Тема! Спасибо!
      • 0
        Дмитрий, первый параметр в формуле у меня работает, только если я ссылаюсь на ячейку. текст в кавычках например не могу прописать — не срабатывает. так и должно быть?
        • 0
          Исходя из синтаксиса — да, но практически нужно учитывать и этот вариант, не продумал его заранее. Реализую
        • 0
          на массиве в 2^20 строк обычный бинарный поиск будет делать ~10 вычислений, формула выше — около 20, в то время, как линейный поиск — ~500.000

          Как было получено ~500.000? 2^20/2? VLOOKUP в Excel идёт в 2 потока?
          • 0
            Нет, речь о чисто математическом расчете, если не учитывать никакие внешние факторы (многопоточность, обслуживание функции, запись в файл и т.д.).
            Если массив 2^20 строк и все поиски разнородные, то при стремлении количества поисков к бесконечности среднее количество операций на один поиск стремится к числу, равному половине массива. Т.к. экстремумы — 1 и 2^20 (искомое может быть как в первой, так и в последней строке), среднее на большом количестве где-то посередине, т.е. 2^10, или ~500.000
            • 0
              аналогично при бинарном поиске, искомое может быть найдено как на 1-й, так и на 20-й итерации. На бесконечном количестве поисков среднее время поиска будет 10 итераций.
              • 0
                Спасибо!

                на текущий момент быстрее стандартного поиска по словарю не нашел, буду рад комментариям и по этой части.

                Есть ещё set() — он меньше в памяти занимает. Грубо говоря, это словарь, в котором есть только ключи, а значений нет.
                • 0
                  продумывал этот вариант, поскольку стажа программирования практически нет, еще не разобрался, даст ли прирост в моем кейсе.
                  + критичным является не оптимизация объема занимаемой памяти, а оптимизация процессорного времени.
                  Массивы в моих задачах большие, но не настолько большие, чтобы не хватило памяти.
                  • 0
                    Если важна скорость, то я бы не использовал Python, а смотрел в сторону C. Хотя и для Python есть разного рода ускорялки.
            • 0
              Первое.
              С единственным ограничением — функция работает корректно только на массиве, сортированном от меньшего к большему.
              На мой взгляд, если уж написали пользовательскую функцию, так почему бы сразу не включить в код предварительную сортировку массива?
              .
              .
              .
              Второе. Поведение отличается от ВПР, что не есть хорошо.

              image
              http://prntscr.com/cyoibc

              Например, при расширении семантического ядра искусственной семантикой 100% будут дубли. Вместо классического инструмента «удалить дубликаты» я иногда использую ВПР для поиска и удаления таких дублей (причину этого и детали расписывать лень, в данном контексте это не важно).

              Полагаю, улучшенная формула должна иметь такое же поведение на массивах, содержащих дубликаты, что и исходный ВПР=)
              • 0
                по 1-му пункту — так и было задумано, если хотите свой вариант — вполне можете переработать код под ваши нужды. По мне это предложение уже чересчур кастомное.
                по 2-му — тут интереснее, так не было задумано, буду фиксить вместе с первым параметром, который не принимает вручную добавленные или вычисляемые строки (что хотелось бы и мне в том числе). Апдейт кода выложу.
                • 0
                  апдейт кода выложил, но вышеописанное поведение (скриншот) — корректное при бинарном поиске, поэтому там ничего не корректировалось. И в целом если корректировать, это ухудшит производительность.
                • 0
                  Дмитрий, спасибо большое за статью. В принципе фишка с двойным ВПРом очень ускорила пересчёты в файлах.

                  Подскажите, может вы знаете что-нибудь такого же уровня эффективности для поиска по 2 критериям? У меня сейчас подобный поиск реализован через ИНДЕКС+ПОИСКПОЗ, но работает данная связка омерзительно медленно. Можно как-либо ускорить процесс без добавления столбца с конкатенацией критериальных столбцов в исходную таблицу?
                  • +1
                    Решение выглядело бы как последовательная сортировка каждого из критериев, справа налево, затем конкатенация, затем тот же бинарный поиск с выводом значения. Это возможно, если сортировка не мешает.
                    Думаю, решения должны быть, если нет, можно задуматься о реализации.
                  • +1
                    ВПР, к сожалению, требует слишком много условий для нормальной работы:
                    — ключ в первом столбце
                    — ключ сортированный по возврастанию
                    — повторый ключа вносят неопределенность

                    Для составления чего-то, похожего на реляционную базу с контролем ошибок неприменима.

                    Поэтому
                    — либо СУММПРОИЗВ — для работы с числовыми результирующими столбами и отбор по любому количеству параметров
                    — либо связка ПОИСКПОЗ+СЦЕПИТЬ+ИНДЕКС — для опятьже нескольких условий и получения текстового значения (в этом варианте дубли ключа также вносят непореденность)
                    — либо формула массива для высталения парамета по столбцам, а не только по строкам. Но это довольно медленно
                    • 0
                      кому как)
                      первые два пункта — трудно представить как нечто непреодолимое.
                      последний в моих проектах не актуален (ключи уникальны), и непонятно, как вопрос с неопределенностью решают другие алгоритмы.
                      Несколько условий — целый отдельный кейс реализации.
                      • 0
                        1. Не совсем согласен с вами.

                        ВПР, к сожалению, требует слишком много условий для нормальной работы:
                        — ключ сортированный по возврастанию
                        Если в формулу последним параметром ставить «0» («ЛОЖЬ») то поиск ведется до победного и сортировка для ВПР не нужна.

                        ВПР, к сожалению, требует слишком много условий для нормальной работы:
                        — повторый ключа вносят неопределенность
                        Так ИНДЕКС+ПОИСКПОЗ при наличие дублей тоже вырнет только первое найденное вхождение.
                        .
                        .
                        Итого, ВПР проигрывает ИНДЕКС+ПОИСКПОЗ только по требованию «ищу только в первом столбце».
                        .
                        .
                        .
                        2. Вы не могли бы привести конкретный пример, в каких случаях используете «СЦЕПИТЬ» в этой конструкции:
                        — либо связка ПОИСКПОЗ+СЦЕПИТЬ+ИНДЕКС — для опятьже нескольких условий и получения текстового значения
                        ?
                        • 0
                          Так делаем, когда надо получить текстовое значение, т.е. без агрегатных функций. Обычно в таких слкчаях наборка небольшая (сотни-тысячи записей), поэтому скорость не критична.

                          Например, 3 столбца отбора, 1 столбец данных. Добавляем 5-й столбец, который соединяет значения этих 3-х столбцов отбора: = СЦЕПИТЬ(Столбец1;"-"; Столбец2;"-"; Столбец3)

                          Потом при поиске пишем =Индекс(Столбец4; ПОИСКПОЗ(СЦЕПИТЬ(Условие1;"-"; Условие2;"-"; Условие3); Столбец5;0))
                          • 0
                            «1. Не сосем согласен с вами. Если в формулу последним параметром ставить «0» («ЛОЖЬ») то поиск ведется до победного и сортировка для ВПР не нужна».
                            Это понятно. Но тут ведь описывается вундервафля с ускорением в 25 раз. Только кто-то должен не забыть отсортировать данные. Для разовой обработки набора данных — пойдет. Для рабочего файла, которые используется регулярно, да ещё и несколькими пользователями — это выстрел в ногу. Такойже как сводные таблицы.
                            Кстати, ни автор статьи, ни в тех статья, на которые он ссылается, не указывается, за сколько с задачей справится сводная таблица — это может быть самый простой путь для разовой обработки данных.

                            Вообще, для разработки именно приложений многократного использования пока лучше всего показывают себя СУММПРОИЗВ (быстрее, но требуют данных одинакового размера) и формулы массивов (они медленне, но позволяют разноразмерные данные) в связке с таблицам (именование области данных с именованными столбцами)
                            • 0
                              «Итого, ВПР проигрывает ИНДЕКС+ПОИСКПОЗ только по требованию «ищу только в первом столбце».»

                              Также он проигрывает ещё в критичной зависимости к структуре данных. Добавление одного столбца в таблицу данных может все поломать.
                              Кстати, в стетьях, на которые ссылается автор, сравниваются в том числе и ВПР и ИНДЕКС+ПОИСКПОЗ. Вторая связка произрывает на 5-10% (на данных в 200 тыс строк 50 сек вместо 45), что не критично, зато поддерживает целостность данных.
                              • 0
                                зависимость от структуры при желании легко обойти. помимо ВПР есть ГПР — всегда можно ссылаться не на номер столбца, а на индекс его заголовка.
                                В других случаях можно просто ссылаться на индекс нужного столбца через подсчет ширины массива — при добавлении столбцов будет смещаться и индекс.
                                Речь вообще идет о феномене бинарного поиска, а не о функциях — индекс или ВПР. И та и та функция умеют искать бинарным поиском по сортированному массиву.
                                • 0
                                  на данных в 200 тыс строк 50 сек вместо 45), что не критично, зато поддерживает целостность данных.

                                  это если делать немного поисков.
                                  А если нужно одновременно в массиве из 1 млн значений найти другие 60.000 — это совершенно другая история. тут нужна сортировка и бинарный.
                              • 0
                                Тоже всегда пользуюсь Индекс + ПоискПоз, т.к. они универсальны, особенно при работе с таблицами формата 2007 и старше — нет зависимости от местоположения столбцов и их всегда можно менять.

                                Но, кстати, возникает вопрос — можно ли оптимизировать ПоискПоз?
                                • 0
                                  ПОИСКПОЗ тоже бывает бинарный, принимает последний аргумент 1 и -1 для сортировки а-я и я-а соответствено.
                                  Поэтому совмещение ВПР и Индекс-ПОИСКПОЗ дает убер-решение, которое такое же быстрое, но в то же время не обладает недостатками ВПР. В статье выше об этом тоже ведется речь, даже выложен пример функции. UDF тоже напишу, попозже, опубликую, если до меня кто-нибудь не опубликует :)
                                  Статья:
                                  http://analystcave.com/excel-vlookup-vs-index-match-vs-sql-performance/
                              • +1
                                Добавил усовершенствование.
                                https://habrahabr.ru/post/314302/

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое