Вдосконалимо функцію ВВР Excel

Прочитання публікації Спрощуємо бінарний пошук в Excel сподвигло на додаткове вдосконалення функції ВВР порівняно з наведеним у статті.
Що не було враховано, і що хотілося б додати:
Читати далі →

Спрощуємо бінарний пошук в 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:

Читати далі →

SMAS: «Відсортована мульти-масивна структура» (Sorted Multi Struct Array) — альтернатива бінарним дереву пошуку

Вступ

Здрастуйте, хабравчане. Це моя перша публікація, в якій хочу поділитися структурою даних SMAS. В кінці статті буде надано З++ — клас запропонованої структури даних. Реалізація рекурсивна, але моя мета — донести ідею. Реалізацію не рекурсивну версії — справа друга. Важливо «почути» думки.

Що не так з деревом?

Так, все так і можна завершувати статтю, всім спасибі. було б плюнути на значний оверхеад пам'яті на допоміжні дані у вигляді посилань на ліві-праві піддерева і прапор для балансування (різний в залежності від використовуваної техніки — червоно-чорні, АВЛ і т. п. дерева). Ще один, не те щоб мінус — це постійна модифікація дерева при вставці для балансування (тут особливо важлива складність і заплутаність методів для новачків). На цьому мінуси закінчуються і складно собі уявити щось краще і більш універсальне (хеш-таблиці, ІМХО, ще крутіше, але ОХ ВЖЕ ЦІ КОЛІЗІЇ).

Читати далі →

Питання про індекси, які вам не треба буде задавати



Після відповідей на 14 питань про індекси, які ви соромилися задати, у мене виникло набагато більше коментарів, уточнень і виправлень. Скомпілювати з усього цього статтю виглядало витівкою з мінімумом користі. І це змусило мене задумався, а чому взагалі ми повинні «соромитися ставити подібні питання? Соромно не знати? А чи є спосіб розібратися, не вганяючи себе в фарбу? Є. Причому він позбавить від численних неточностей, якими рясніють багато «відповіді». Ви будете почувати буквально кожен байт вашої бази кінчиками своїх пальців.

Для цього, я пропоную підняти капот» у SQL Server і зануритися в солодкий мир шістнадцяткових дампів. Може статися, що всередині все набагато простіше, ніж вам здавалося.


Читати далі →