Какой алгоритм сортировки дает одну страницу результатов быстрее всего? (частичный набор результатов)

Question

У меня есть «большой» набор данных, в котором мне нужно отобразить первые или последние 10 строк данных и разрешить операции сортировки работать в фоновом режиме, когда пользователь просматривает первую страницу результатов.

Редактировать : Подробности о том, что означает "большой"

Я собираю данные Syslog и EventLog для нескольких хостов в доступном для поиска хранилище. Так как я буду смотреть на N компьютеров, которые разрывают / регистрируют спам в журнале событий с различными интервалами, элемент, который я ищу, может быстро расти, если он не находится в порядке по умолчанию Machine\Log\Event DateTime

Основываясь на полученном ответе, я могу заполнить вторичный индекс при вставке данных, чтобы исходное представление было очень эффективным.

Я думаю, что было бы неэффективно сначала сортировать все данные, а затем доставлять весь набор результатов, когда 80% времени пользователь заботится только о первых или последних 10 записях.

Каков наилучший алгоритм для доставки частичного набора результатов и продолжения обработки в фоновом режиме?

Исходя из этого примера , куча, быстрая сортировка и оболочка обеспечивают наилучшую производительность и могут предложить одну страницу результатов из коробки.

Как бы я сказал, когда какой-либо из этих алгоритмов готов обслуживать первую страницу? Какой порог я бы посмотрел?

Answer 1

Вы можете выбрать лучшие элементы K за O(n) время.См. http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements.. Вы можете использовать алгоритм Quickselect, чтобы выбрать первые 10 (которые поместили бы их в начало массива), сделать это снова для 10 нижних (поместить в конец массива), а затемзапускать сортировку в фоновом режиме, сортируя элементы с 10 по n-10.

На практике Heapselect работает быстрее, чем Quickselect, когда количество элементов, которые вы хотите выбрать, составляет менее 1% от общего количества элементов.,То есть, чтобы выбрать k элементов из списка n, вы должны использовать Heapselect, если k < n/100.Если k равно 10, а n - миллион, Heapselect будет намного быстрее, чем Quickselect.

Недостаток Heapselect заключается в том, что он требует O (k) дополнительного пространства.Но когда k == 10, это не имеет большого значения.

Это зависит от характера ваших данных.Если общее количество отображаемых строк обычно превышает 1000, вам следует использовать Heapselect.В противном случае используйте Quickselect.Они оба просты в реализации.

См. Когда теория встречается с практикой для получения дополнительной информации о разнице между двумя алгоритмами выбора.

Answer 2

Поиск лучших K элементов можно выполнить за время O (nlogk), что намного, намного быстрее, чем за O (nlogn), с использованием кучи или, в конечном итоге, очереди с приоритетами. Стратегия состоит в том, чтобы пройти список один раз, и на ходу сохраняйте список лучших k элементов, которые вы нашли до сих пор. Чтобы сделать это эффективно, вы всегда должны знать наименьший элемент в этом top-k, так что вы можете заменить его на элемент большего размера. Структура кучи позволяет легко поддерживать этот список без лишних усилий.

Вы также можете использовать алгоритм выбора, упомянутый в http://en.wikipedia.org/wiki/Selection_algorithm, для поиска первых k самых маленьких или самых больших записей в вашем списке. что быстрее, чем сортировка всего списка.

Я бы посоветовал вам сначала отсортировать k записей и отобразить результат, а в фоновом режиме отсортировать оставшиеся записи с помощью слияния, кучи или быстрой сортировки.

Answer 3

Исходя из этого примера, куча, быстрая сортировка и оболочка обеспечивают наилучшую производительность и могут предложить одну страницу результатов из коробки.

Для этого вамнам понадобится алгоритм, который сортирует список по порядку.Каждая итерация списка помещает следующий по величине (или наименьший) элемент в списке на свое место.Итак, после первого прохода самый маленький элемент находится в позиции 1, а после второго прохода второй самый маленький элемент находится в положении 2. Для этого вам понадобится что-то вроде сортировки выбора] 2 .

Вот проблема по сравнению с другими алгоритмами и порядком данных, они могут быть значительно лучше.Таким образом, даже если вы «быстро» получаете первые 10 записей после их сортировки, другой алгоритм мог бы отсортировать весь список за то же время.