Предыстория
Все началось с того, что я открыл для себя т.н. 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)
grunga
24.10.2016 22:51Дмитрий, первый параметр в формуле у меня работает, только если я ссылаюсь на ячейку. текст в кавычках например не могу прописать — не срабатывает. так и должно быть?
tiendi3
24.10.2016 22:53Исходя из синтаксиса — да, но практически нужно учитывать и этот вариант, не продумал его заранее. Реализую
Habra__User
25.10.2016 11:24на массиве в 2^20 строк обычный бинарный поиск будет делать ~10 вычислений, формула выше — около 20, в то время, как линейный поиск — ~500.000
Как было получено ~500.000? 2^20/2? VLOOKUP в Excel идёт в 2 потока?tiendi3
25.10.2016 11:30Нет, речь о чисто математическом расчете, если не учитывать никакие внешние факторы (многопоточность, обслуживание функции, запись в файл и т.д.).
Если массив 2^20 строк и все поиски разнородные, то при стремлении количества поисков к бесконечности среднее количество операций на один поиск стремится к числу, равному половине массива. Т.к. экстремумы — 1 и 2^20 (искомое может быть как в первой, так и в последней строке), среднее на большом количестве где-то посередине, т.е. 2^10, или ~500.000tiendi3
25.10.2016 11:32аналогично при бинарном поиске, искомое может быть найдено как на 1-й, так и на 20-й итерации. На бесконечном количестве поисков среднее время поиска будет 10 итераций.
Habra__User
25.10.2016 11:34Спасибо!
на текущий момент быстрее стандартного поиска по словарю не нашел, буду рад комментариям и по этой части.
Есть ещё set() — он меньше в памяти занимает. Грубо говоря, это словарь, в котором есть только ключи, а значений нет.tiendi3
25.10.2016 11:56продумывал этот вариант, поскольку стажа программирования практически нет, еще не разобрался, даст ли прирост в моем кейсе.
+ критичным является не оптимизация объема занимаемой памяти, а оптимизация процессорного времени.
Массивы в моих задачах большие, но не настолько большие, чтобы не хватило памяти.Habra__User
25.10.2016 15:23Если важна скорость, то я бы не использовал Python, а смотрел в сторону C. Хотя и для Python есть разного рода ускорялки.
zamboga
25.10.2016 13:58Первое.
С единственным ограничением — функция работает корректно только на массиве, сортированном от меньшего к большему.
На мой взгляд, если уж написали пользовательскую функцию, так почему бы сразу не включить в код предварительную сортировку массива?
.
.
.
Второе. Поведение отличается от ВПР, что не есть хорошо.
http://prntscr.com/cyoibc
Например, при расширении семантического ядра искусственной семантикой 100% будут дубли. Вместо классического инструмента «удалить дубликаты» я иногда использую ВПР для поиска и удаления таких дублей (причину этого и детали расписывать лень, в данном контексте это не важно).
Полагаю, улучшенная формула должна иметь такое же поведение на массивах, содержащих дубликаты, что и исходный ВПР=)tiendi3
25.10.2016 23:06по 1-му пункту — так и было задумано, если хотите свой вариант — вполне можете переработать код под ваши нужды. По мне это предложение уже чересчур кастомное.
по 2-му — тут интереснее, так не было задумано, буду фиксить вместе с первым параметром, который не принимает вручную добавленные или вычисляемые строки (что хотелось бы и мне в том числе). Апдейт кода выложу.
tiendi3
28.10.2016 03:09апдейт кода выложил, но вышеописанное поведение (скриншот) — корректное при бинарном поиске, поэтому там ничего не корректировалось. И в целом если корректировать, это ухудшит производительность.
Si1ent_Assass1N
25.10.2016 22:44Дмитрий, спасибо большое за статью. В принципе фишка с двойным ВПРом очень ускорила пересчёты в файлах.
Подскажите, может вы знаете что-нибудь такого же уровня эффективности для поиска по 2 критериям? У меня сейчас подобный поиск реализован через ИНДЕКС+ПОИСКПОЗ, но работает данная связка омерзительно медленно. Можно как-либо ускорить процесс без добавления столбца с конкатенацией критериальных столбцов в исходную таблицу?tiendi3
25.10.2016 23:01+1Решение выглядело бы как последовательная сортировка каждого из критериев, справа налево, затем конкатенация, затем тот же бинарный поиск с выводом значения. Это возможно, если сортировка не мешает.
Думаю, решения должны быть, если нет, можно задуматься о реализации.
max1gu
28.10.2016 02:55+1ВПР, к сожалению, требует слишком много условий для нормальной работы:
— ключ в первом столбце
— ключ сортированный по возврастанию
— повторый ключа вносят неопределенность
Для составления чего-то, похожего на реляционную базу с контролем ошибок неприменима.
Поэтому
— либо СУММПРОИЗВ — для работы с числовыми результирующими столбами и отбор по любому количеству параметров
— либо связка ПОИСКПОЗ+СЦЕПИТЬ+ИНДЕКС — для опятьже нескольких условий и получения текстового значения (в этом варианте дубли ключа также вносят непореденность)
— либо формула массива для высталения парамета по столбцам, а не только по строкам. Но это довольно медленноtiendi3
28.10.2016 03:03кому как)
первые два пункта — трудно представить как нечто непреодолимое.
последний в моих проектах не актуален (ключи уникальны), и непонятно, как вопрос с неопределенностью решают другие алгоритмы.
Несколько условий — целый отдельный кейс реализации.
zamboga
28.10.2016 10:391. Не совсем согласен с вами.
ВПР, к сожалению, требует слишком много условий для нормальной работы:
Если в формулу последним параметром ставить «0» («ЛОЖЬ») то поиск ведется до победного и сортировка для ВПР не нужна.
— ключ сортированный по возврастанию
ВПР, к сожалению, требует слишком много условий для нормальной работы:
Так ИНДЕКС+ПОИСКПОЗ при наличие дублей тоже вырнет только первое найденное вхождение.
— повторый ключа вносят неопределенность
.
.
Итого, ВПР проигрывает ИНДЕКС+ПОИСКПОЗ только по требованию «ищу только в первом столбце».
.
.
.
2. Вы не могли бы привести конкретный пример, в каких случаях используете «СЦЕПИТЬ» в этой конструкции:
— либо связка ПОИСКПОЗ+СЦЕПИТЬ+ИНДЕКС — для опятьже нескольких условий и получения текстового значения
?max1gu
28.10.2016 14:17Так делаем, когда надо получить текстовое значение, т.е. без агрегатных функций. Обычно в таких слкчаях наборка небольшая (сотни-тысячи записей), поэтому скорость не критична.
Например, 3 столбца отбора, 1 столбец данных. Добавляем 5-й столбец, который соединяет значения этих 3-х столбцов отбора: = СЦЕПИТЬ(Столбец1;"-"; Столбец2;"-"; Столбец3)
Потом при поиске пишем =Индекс(Столбец4; ПОИСКПОЗ(СЦЕПИТЬ(Условие1;"-"; Условие2;"-"; Условие3); Столбец5;0))
max1gu
28.10.2016 14:26«1. Не сосем согласен с вами. Если в формулу последним параметром ставить «0» («ЛОЖЬ») то поиск ведется до победного и сортировка для ВПР не нужна».
Это понятно. Но тут ведь описывается вундервафля с ускорением в 25 раз. Только кто-то должен не забыть отсортировать данные. Для разовой обработки набора данных — пойдет. Для рабочего файла, которые используется регулярно, да ещё и несколькими пользователями — это выстрел в ногу. Такойже как сводные таблицы.
Кстати, ни автор статьи, ни в тех статья, на которые он ссылается, не указывается, за сколько с задачей справится сводная таблица — это может быть самый простой путь для разовой обработки данных.
Вообще, для разработки именно приложений многократного использования пока лучше всего показывают себя СУММПРОИЗВ (быстрее, но требуют данных одинакового размера) и формулы массивов (они медленне, но позволяют разноразмерные данные) в связке с таблицам (именование области данных с именованными столбцами)
max1gu
28.10.2016 14:35«Итого, ВПР проигрывает ИНДЕКС+ПОИСКПОЗ только по требованию «ищу только в первом столбце».»
Также он проигрывает ещё в критичной зависимости к структуре данных. Добавление одного столбца в таблицу данных может все поломать.
Кстати, в стетьях, на которые ссылается автор, сравниваются в том числе и ВПР и ИНДЕКС+ПОИСКПОЗ. Вторая связка произрывает на 5-10% (на данных в 200 тыс строк 50 сек вместо 45), что не критично, зато поддерживает целостность данных.tiendi3
29.10.2016 00:46зависимость от структуры при желании легко обойти. помимо ВПР есть ГПР — всегда можно ссылаться не на номер столбца, а на индекс его заголовка.
В других случаях можно просто ссылаться на индекс нужного столбца через подсчет ширины массива — при добавлении столбцов будет смещаться и индекс.
Речь вообще идет о феномене бинарного поиска, а не о функциях — индекс или ВПР. И та и та функция умеют искать бинарным поиском по сортированному массиву.
tiendi3
29.10.2016 00:51на данных в 200 тыс строк 50 сек вместо 45), что не критично, зато поддерживает целостность данных.
это если делать немного поисков.
А если нужно одновременно в массиве из 1 млн значений найти другие 60.000 — это совершенно другая история. тут нужна сортировка и бинарный.
SAnatoly
28.10.2016 17:38Тоже всегда пользуюсь Индекс + ПоискПоз, т.к. они универсальны, особенно при работе с таблицами формата 2007 и старше — нет зависимости от местоположения столбцов и их всегда можно менять.
Но, кстати, возникает вопрос — можно ли оптимизировать ПоискПоз?tiendi3
29.10.2016 00:36ПОИСКПОЗ тоже бывает бинарный, принимает последний аргумент 1 и -1 для сортировки а-я и я-а соответствено.
Поэтому совмещение ВПР и Индекс-ПОИСКПОЗ дает убер-решение, которое такое же быстрое, но в то же время не обладает недостатками ВПР. В статье выше об этом тоже ведется речь, даже выложен пример функции. UDF тоже напишу, попозже, опубликую, если до меня кто-нибудь не опубликует :)
Статья:
http://analystcave.com/excel-vlookup-vs-index-match-vs-sql-performance/
4002
Тема! Спасибо!