Задачник Базовый курс EN

Слияние с надгробиями

базы данных хеш-таблица сортировка внешняя память в проде

Хранилище ключ-значение устроено как LSM-дерево: записи лежат на диске отсортированными прогонами, а фоновый процесс сливает прогоны. В каждой записи — ключ, номер записи (чем больше, тем новее) и значение. Удаление ключа записано надгробием — значением «-».

Нужно слить несколько прогонов в один. У каждого ключа в результате остаётся только самая новая версия — с наибольшим номером среди всех сливаемых прогонов. Надгробие тоже версия: если оно самое новое, ключ удалён. Но под сливаемыми прогонами лежат более старые, глубокие прогоны, которые в этом слиянии не участвуют. Надгробие нужно сохранить, если ключ встречается хотя бы в одном глубоком прогоне: там его старая версия, и без надгробия она снова станет видна. Если ни в одном глубоком прогоне ключа нет, надгробие закрывать уже нечего — его выбрасывают. Выведите слитый прогон. Среди тестов — моменты дерева из статьи, через которое прошла история git этого сайта: ключи там — пути файлов.

Вход

В первой строке — k и d: сколько прогонов сливается и сколько глубоких прогонов под ними (1 ≤ k ≤ 10, 0 ≤ d ≤ 10). Дальше k сливаемых прогонов: в первой строке прогона — число записей m, затем m строк «ключ номер значение», по возрастанию ключей. Номера всех записей различны, значение — целое число от 1 до 10⁹ или «-». Затем d глубоких прогонов: число ключей и сами ключи по одному в строке, по возрастанию. Ключ — строка без пробелов длиной до 100 символов; ключи сравниваются по байтам. Всего строк во входе не больше 2·10⁵.

Выход

В первой строке — число записей c в слитом прогоне, дальше c строк «ключ значение» по возрастанию ключей.

В первом примере README.md удалён, а его старая версия лежит глубже — надгробие остаётся. old.txt удалён, и глубже его нет — надгробие уходит. Во втором примере глубоких прогонов нет вовсе, а у b.txt надгробие старше записи в соседнем прогоне: файл создали заново.

Примеры

Пример 1

Вход

2 1
3
README.md 9 -
app.js 8 140
old.txt 7 -
3
README.md 5 2100
app.js 4 120
style.css 3 800
2
README.md
index.html

Выход

3
README.md -
app.js 140
style.css 800

Пример 2

Вход

2 0
2
a.txt 6 -
b.txt 5 10
3
a.txt 2 70
b.txt 4 -
c.txt 1 30

Выход

2
b.txt 10
c.txt 30

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Что прочитает поиск ключа README.md после слияния, если надгробие выбросить? В глубоком прогоне есть его старая версия.

2Идея

Слияние — это выбор новейшей версии каждого ключа, а потом решение о надгробиях. Новейшую версию даёт словарь «ключ → (номер, значение)», где запись заменяется, если пришла с большим номером. Надгробие с новейшим номером нельзя выбросить, пока где-то ниже лежит любая версия ключа: поиск идёт от новых прогонов к старым и остановится на первой найденной — без надгробия ею окажется старая версия, и удалённый файл воскреснет. Поэтому ключи глубоких прогонов собираем в множество и оставляем надгробие только для ключей из него.

3Разбор

Прогоны отсортированы, и в настоящих хранилищах их сливают потоком — кучей по текущим ключам, как в слиянии k списков, — чтобы не держать всё в памяти. Здесь все записи помещаются в словарь, и хватает его и сортировки ключей в конце. Множество ключей глубоких прогонов можно заменить двоичным поиском по каждому из них: они тоже отсортированы.

Настоящие хранилища решают про надгробия грубее. Самое простое правило — выбрасывать надгробия только при слиянии в самый нижний уровень: ниже ничего нет. Точнее — проверять, пересекается ли диапазон ключей глубоких прогонов с ключом. А пока надгробие не выброшено, оно занимает место и замедляет чтения: в базах с частыми удалениями «кладбища» надгробий — известная беда. В третьем тесте из истории сайта сливаются четыре прогона L0; 30 надгробий в результате остаются, потому что старые версии этих файлов лежат глубже.

3+Решение

4Сложность

O(N log N) на N записей с сортировкой в конце; потоковое слияние кучей — O(N log k) и памяти O(k).

5Типичные ошибки

Выбросить все надгробия. Результат выглядит чище, но удалённые ключи с версиями в глубоких прогонах воскресают — первый пример ловит именно это.
Оставить все надгробия. Ничего не воскреснет, но надгробия копятся вечно; здесь это неверный ответ.
Новейший по прогону, а не по номеру. Прогоны идут от новых к старым, но решает номер записи — на нём и держится правило.
Удалённый, потом созданный заново. Если после надгробия ключ записали снова, новейшая версия — значение, и надгробие исчезает вместе со старыми версиями.

Алгоритмы задачи

SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым.

запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень

2 задачи SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи