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

Если часто используете в работе ВПР для сравнения или поиска данных в больших массивах
vlookup

Предыстория

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

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

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

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

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

Мануал по решению типизированных задач в Microsoft Excel

Синтаксис выглядит так:

Если(ВПР(искомое; массив;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-го параметра, т.к. он не нужен: (искомое; массив; номер столбца).

Разбираем и вычисляем формулы MS Excel

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