Использование кучи для больших дисков - PullRequest
Новая
       34

Использование кучи для больших дисков

0 голосов
/ 01 июня 2019

На официальных документах Python здесь упоминается, что:

Кучи также очень полезны при сортировке больших дисков. Вы, скорее всего, все знать, что большой вид подразумевает производство «прогонов» (которые предварительно отсортированы последовательности, размер которых обычно связан с объемом памяти процессора), с последующими проходами слияния для этих прогонов, которые часто очень умно организовано.
Очень важно, чтобы начальный Сортировка производит самые длинные прогоны. Турниры - это хороший способ чтобы достичь этого. Если, используя всю доступную память для хранения турнир, вы заменяете и фильтруете предметы, которые соответствуют текущий прогон, вы будете производить прогоны, которые в два раза больше память для случайного ввода и гораздо лучше для ввода нечётко упорядоченных.

Более того, если вы выводите 0-й элемент на диск и получаете ввод, который может не вписаться в текущий турнир (потому что значение «выигрывает» последнее выходное значение), он не может поместиться в кучу, поэтому размер куча уменьшается. Освобожденная память может быть использована повторно немедленно для постройки второй кучи, которая растет в точно такая же скорость, как тает первая куча.
Когда первая куча полностью исчезает, вы переключаете кучу и начинаете новый запуск. Умный и довольно эффективно!

Мне известен алгоритм, называемый Внешняя сортировка , в котором мы:

  1. Разбейте вход на более мелкие куски.
  2. Сортировка всех фрагментов по отдельности и запись их на диск по одному.
  3. Создайте кучу и сделайте k-way слияние среди всех отсортированных кусков.

Я полностью понял внешнюю сортировку, как описано в Википедии, но не могу понять автора, когда они говорят:

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

и

Более того, если вы выводите 0-й элемент на диск и получаете ввод, который может не вписаться в текущий турнир (потому что значение «выигрывает» последнее выходное значение), он не может поместиться в кучу, поэтому размер куча уменьшается.

Что это за куча тающая ?

1 Ответ

2 голосов
/ 02 июня 2019

Таяние кучи это не вещь.Это просто слово, которое автор использует для уменьшения кучи, чтобы вытащить самые мелкие элементы.

Идея, о которой он говорит, - это умная замена для «деления ввода на куски и сортировки кусков» частивнешний видОн производит большие отсортированные куски.

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

Когда вы читаете элемент, который меньше, чем элемент, который вы уже записали, он не может войти в текущий фрагмент (это разрушит сортировку), поэтому вы помните его для следующего фрагмента.,Элементы, которые не меньше, чем последний, который вы выписали, могут быть вставлены в кучу.Они разбираются в текущем чанке, увеличивая текущий чанк.

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

...