Спрощуємо бінарний пошук в 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 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 — порівняння різних способів пошуку, включаючи «трюк з подвійним ввр
Остання версія «Робота-Розпізнавача» і всі попередні, і деякі інші інструменти для контекстної реклами, включаючи предмет цієї статті, за однією посиланням.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.