Добавлю в копилку статей Хабра о Бинарном поиске еще одну.
Речь пойдет о кастомной реализации, может быть полезно всем, кто часто использует в работе ВПР для сравнения больших списков или для поиска данных в больших массивах.
Предыстория
Все началось с того, что я открыл для себя т.н. 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 As Range, b As Range, c As Integer)
If Application.WorksheetFunction.VLookup(a, [b].CurrentRegion.Columns(1).Value, 1, True) < a Then
БИНПОИСК = ""
Else
БИНПОИСК = Application.WorksheetFunction.VLookup(a, b, c, True)
End If
End Function
Чтобы использовать функцию в вашем Excel файле, нужно добавить в текущую книгу модуль, в который добавить вышеуказанный код, или скачать по ссылке файл-пример, в котором это уже сделано за вас.
Функция принимает на вход 3 параметра, синтаксис аналогичен обычному ВПР, за исключением 4-го параметра, т.к. он не нужен: (искомое; массив; номер столбца).
Так на выходе мы получили функцию с привычным синтаксисом и привычным поведением, но со скоростью, в десятки-сотни-тысячи раз быстрее обычного ВПР, в зависимости от длины массива. С единственным ограничением — функция работает корректно только на массиве, сортированном от меньшего к большему. Зачастую последний момент не является непреодолимым препятствием.
Пользуйтесь, комментируйте. Буду рад улучшениям в алгоритм и похожие идеи реализации.
Работаю над оптимизацией поиска на Python, на текущий момент быстрее стандартного поиска по словарю не нашел, буду рад комментариям и по этой части.
Ссылки
fastexcel.wordpress.com/2012/03/29/vlookup-tricks-why-2-vlookups-are-better-than-1-vlookup — Статья про трюк с двойным ВПР «Почему 2 ВПР лучше, чем 1».
analystcave.com/excel-vlookup-vs-index-match-vs-sql-performance — сравнение разных способов поиска, включая «трюк с двойным впр»
Последняя версия «Робота-Распознавателя» и все предыдущие, и некоторые другие инструменты для контекстной рекламы, включая предмет этой статьи, по одной ссылке.
Автор: tiendi3
