C#N方式合并为外部排序

Question

什么是为N个排序文件实现N路合并的最佳方法？

假设我有9个已排序的文件,每个文件有10个记录？如何合并这些文件以创建包含90个已排序记录的大文件？

Answer 1

我假设你的例子中可能会有更多的数据.如果您可以同时打开所有文件,则可以使用此算法:

• 从每个文件中读取第一行,因此内存中有10行,每行有一行.
• 按排序顺序将行放入优先级队列.
• 从优先级队列中取出最少的元素(先排序)并写入输出文件.
• 从该行所来自的相应文件中再读一行,并将其放入优先级队列.
• 重复,直到所有文件都被读到最后.

请注意,您不必一次将所有文件读入内存,因此如果您有合理数量的大文件,这将很有效,但如果您有大量小文件则不行.

如果您有许多小文件,则应将它们合并为组以为每个组创建单个输出文件,然后重复此过程以合并这些新组.

在C#中,您可以使用例如a 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

策略可能取决于数据量。

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