Loser story

Вообще как бы вы решали задачу k-way merge (есть k отсортированных input, нужно получить 1 отсортированный output)?

Я бы встретив такое на собесе решил бы через кучу, и с асимптотической точки зрения лучше нельзя.

Но с практической можно делать меньшее (в константу раз) число сравнений.
Вчера я вспомнил, что хотел померить это в arangosearch.

Ну и в общем в чем же идея?
Давайте сначала вспомним, что будет происходить в случае кучи:
Каждый раз доставая элемент нужно сделать sift down обновленной вершины:
Это в свою очередь спуск вниз на глубину log(k), к сожалению на каждом спуске нам ещё нужно проверять спускаться в левое или в правое под дерево, то есть в итоге мы получим не больше 2 * log(k)
(в плюсах и многих других языках из коробки ещё хуже, так как decrease key отсутствует, нужно сделать pop + push, что уже до 3 логарифмов, +1 потому что push это sift up, который требует не более логарифма сравнений)

Почему такое вообще происходит?
Потому что с точки зрения дерева минимумов оно у нас встроенное в сами данные, и поддерживать такую структуру немного сложнее.

Поэтому вместо этого можно поддержать дерево явно, по сути сделав дерево отрезков минимумов, такой подход называют tournament tree, и он даст ровно log сравнений

Cегодня я набросал код и вероятно завтра напишу микробенчмарки, потом еще посмотрю на перф в аранге:
https://github.com/iresearch-toolkit/iresearch/pull/476

В целом весьма очевидно что мы выигрываем, есть ли минусы? В сравнение с pop + push подходом нет, в сравнении с sift_down к сожалению да.

Главная проблема что в случае дерева нам нужно поднимать новое значение снизу, то есть логарифм сравнений мы делаем всегда.
В случае же с кучей мы опускаем значение среди других значений и если нам повезло и input-ы не пересекаются мы на каждый push в output будем делать только 2 сравнения (кроме тех где input закончился).

Резюмируя для [0;4-8] инпутов tournament tree однозначно лучший подход, относительно числа сравнений.

А дальше это зависит от данных. Если данные рандомные то все еще лучший. А вот если по какой-то причине у вас очень мало переключений инпутов или вообще disjoint диапазоны, то вероятно ручной sift down покажет себя оптимальнее :(

Можно ли что-то с этим сделать?
Наверно нет, только страдать, впрочем еще мне нравится подход с деревом тем, что это всегда фиксированное число сравнений, их число не зависит от того как именно output данные расположены в input-ах

GitHub

Benchmark comparison count: tournament tree vs binary heap by MBkkt · Pull Request #476 · iresearch-toolkit/iresearch

IResearch is a cross-platform, high-performance document oriented search engine library written entirely in C++ with the focus on a pluggability of different ranking/similarity models - Benchmark comparison count: tournament tree vs binary heap by MBkkt ·…

👍7👎1

www.tgoop.com/reverse13/708

2.11K viewsedited  Jan 23, 2023 at 00:47

Вообще как бы вы решали задачу k-way merge (есть k отсортированных input, нужно получить 1 отсортированный output)?

Я бы встретив такое на собесе решил бы через кучу, и с асимптотической точки зрения лучше нельзя.

Но с практической можно делать меньшее (в константу раз) число сравнений.
Вчера я вспомнил, что хотел померить это в arangosearch.

Ну и в общем в чем же идея?
Давайте сначала вспомним, что будет происходить в случае кучи:
Каждый раз доставая элемент нужно сделать sift down обновленной вершины:
Это в свою очередь спуск вниз на глубину log(k), к сожалению на каждом спуске нам ещё нужно проверять спускаться в левое или в правое под дерево, то есть в итоге мы получим не больше 2 * log(k)
(в плюсах и многих других языках из коробки ещё хуже, так как decrease key отсутствует, нужно сделать pop + push, что уже до 3 логарифмов, +1 потому что push это sift up, который требует не более логарифма сравнений)

Почему такое вообще происходит?
Потому что с точки зрения дерева минимумов оно у нас встроенное в сами данные, и поддерживать такую структуру немного сложнее.

Поэтому вместо этого можно поддержать дерево явно, по сути сделав дерево отрезков минимумов, такой подход называют tournament tree, и он даст ровно log сравнений

Cегодня я набросал код и вероятно завтра напишу микробенчмарки, потом еще посмотрю на перф в аранге:
https://github.com/iresearch-toolkit/iresearch/pull/476

В целом весьма очевидно что мы выигрываем, есть ли минусы? В сравнение с pop + push подходом нет, в сравнении с sift_down к сожалению да.

Главная проблема что в случае дерева нам нужно поднимать новое значение снизу, то есть логарифм сравнений мы делаем всегда.
В случае же с кучей мы опускаем значение среди других значений и если нам повезло и input-ы не пересекаются мы на каждый push в output будем делать только 2 сравнения (кроме тех где input закончился).

Резюмируя для [0;4-8] инпутов tournament tree однозначно лучший подход, относительно числа сравнений.

А дальше это зависит от данных. Если данные рандомные то все еще лучший. А вот если по какой-то причине у вас очень мало переключений инпутов или вообще disjoint диапазоны, то вероятно ручной sift down покажет себя оптимальнее :(

Можно ли что-то с этим сделать?
Наверно нет, только страдать, впрочем еще мне нравится подход с деревом тем, что это всегда фиксированное число сравнений, их число не зависит от того как именно output данные расположены в input-ах

BY Loser story