合并大文件的算法

Question

我有几个事件日志文件（每行一个事件）。这些日志可能会重叠。这些日志是在不同的客户端机器上生成的，可能来自多个时区（但我假设我知道时区）。每个事件都有一个时间戳，通过使用与日志文件相应的时区实例化每个日志解析器的日历实例，并使用getTimeInMillis获取UTC时间来将其标准化到公共时间。日志已按时间戳排序。多个事件可以同时发生，但它们绝对不是相等的事件。

这些文件可能相对较大，例如单个日志中有500,000个或更多事件，因此将日志的整个内容读入简单的Event[]中是不可行的。

我试图做的是将每个日志的事件合并到一个日志中。这有点像归并排序任务，但每个日志已经排好序，我只需要将它们组合起来。第二个组成部分是同一事件可能在每个单独的日志文件中出现，我希望在文件输出日志中“删除重复事件”。

这是否可以“原地”完成，即顺序地处理每个日志文件的一些小缓冲区？我不能简单地将所有文件读入Event[]，对列表进行排序，然后删除重复项，但迄今为止，我的有限编程能力只使我看到这个作为解决方案。在同时从每个日志中读取事件时，我是否可以使用更复杂的方法来完成此操作？

- Josh

---

哦，老兄！“归并排序”这个词让你想起了什么？ ;) - Vladimir Dyuzhev

Answer 1

1. 从每个日志文件的第一行开始阅读

2. 循环

   a. 找到“最早”的行。

   b. 将“最早”的行插入主日志文件

   c. 从包含最早行的文件中读取下一行

您可以在b和c之间检查重复项，为这些文件中的每个文件推进指针。

- Adam Tegen

Answer 2

当然-打开每个日志文件。将每个文件的第一行读入到一个“当前”行的数组中。然后反复从当前数组中选择时间戳最低的行。将其写入输出，并从适当的源文件中读取新行以替换它。

以下是Python示例，但它也可以作为良好的伪代码：

def merge_files(files, key_func):
    # Populate the current array with the first line from each file
    current = [file.readline() for file in files]
    while len(current) > 0:
        # Find and return the row with the lowest key according to key_func
        min_idx = min(range(len(files)), key=lambda x: return key_func(current[x]))
        yield current[min_idx]
        new_line = files[min_idx].readline()
        if not new_line:
            # EOF, remove this file from consideration
            del current[min_idx]
            del files[min_idx]
        else:
            current[min_idx] = new_line

- Arachnid

---

真是太棒了。 - datatraveller1

Answer 3

请查看此链接：http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• 使用基于数组的堆。此堆/数组中的元素数量将等于您拥有的日志文件数量。

• 从所有文件中读取第一条记录并将其插入到堆中。

• 循环直到（任何一个文件中没有更多记录）

      > 从堆中删除最大元素
      > 将其写入输出
      > 从先前的最大元素所属的文件中读取下一条记录
          如果该文件中没有更多记录
              从文件列表中删除它
              继续
      > 如果它与（先前的）最大元素不同，则将其添加到堆中

现在你已经将所有事件记录到一个日志文件中，它们已经排序，并且没有重复的记录。该算法的时间复杂度为(n log k)，其中n是总记录数，k是日志文件数。

在读写文件时，应使用缓冲读取器和缓冲写入器对象来最小化磁盘读写次数，以便优化时间。

- user130198

Answer 4

我们需要按时间顺序合并多个日志文件，每个日志条目有多行（Java应用程序经常这样做-它们的堆栈跟踪相同）。我决定实现一个简单的shell+perl脚本。它可以完成我们的任务。如果您对此感兴趣，请点击链接http://code.google.com/p/logmerge/。

- jsxt

Answer 5

或者你可以从 Awstats 借用一个日志合并实用工具，它是一个开源的网站统计工具。

logresolvemerge.pl 是一个 perl 脚本，它可以合并多个日志文件：你甚至可以使用多个线程来合并日志文件（需要有 Perl 5.8 版本以支持多线程使用）。为什么不尝试使用现成的工具而不是自己构建一个呢？

- anjanb

---

这个项目是用Java编写的，我不想进行系统调用或需要perl。此外，我不会将信息写入日志文件，而是定期处理合并结果的输出。这是一个业余项目，我想学习如何自己完成它。 - Josh

Answer 6

从两个源文件中每次只读取一行。 比较这两行并将较旧的一行写入输出文件（然后进入下一行）。 重复此过程，直到您已经合并了两个文件。

并确保删除重复项 :)

我想这段C#代码可以说明这种方法：

        StringReader fileStream1;
        StringReader fileStream2;
        Event eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
        Event eventCursorFile2 = Event.Parse(fileStream2.ReadLine());

        while !(fileStream1.EOF && fileStream2.EOF)
        {
            if (eventCursorFile1.TimeStamp < eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
            }
            else if (eventCursorFile1.TimeStamp == eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }
            else
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }  
        }

中断条件并不完全正确，因为这只是快速而粗略的处理，但它应该看起来相似。

- Tigraine