C#外部排序中的N路合并

Question

如何实现N路归并以合并N个有序文件？

假设我有9个每个都有10条记录的有序文件，我该如何将这些文件合并成一个90个有序记录的大文件？

- user262102

---

有重复记录还是没有重复记录？ - Bobby

什么阻止您进行内存排序并写入文件？换句话说，您的约束条件是什么？ - Aryabhatta

我倾向于说，加载或仅追加所有9个文件并重新排序。考虑到文件访问的开销，我想不出任何好的理由尝试在合并时交错数据文件。如果您正在处理大于可用内存的总记录负载，则情况更为复杂。 - Lazarus

由于文件大小超过2GB，因此无法在内存中进行操作，无论是否存在重复项。 - user262102

Answer 1

回答中提到的问题：

如果你有一个可变数量的文件，这是我要做的。这只是为了让大家理解的草图；这段代码不能编译，我的方法名写错了等等。

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

这样说是否清晰明了？你只需不断从优先队列中取出最小的元素，并用该流中的下一个记录替换它（如果有的话）。最终，队列将为空，你就完成了。

- Eric Lippert

---

一个问题是我的记录是一个字符串数组，我不能将其用作字典的键。我需要这样做，因为我解析CSV文件以保留每个字段中的值，并根据用户提供的列作为键，使用快速排序找出最小的记录。希望清楚明白，所以我无法使用上述算法。还有其他想法吗？ - user262102

创建一个实现该逻辑的比较器对象，并将其作为排序函数传递给排序字典。 - Eric Lippert

这是一个非常简单的算法实现，但请注意使用_SortedDictionary_意味着如果您的输入中有重复数据，它将抛出异常。因此，要么使用_IPriorityQueue_，要么如果您不想要重复项，则在插入之前检查其是否存在。 - MaYaN

Answer 2

我假设你的例子中可能有更多的数据。如果你可以同时打开所有文件，你可以使用以下算法：

• 从每个文件中读取第一行，这样你就有了10行内存，每个文件一行。
• 按排序顺序将这些行放入优先队列中。
• 从优先队列中取出最小的元素（排在最前面的）并写入输出文件。
• 从相应文件中读取另一行并将其放入优先队列中。
• 重复以上步骤，直到所有文件都读取完毕。

注意，你不必一次性将所有文件读入内存，所以如果你有一个合理数量的大文件，这种方法会很有效，但是如果你有很多小文件，这种方法就不太适用了。

如果你有很多小文件，你应该将它们分组合并成一个输出文件，然后重复这个过程来合并这些新的组。

在C#中，你可以使用SortedDictionary来实现优先队列。

- Mark Byers

---

如果您一次只读取一行，那么在文件扇区之间来回切换会产生显着的磁盘开销吗？似乎为每个文件读入数据缓冲区是一个重要因素。 - tbischel

嘿，感谢您的快速回复。这就是我打算使用的算法。所以这里是下一个问题我有一个列表，其中包含示例中的9个临时文件名。但是，每次根据原始文件中的数据和用户指定的内存情况，这个数字可能会有所不同。如何根据从原始文件创建的排序文件数量拥有可变数量的打开流？ - user262102

@user262102：创建一个List<Stream>。将流添加到列表中。使用foreach循环遍历流列表。完成后不要忘记关闭所有流。 - Eric Lippert

@tbischel：现代磁盘控制器具有大缓存和许多智能功能。除非实际测试表明存在问题，否则不必担心它。 - Eric Lippert

@iser262102：使用排序字典作为优先队列的建议是很好的。你可以将字典用作从记录到生成该记录的流的映射。我会画一个草图。 - Eric Lippert

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

- Mikael Svenson

---

谢谢，请查看我的上面的评论。 - user262102

Answer 4

我会建议不要使用优先队列，也不要使用IEnumerable。这两个都非常慢。

以下是一种在外部存储器中快速排序或合并已排序文件的方法：

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

- Stefan Savev

---

大家好， 谢谢你们的回复，我使用归并排序算法实现了它。对于我的 QA 目的来说，它足够快了。这个程序比较两个文件（每个文件约 300MB），每个文件都有接近3000万个单元格，只需要不到2分钟就能完成。这包括了归并排序和随后的比较所用的时间。谢谢， Bhavin - user262102