算法用于合并大的文件

StackOverflow https://stackoverflow.com/questions/128043

  •  02-07-2019
  •  | 
  •  

题

我有几个日志的文件的活动(一个事件的每线)。本记录可能重叠。日志产生的对独立的客户机从可能的多个时区(但我认为我知道时间区)。每个事件都有时间戳，被归入一个共同的时间(由instantianting每日志的分析程序的日历实例时区适当的登录文件，然后使用getTimeInMillis得到UTC时间)。日志都已经按时间戳。多个事件可能发生在同一时间，但他们不是平等的活动。

这些文件可以相对较大，为，500000事件或更多在一个日志，所以读取全部内容的记录到一个简单的事件[]是不可行的。

我想做的是合并的事件从每个日志成一个单一的记录。它是有点像一个成了归并排序的任务，但是每个日志是已排，我只是需要把它们结合起来。第二件是，同一事件可以看到在每个独立的日志文件，我想要"清除重复活动"的文件输记录。

这样做可以"地方"，因为，顺序作了一些小缓冲区的每个日志的文件？我不能简单地读取所有文件纳入一个事件[]、排序的名单，然后删除重复，但迄今为止我编程功能只有使我能够看到这样的解决方案。是有一些更复杂的方法，我能用来做这个，因为我读的事件从每个日志，同时?

有帮助吗？

解决方案

  1. 读取第一线，从每个日志文件

  2. 循环

    a.找到"尽早"的路线。

    b.插入"早期"行进主日志文件

    c.阅读下一个线从该文件所载的最早线

你可以检查重复之间的b和c，推进针对每个这些文件。

其他提示

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

这是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

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

  • 使用堆(基于一个阵列)。这些元素在这堆/array将等于该数目的记录文件。

  • 读取第一记录所有文件和它们插入你的堆。

  • 循环直到(没有更多的记录在的任何文件)

      > remove the max element from the heap
      > write it to the output
      > read the next record from the file to which the (previous) max element belonged
          if there are no more records in that file
              remove it from file list
              continue
      > if it's not the same as the (previous) max element, add it to the heap

现在你有你的所有事件在一个日志文件，它们都是根据，并且没有重复。时间复杂的算法(n记录k)其中n为的记录总数和k的数量日志的文件。

你应该使用缓冲阅读器和缓冲作家的对象，当读到文件的数量减至最小磁盘读写，以便优化对的时间。

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

从两个源文件一次只读一行。 比较这些行并将旧的行写入输出文件（并前进到下一行）。 这样做直到你到达两个文件的末尾并且你已经合并了文件。

并确保删除重复项：）

我想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());
            }  
        }

休息条件不完全正确，因为这只是Quick'n'dirty，但看起来应该类似..

或者您可以从Awstats借用日志合并实用程序，这是一个开源网站统计工具。

logresolvemerge.pl 是一个可以合并多个日志文件的perl脚本：您甚至可以使用多个线程来合并日志文件（需要使用perl 5.8进行多线程使用）。为什么不尝试使用现成的工具而不是构建一个？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top