C # N способ слияния для внешней сортировки

Question

Какой лучший способ реализовать N-способ слияния для N отсортированных файлов?

Допустим, у меня 9 отсортированных файлов по 10 записей в каждом?Как объединить эти файлы, чтобы создать большой файл с 90 отсортированными записями?

Answer 1

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

• Считайте первую строку из каждого файла, чтобы у вас было 10 строк в памяти, по одной из каждого файла.
• Поместить строки в приоритетную очередь по порядку сортировки.
• Извлечь наименьший элемент (отсортированный первым) из очереди приоритетов и записать в выходной файл.
• Считайте еще одну строку из соответствующего файла, откуда пришла строка, и поместите его в очередь с приоритетами.
• Повторяйте, пока все файлы не будут прочитаны до конца.

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

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

В C # вы можете использовать, например, SortedDictionary для реализации очереди с приоритетами.

Answer 2

Обращаясь к комментариям в другом ответе:

Если у вас переменное количество файлов, вот что я бы сделал. Это просто набросок, чтобы донести идею; этот код не компилируется, я неправильно указал имена методов и т. д.

// initialize the data structures
var priorityQueue = new SortedDictionary<Record, Stream>();
var streams = new List<Stream>();
var outStream = null; 
try
{
  // open the streams.
  outStream = OpenOutputStream();
  foreach(var filename in filenames)
    streams.Add(GetFileStream(filename));
  // initialize the priority queue
  foreach(var stream in streams)
  {
    var record = ReadRecord(stream);
    if (record != null)
      priorityQueue.Add(record, stream);
  // the main loop
  while(!priorityQueue.IsEmpty)
  {
     var record = priorityQueue.Smallest;
     var smallestStream = priorityQueue[record];
     WriteRecord(record, outStream);
     priorityQueue.Remove(record);
     var newRecord = ReadRecord(smallestStream);
     if (newRecord != null)
       priorityQueue.Add(newRecord, smallestStream);
  }
}
finally { clean up the streams }

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

Answer 3

Я бы сказал, не используйте приоритетную очередь, не используйте IEnumerable.Оба очень медленные.

Вот быстрый способ сортировки или объединения отсортированных файлов во внешней памяти:

http://www.codeproject.com/KB/recipes/fast_external_sort.aspx

Answer 4

Стратегия может зависеть от количества данных.

1. Если данные помещаются в память, вы можете прочитать все данные в списке, отсортировать их и записать
2. Если вы хотите удалить дубликаты, используйте HashSet вместо списка
3. Если он не помещается в памяти, откройте все файлы для чтения, сравните первую запись каждого файла и запишите самый низкий. Затем продвиньте файл, который вы прочитали. Переберите все файлы, пока они не будут исчерпаны и записаны в новый файл.
4. Если вы хотите удалить дубликаты, сделайте то же, что и выше, но пропустите любую запись, равную последней записанной.

Вот пример кода, который читает в N отсортированных текстовых файлах и объединяет их. Я не включил проверку дубликатов, но это должно быть легко осуществить.

Первый класс помощников.

class MergeFile : IEnumerator<string>
{
    private readonly StreamReader _reader;

    public MergeFile(string file)
    {
        _reader = File.OpenText(file);
        Current = _reader.ReadLine();
    }

    public string Current { get; set; }

    public void Dispose()
    {
        _reader.Close();
    }

    public bool MoveNext()
    {
        Current = _reader.ReadLine();
        return Current != null;
    }

    public void Reset()
    {
        throw new NotImplementedException();
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }
}

А затем код для чтения и слияния (для ясности он должен быть переработан):

// Get the file names and instantiate our helper class
List<IEnumerator<string>> files = Directory.GetFiles(@"C:\temp\files", "*.txt").Select(file => new MergeFile(file)).Cast<IEnumerator<string>>().ToList();
List<string> result = new List<string>();
IEnumerator<string> next = null;
while (true)
{
    bool done = true;
    // loop over the helpers
    foreach (var mergeFile in files)
    {
        done = false;
        if (next == null || string.Compare(mergeFile.Current, next.Current) < 1)
        {
            next = mergeFile;
        }
    }
    if (done) break;
    result.Add(next.Current);
    if (!next.MoveNext())
    {
        // file is exhausted, dispose and remove from list
        next.Dispose();
        files.Remove(next);
        next = null;
    }
}