Loser story

Loser story

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

В общем недавно появилось время и я доделал дерево вместо кучи,
померял и даже на простом компараторе получил ускорение на 15%.

Ещё недавно пофиксил оптимизировал довольно забавный кейс:
Дана сортированная по возрастанию последовательность уникальных чисел.
Затем по ней много ищут.
Есть две особенности:
1. В последовательности множество dense подотрезков, как правило с длиной больше 1.
2. Если все искомые числа выписать в одну последовательность, то это будет последовательность сортированных подотрезков, как правило с длиной больше 1.

Понятно что baseline здесь это обычный бинпоиск.
Но мы могли бы сохранить найденную позицию в массив.
Тогда при следующем поиске, нужно вычислить разницу между значением, которое было на этой позиции и искомым числом.
После прибавить эту разницу к прошлой позиции.
Затем проверить, что мы не вышли за пределы массива и это действительно искомый элемент.
В случае если между текущим искомым числом и прошлым был dense диапазон, мы нашли новое число.
А если не получилось все ещё можно использовать обычный бинпоиск.

Я не особо усердно бенчмаркал, так как это очевидно лучше, но даже на достаточно маленьких массивах (1e5) вышло в 2-4 раза быстрее.

GitHub

Use tree instead of heap for k-way merge by MBkkt · Pull Request #530 · iresearch-toolkit/iresearch

Motivation
Segment tree (tournament tree) always makes at most log_2(size) count of comparison.
Pessimistic heap (our previous approach) makes X count of comparison:

X = log_2(size + 1) - 1 when i...

www.tgoop.com/reverse13/711

1.7K viewsedited  Jul 6, 2023 at 20:27

В общем недавно появилось время и я доделал дерево вместо кучи,
померял и даже на простом компараторе получил ускорение на 15%.

Ещё недавно пофиксил оптимизировал довольно забавный кейс:
Дана сортированная по возрастанию последовательность уникальных чисел.
Затем по ней много ищут.
Есть две особенности:
1. В последовательности множество dense подотрезков, как правило с длиной больше 1.
2. Если все искомые числа выписать в одну последовательность, то это будет последовательность сортированных подотрезков, как правило с длиной больше 1.

Понятно что baseline здесь это обычный бинпоиск.
Но мы могли бы сохранить найденную позицию в массив.
Тогда при следующем поиске, нужно вычислить разницу между значением, которое было на этой позиции и искомым числом.
После прибавить эту разницу к прошлой позиции.
Затем проверить, что мы не вышли за пределы массива и это действительно искомый элемент.
В случае если между текущим искомым числом и прошлым был dense диапазон, мы нашли новое число.
А если не получилось все ещё можно использовать обычный бинпоиск.

Я не особо усердно бенчмаркал, так как это очевидно лучше, но даже на достаточно маленьких массивах (1e5) вышло в 2-4 раза быстрее.

BY Loser story