Меня интересует одна тема, предположим, что у нас есть восемь файлов, каждый из которых содержит 1 миллиард целых чисел, и мы должны объединить эти файлы в 8 миллиардов целых файлов, все они в каждом файле отсортированы , Конечно, задача проста, если мы делаем 8-ми слияние, но мой вопрос в том, важно ли это упорядочивать файлы, в каком порядке мы должны делать комбинацию на них? Например, вначале вместо объединения первого и второго файлов создайте новый файл M и объединитесь с третьим файлом, возможно, иногда сочетание второго и третьего, а затем с первым будет более выгодным? Я думаю, мой вопрос ясен. Имеет ли значение упорядочение файлов во время процедуры слияния? Если да, то как мы можем выбрать оптимальный?Заказ файлов во время mergesort
ответ
Возможно, оптимальным вариантом является сортировка с 8 путями без промежуточных файлов. Откройте 8 дескрипторов файлов, найдите наименьшее целое число из всех 8, напишите это в выходной файл и прочитайте следующее целое число из этого файла. Вероятно, вы могли бы управлять 8-элементным массивом из ваших 8 источников (удерживая дескриптор файла и прочитанное последнее значение), используя сортировку вставки.
Что касается заказа, если вы могли объединять только два файла одновременно, я бы, вероятно, сначала объединил наименьшие файлы. Упростите свой пример, и вы можете понять, почему.
Предположим, у вас есть 3 файла, в них 1, 2 и 100 записей.
Если вы объедините 1 & 2 в временный файл с 3 записи, а затем объединить, что с 100, вы прочитали 106 записей и написано 103.
Если вы вместо того, чтобы объединить 1 & 100 во временный файл с 101 записями, а затем слить его с помощью 2, вы прочитаете 204 записи и написали 103.