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

StackOverflow https://stackoverflow.com/questions/3814188

Вопрос

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

Это было полезно?

Решение

Похоже, тебе нужно только слияние Числа в ваших файлах, не сортируют их, поскольку они уже отсортированы в каждом файле. То 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 МБ из необходимого файла. Там нет необходимости оформить что-либо.

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

Другие советы

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

#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);
}

Вы, вероятно, хотите прочитать / писать в разумных чанках, чтобы избежать накладных расходов ввода / вывода. Поэтому, вероятно, используют три буфера ~ 30 м, вход1, ввод2 и вывод.

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

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

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

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

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

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

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

Ориентир. Читайте значение по значению и заблокировать чтение. Почувствуйте разницу! знак равно

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top