Паттерн «веревка» (rope)
Как выяснилось, веревка нынче не входит в курс алгоритмов и структур данных для школьников, а высшее образование, как известно, для слабаков
ссылка на википедию для тех, кто считает, что я непонятно объясняю
Классичесая веревка
состоит из
- Типа
- Моноида над типом
- Бинарного дерева (без красок)
- ????????????
- foldl за
O(1)
`
И бонусом склейка и разрезание (и, как следствие, вставка и удаление) за
O(log N)
. С сохранением сортировки
Реализовывать в коде мы её, конечно, не будем, потому что есть википедия
Заметим,
что прямое произведение пар (тип, моноид) является парой (тип, моноид)
Определим его следующим образом:
((A, ma) × (B, mb) = ((A, B), λ(a1, b1).λ(a2, b2).(ma a1 a2, mb b1 b2))
Таким образом, мы можем использовать веревку для того, чтобы вычислять свертку с произвольным числом моноидов за O(1).
Также
Мы можем использовать вместо естественной сортировки любой удобный нам порядок,
чтобы быстро (O(log N)
в худшем случае) вычислять свертку над произвольным
отрезком.
Или даже
Собрать веревку из веревок, чтобы иметь возможность делать выборки по отдельным функциям. Например, возьмем массив данных с счетчика посещаемости, и сделаем группировку по пользователю. Каждой группе выделим свою веревку, а их корни соберем в суперверевку, в которой будет агрегация по всем пользователям. К сожалению, сортировку при выборке по всем пользователям мы уже не сможем использовать (разве что отсортировать по их id)
Напрашивается вывод
Засунуть веревку в базу данных. Было бы охуенно.
Вообще говоря, такого рода агрегация - типовая задача. Мы очень часто собираем руками огромные таблицы с группировкой по некоторым параметрам, чтобы гонять агрегации для статистики уже над полуагрегированным данными. Можно делать это тригерами в БД, можно руками делать транзакции из приложения, а круто было бы просто объявить веревку в базе данных и пусть она сама все считает.
И, на последок, народная мудрость. В военное время O(log N)
= O(1)