Внешняя сортировка с кучей?

Question

У меня есть файл с большим объемом данных, и я хочу отсортировать его, храня только часть данных в памяти в любой момент времени.

Я заметил, что сортировка слиянием популярна для внешней сортировки, но мне интересно, если это можно сделать с кучей (мин или макс). По сути, моя цель состоит в том, чтобы получить 10 лучших элементов (используя произвольные числа) в списке из 100 элементов, при этом никогда не сохраняя в памяти более 10 элементов.

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

Идеи?

Спасибо!:D

Answer 1

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

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

Однако есть один аспект, который делает эти факты о сортировке неактуальными: вы говорите, что хотите определить 10 лучших элементов. Для этого вы действительно можете использовать кучу в памяти. Просто возьмите элемент из файла, поместите его в кучу и, если размер кучи превышает 10, удалите самый нижний элемент. Чтобы сделать его более эффективным, вставляйте его в кучу только в том случае, если его размер меньше 10 или он выше самого нижнего элемента, который вы затем заменяете и повторно складываете в кучу. Хранение первой десятки в куче позволяет сканировать файл только один раз, все остальное будет сделано в памяти. Использование двоичного дерева вместо кучи также будет работать и, вероятно, будет таким же быстрым, для небольшого числа, например 10, можно даже использовать массив и пузырьковую сортировку элементов на месте.

Примечание: я предполагаю, что 10 и 100 были просто примерами. Если ваши цифры действительно так низки, любое обсуждение эффективности, вероятно, является спорным, если вы не выполняете эту операцию несколько раз в секунду.

Answer 2

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

Следующее получитk предметы, используя максимальную кучу длины k, Вы можете читать файл последовательно, выполняя ввод-вывод для каждого элемента, но, как правило, загрузка данных в блоках будет намного быстрее во вспомогательный буфер длины b, Метод работает в O(n*log(k)) операции с использованием O(k + b) пространство.

while (file not empty)

    read block from file

    for (i = all items in block)
        if (heap.count() < k)
            heap.push(item[i])
        else
        if (item[i] < heap.root())
            heap.pop_root()
            heap.push(item[i])
        endif
    endfor

endwhile

Answer 3

Кучи требуют много непоследовательного доступа. Mergesort отлично подходит для внешней сортировки, потому что он делает много последовательного доступа.

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

Answer 4

Используя сортировку слиянием и передавая два значения по ссылке, вам нужно только сохранить два сравниваемых значения в буфере и перемещаться по массиву, пока он не будет отсортирован на месте.