Как добавить данные в кучу отсортированных файлов

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

Кроме того, я бы сказал, что сортировку 32-битных целых чисел лучше всего выполнять с результатом уже в виде счетчиков, особенно в очень больших масштабах, таких как «несколько жестких дисков». битовое пространство, поэтому хранение 64 бит * 2 ^ 32 может быть меньше, чем, скажем, 2 ^ 33 32-битных нулей, затем 2 ^ 32 единицы, затем...

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

Однако в мире жестких дисков операции чтения и записи намного дороже, чем в ОЗУ, поэтому вставка данных куда-либо, а затем смещение (перезапись) остальных данных кажется непомерно дорогим.

Внешняя сортировка предназначена для случаев, когда у вас недостаточно памяти (или в большинстве случаев достаточно «на процесс»), чтобы сделать это внутри. Нередки случаи, когда наборы данных слишком велики для одновременного хранения в памяти. Таким образом, вы принимаете более высокую стоимость сортировки ввода-вывода во время выполнения.

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

Если вы хотите использовать тот факт, что большая часть массива уже отсортирована, и у вас есть место в памяти для этого, то сортировка вставленных элементов и объединение их со списком элементов, которые больше, чем его наименьший элемент, является хороший, быстрый способ сделать это. НАПРИМЕР:

ДИСК:

1 2 3 4 5 6 8 10 11 12

Вставки: 9 7 13

Отсортируйте вставки:

7 9 13

Найдите подмножество отсортированного списка на диске, которое подходит: 8 10 11 12

Объедините элементы в (как в Mergesort:)

7 8 9 10 11 12 13

Скопируйте их обратно на диск:

1 2 3 4 5 6 7 8 9 10 11 12 13

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

1 2 3 4 .. 1000 1002 1003... 999,998, 1,000,000...

как ваш список на диске и

1001, 999,999

как ваши вставки. В этой ситуации вам нужно просмотреть каждый элемент, вычислить количество элементов в списке вставки, которые меньше этого элемента, а затем сделать это. В этом простом примере наивный счетчик работает очень быстро — вы можете видеть, что для 1 000 0000 требуется два прыжка. Если количество вставок может быть сравнительно большим, вы можете отсортировать свои вставки, а затем использовать двоичный поиск для этого элемента, чтобы найти, где может находиться каждый элемент в вашем большем массиве. Это даст вам информацию о том, сколько элементов вы можете скопировать. Таким образом, соответствующие значения прыжка для вершины будут:

0 0 0 0 ... 0 1 1 ... 1 2

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