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

Question

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

Answer 1

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

#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 5

Бенчмарк. Прочитайте значение по значению и прочитайте блок. Почувствуйте разницу! =)