合并大文件的算法

Question

我有几个事件的日志文件(每行一个事件).日志可能会重叠.日志是在可能的多个时区的不同客户端计算机上生成的(但我假设我知道时区).每个事件都有一个标准化为公共时间的时间戳(通过使用适合于日志文件的时区实例化每个日志解析器日历实例,然后使用getTimeInMillis获取UTC时间).日志已按时间戳排序.多个事件可以同时发生,但它们绝不是平等的事件.

这些文件可能相对较大,如单个日志中的500000个事件或更多,因此将日志的全部内容读入简单的Event []是不可行的.

我正在尝试做的是将每个日志中的事件合并到一个日志中.它有点像mergesort任务,但每个日志已经排序,我只需将它们组合在一起.第二个组件是可以在每个单独的日志文件中看到相同的事件,我想在文件输出日志中"删除重复事件".

这可以"就地"完成,例如,顺序处理每个日志文件的一些小缓冲区吗？我不能简单地将所有文件读入Event [],对列表进行排序,然后删除重复项,但到目前为止,我的有限编程功能只能让我将其视为解决方案.当我同时从每个日志中读取事件时,是否有一些更复杂的方法可用于执行此操作？

Answer 1

1. 从每个日志文件中读取第一行

2. 环

   一个.找到"最早"的行.

   湾 将"最早"行插入主日志文件

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

您可以检查b和c之间的重复项,推进每个文件的指针.

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