Разбор задач с конференции Hydra — балансировка нагрузки и in-memory хранилища
Решение на поверхности: отсортировать все документы (например, с помощью quicksort), затем взять N+S документов. В таком случае сложность сортировки в среднем — O (M lg M), в худшем — O (M2).
Очевидно, что сортировать все M документов, чтобы затем взять только небольшую часть от них — неэффективно. Чтобы не сортировать все документы, подойдёт алгоритм quickselect, который выберет N+S нужных документов (их можно будет отсортировать любым алгоритмом). В этом случае сложность в среднем уменьшится до O (M), а худший случай останется тем же.
Однако, можно сделать ещё эффективнее — воспользоваться алгоритмом binary heap streaming. В этом случае первые N+S документов складываются в min- или max-heap (в зависимости от направления сортировки), а затем каждый следующий документ сравнивается с корнем дерева, где содержится минимальный или максимальный на текущий момент документ, и при необходимости добавляется в дерево. В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O (N lg N), сложность в среднем — O (N), как и при использовании quickselect.
Однако heap streaming оказывается эффективнее за счёт того, что на практике большую часть документов получается отбросить, не перестраивая кучу, после единственного сравнения с её корневым элементом. Такая сортировка реализована в документной in-memory базе данных Zebra, разработанной и используемой в Контуре.
