Как оптимизировать сортировку слиянием?

Question

У меня есть два файла по 1 ГБ, каждый из которых содержит только числа в отсортированном порядке. Теперь я знаю, как читать содержимое файлов и сортировать их с помощью алгоритма сортировки слиянием и выводить его в другой файл, но меня интересует, как это сделать только с использованием размера буфера 100 МБ (я не беспокоюсь о царапинах пространство). Например, один из способов - прочитать фрагменты по 50 МБ из обоих файлов и отсортировать их, и по мере сортировки я мог бы прочитать новый элемент и продолжить процесс, пока не достигну конца обоих файлов (Может кто-нибудь дать мне представление о том, как реализовать это).

Answer 1

Похоже, вам нужно только объединить числа в ваших файлах, а не сортировать их, поскольку они уже отсортированы в каждом файле. merge часть сортировки слиянием такова:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append left to result
            break             
        else if length(right) > 0
            append right to result
            break
    end while
    return result

Теперь вы можете просто прочитать первые 50 МБ чисел из обоих файлов в двух буферах, применить алгоритм объединения, затем, когда один из буферов исчерпан (все его числа проанализированы), прочитать еще 50 МБ из необходимого файла , Не нужно ничего сортировать.

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

Answer 2

Почему бы не использовать стандартную библиотеку?

#include <fstream>
#include <iterator>
#include <algorithm>

int main()
{
   std::ifstream in1("in1.txt");
   std::ifstream in2("in2.txt");
   std::ofstream ut("ut.txt");
   std::istream_iterator<int> in1_it(in1);
   std::istream_iterator<int> in2_it(in2);
   std::istream_iterator<int> in_end;
   std::ostream_iterator<int> ut_it(ut, "\n");

   std::merge(in1_it, in_end, in2_it, in_end, ut_it);
}

Answer 3

Вы, вероятно, хотите читать / писать в разумных порциях, чтобы избежать накладных расходов ввода-вывода. Поэтому, вероятно, используйте три буфера ~ 30M, input1, input2 и output.

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

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

Кроме того, вам необходим асинхронный ввод-вывод для чтения / записи данных во время сортировки. Но это, вероятно, излишне.

Answer 4

Benchmark.Чтение по значению и чтение блока.Почувствуйте разницу!=) * * Тысяча одна

Answer 5

Поскольку вы выполняете только слияние, а не полную сортировку, это просто основной цикл слияния. Чисто последовательный ввод / вывод. Не нужно беспокоиться о буферах. Изобразите молнию на жакете. Это так просто. (Примечание: это может быть намного быстрее, если числа в файлах представлены в двоичном формате. Мало того, что файлы будут меньше, но программа будет ограничена вводом / выводом, а числа будут совершенно точными.)

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

---

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

Единственная разница между копированием и алгоритмом слияния, как у вас, заключается в том, что он читает два файла, а не один. В любом случае, базовая временная последовательность представляет собой серию операций чтения и записи в буфер, перемежающихся с небольшим количеством действий процессора. (Можно выполнить перекрывающийся ввод / вывод, чтобы действие ЦП имело место , в то время как происходит ввод / вывод, поэтому в основном задержка не буфер читает и записывает, но это было больше, когда процессоры были в 1000 раз медленнее.)

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