Тридцать триллионов сравнений нужно, чтобы сверить в лоб базы на двадцать пять миллионов и миллион двести тысяч клиентов. Слияние упорядоченных баз справится в десятки тысяч раз быстрее. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский показывает его и быструю сортировку в трёх нотациях.
Рис. 1. Слияние сравнивает только первые заявки двух очередей и переносит более срочную
Крупному игроку, скупавшему местные банки, за двадцать лет пришлось семь раз втягивать чужую клиентскую базу – от 1,2 до 25 млн записей. У клиента бывало от одного до семи активных продуктов плюс счета, и счёт шёл на сутки, а не на часы, даже на сверхмощном оборудовании. Главный вопрос каждый раз: как свести базы, не потеряв ни клиента, ни истории.
Форматы данных различались префиксами, суффиксами, очерёдностью, числом заполненных и зарезервированных полей. Клиент мог оказаться примерным в одном банке и должником в другом. Постепенно выработали единый профиль клиента, который скоро перестал меняться: он вобрал опыт множества проб и ошибок.
Короткий ответ: слияние сводит две упорядоченные очереди за один проход и делает не больше сравнений, чем заявок в обеих. На нём держится сортировка слиянием с гарантированной ценой. Быстрая сортировка в среднем почти так же хороша, но на готовом списке может провалиться. Рисовать обе удобнее всего деревом разбиения.
Как устроено слияние?
Слияние – способ свести две упорядоченные очереди в одну, сравнивая каждый раз только первые заявки обеих. Более срочная переходит в итог, и сравнение повторяется с новой первой заявкой. Когда одна очередь опустела, остаток другой дописывают целиком, уже без сравнений.
На схеме по ГОСТ 19.701 это один цикл с двумя ромбами: левый проверяет, есть ли что сравнивать, правый выбирает, из какой очереди брать. При равных сроках берут заявку из очереди A, и клиент, пришедший раньше, не окажется позади.
Как «Кедр» сливает две очереди?
Сервисная компания «Кедр» купила соседнюю фирму «Ольха» вместе с очередью заявок. У «Кедра» до срока осталось один, три, семь и девять дней, у «Ольхи» – два, пять и восемь. Обе очереди упорядочены, и диспетчеру нужна одна общая.
Рис. 2. Слияние по шагам: заявки «Кедра» и «Ольхи» встают в общий порядок
Шесть сравнений на семь заявок: каждое отправляет в итог одну, а последнюю переносят без сравнения. Если бы каждую заявку «Ольхи» сверяли со всеми заявками «Кедра», понадобилось бы двенадцать. На базах в миллионы записей эта разница вырастает до тех самых триллионов.
Как слияние превращается в сортировку?
Сортировка слиянием – способ упорядочить список, разрезая его пополам до одиночных заявок и сливая половинки обратно. Одиночная заявка упорядочена сама по себе, а сливать упорядоченное уже умеем. Работа идёт уровнями: на каждом сливают все пары кусков.
Рис. 3. Слева – сортировка слиянием, справа – быстрая сортировка с опорной «7»
На пяти заявках со сроками 7, 3, 9, 1 и 5 выходит восемь сравнений – столько же, сколько у вставок из прошлой статьи. Разница видна на масштабе: сотню заявок слияние упорядочит в среднем за 542 сравнения и никогда не больше чем за 573, а вставкам нужно около 2’500.
Чем быстрая сортировка отличается от слияния?
Быстрая сортировка – способ делить список не пополам, а по опорной заявке: всё, что срочнее неё, уходит в одну стопку, остальное – во вторую. Каждую стопку делят так же, пока не останется одна заявка, а потом склеивают. На тех же пяти заявках с опорной «7» – шесть сравнений.
Иногда поглощение было сложнее: вместе с банком покупали страховую компанию или иной сопутствующий бизнес. Часть клиентов была только розничной, другие сочетали признаки физлица и ИП, третьи – физлица и участника ООО или ИП и участника ООО. Отдельно шли нотариусы и адвокаты, выступавшие в двух, трёх и четырёх ролях.
Разложить такую базу на стопки по одному свойству не получалось: клиент попадал сразу в несколько. Опорное свойство приходилось выбирать так, чтобы каждая запись уходила ровно в одну стопку, – эту задачу и решил единый профиль клиента.
Рис. 4. Роли клиентов пересекаются, поэтому одной стопки по признаку мало
Сколько стоит каждый метод?
Сверка двух баз в лоб требует произведения размеров обеих: 25 млн на 1,2 млн – тридцать триллионов сравнений, или трое с половиной суток при ста миллионах сравнений в секунду. Упорядочить обе базы и слить – около 650 млн сравнений, секунды машинного времени. Поэтому любое слияние баз начинают с упорядочивания по ключу.
На сотне заявок «Кедра» разница видна и без миллионов: слияние делает в среднем 542 сравнения, быстрая сортировка – 652, вставки – около 2’500, пузырёк – около 4’900. При десяти секундах на сравнение это полтора часа против тринадцати с половиной.
Руководителю важнее не среднее, а гарантия. Сортировка слиянием никогда не выйдет за 573 сравнения на сотне заявок, а быстрая сортировка без страховки может потратить в восемь с половиной раз больше.
У быстрой сортировки есть ловушка. Если опорной всегда брать первую заявку, а список уже упорядочен, все заявки уходят в одну стопку, и метод вырождается в пузырёк – 4’950 сравнений на сотне. Лечится просто: опорную берут случайно или из середины списка. Слияние такой ловушки лишено: цена слияния никогда не превышает гарантированной.
Рис. 5. На готовом списке наивная быстрая сортировка проваливается до уровня пузырька
Какими нотациями рисовать «разделяй и властвуй»?
ГОСТ 19.701 хорошо передаёт одно слияние – цикл с двумя развилками. С сортировкой хуже: она вызывает сама себя, а стандарт обозначает это лишь блоком «предопределённый процесс», без картины дробления. Его ценят авторы регламентов, но объяснить по нему рекурсию трудно.
Дерево разбиения – рисунок, где каждый узел – кусок списка, а ветки показывают, на что его делят и как собирают. Его любят преподаватели алгоритмов и аналитики данных: глубина дерева сразу говорит о числе уровней, а цифры на ветках – цену каждого шага. На рисунке слева три уровня деления и восемь сравнений, справа – два уровня и шесть.
Диаграмма дорожек передаёт ту же логику как работу людей: исполнители получают отдельные полосы. Координатор назначает опорную заявку и раскладывает стопки, команды упорядочивают их параллельно, координатор склеивает результат.
Рис. 6. Дорожки показывают, кто делит заявки и кто их упорядочивает
Дорожки предпочитают руководители проектов и владельцы процессов: видно, кто кого ждёт и где команды трудятся параллельно. Но дорожки молчат о главном – почему стопки выходят примерно равными и сколько раз придётся делить.
Какая нотация лучше?
Лучшая нотация для «разделяй и властвуй» – дерево разбиения: 21 балл против 16 у дорожек и 13 у ГОСТ. Руководитель за минуту видит, что задача делится уровнями, а цена уровня – не больше числа заявок. Вес вопроса о руководителе удвоен, ведь сборник написан для него.
Рис. 7. Оценка трёх нотаций: 21, 16 и 13 баллов
Дорожки пригодятся вторым рисунком, когда работу раздают командам и нужно показать, кто за что отвечает. ГОСТ остаётся для одной процедуры слияния, где нет рекурсии, зато важна строгость формы.
Когда какой метод уместен?
Слияние подходит для двух упорядоченных очередей: баз после поглощения, выгрузок из двух систем, отчётов двух филиалов. Сортировка слиянием нужна там, где важны гарантия по времени и сохранение порядка заявок с равным сроком.
Для «Кедра» правило простое: две готовые очереди сливают, новую заявку вставляют на место, а большую неупорядоченную груду распределяют между диспетчерами по опорному сроку и сводят слиянием – так же, как банк сводил базы.
Быстрая сортировка хороша, если работу удобно раздать по признаку, а порядок заявок с одинаковым сроком не важен: так делят завал между филиалами или линиями поддержки.
Проверить слияние просто: записей в итоге должно быть столько, сколько в обеих базах, минус найденные дубли, а каждый дубль – в отдельном списке на разбор. Если цифры не сходятся, где-то потерян клиент, и найти его лучше до того, как он сам позвонит с жалобой.
В следующей статье сборника – двоичный поиск: как найти заявку в упорядоченном списке из ста строк за семь вопросов, а не за сто.
Что сделать руководителю?
Хватит четырёх шагов:
- Перед слиянием баз договоритесь о едином ключе клиента и формате записи.
- Упорядочьте обе базы по нему и сливайте за один проход.
- Клиентов с несколькими ролями выносите в отдельную очередь на ручной разбор.
- Большую работу делите по опорному признаку между командами, а готовые части сводите слиянием за один проход.
Что запомнить?
- слияние сводит две упорядоченные очереди за один проход
- сортировка слиянием упорядочит сотню заявок не дольше чем за 573 сравнения
- быстрая сортировка делит по опорной заявке и проваливается на готовом списке
- сверка баз в лоб стоит произведения размеров
- «разделяй и властвуй» лучше всего рисовать деревом разбиения.