Хабрахабр

Разбор задач с конференции Hydra — балансировка нагрузки и in-memory хранилища

В таком случае сложность сортировки в среднем — O(M lg M), в худшем — O(M2). Решение на поверхности: отсортировать все документы (например, с помощью quicksort), затем взять N+S документов.

Чтобы не сортировать все документы, подойдёт алгоритм quickselect, который выберет N+S нужных документов (их можно будет отсортировать любым алгоритмом). Очевидно, что сортировать все M документов, чтобы затем взять только небольшую часть от них — неэффективно. В этом случае сложность в среднем уменьшится до O(M), а худший случай останется тем же.

В этом случае первые N+S документов складываются в min- или max-heap (в зависимости от направления сортировки), а затем каждый следующий документ сравнивается с корнем дерева, где содержится минимальный или максимальный на текущий момент документ, и при необходимости добавляется в дерево. Однако, можно сделать ещё эффективнее — воспользоваться алгоритмом binary heap streaming. В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O(N lg N), сложность в среднем — O(N), как и при использовании quickselect.

Такая сортировка реализована в документной in-memory базе данных Zebra, разработанной и используемой в Контуре. Однако heap streaming оказывается эффективнее за счёт того, что на практике большую часть документов получается отбросить, не перестраивая кучу, после единственного сравнения с её корневым элементом.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть