2

我有一个大日志文件，其中的记录按时间排序。每条线都有时间。我需要找到时间 T1 和时间 T2 (T1 <= T2) 之间的所有记录。我可以逐行扫描整个文件并找到 T1 的起始行，将其复制到缓冲区中，然后扫描下一行，直到到达结束时间 T2。这会起作用，但效率不高。

我想知道是否可以使用二进制搜索来定位时间为 T1 和 T2 的行。但我不确定如何确定以下内容：

  1. 文件的中间行
  2. 如何确定我们应该传递给的偏移量lseek()？

是否可以对文件使用二进制搜索？

4

4 回答 4

1

让我们假设，您的行在平均长度附近都是合理的（这意味着没有行会占用一半左右的日志），这将使二进制搜索变得可行。

接下来，我还将假设您将具有以下功能：

//find the first start of a new log line after (or including) position start
//return the last position of the file if no start could be found
streampos findNextLineStart(ifstream &file, streampos start);
//extract the data as a timestamp from a line
int extractDate(ifstream &file, streampos lineStart);

通过这些功能，我们可以实现以下功能：

//find the position of the first line whose date is bigger than the given
streampos lower_bound(ifstream &file, int date)
{
  file.seekg(0, ios::end);
  streampos begin = 0, 
            end = file.tellg();
  while(begin < end)
  {
     streampos cur = (begin + end) / 2;
     streampos start = findNextLineStart(file, cur);
     //was a line start found?
     if(start < end)
     {
        int lineDate = extractDate(file, start);
        if(lineDate < date)
          begin = start;
        else
          end = start;
     }
     else
       //narrow the bound as no line was found
       end = cur;
  }
  return begin;
}

我不保证这会起作用（在所有极端情况下），但它勾画了整体实现。一个人会使用另一个函数upper_bound，使用那些你可以得到在你的范围内的行的开始和结束。

于 2012-08-27T19:15:34.217 回答
1

首先，您可能不想进行二分搜索来查找范围内的最后一条记录。找到 T1 后，您会线性读取记录，直到找到超出所需范围的记录，因此您实际上只需要找到该范围内的第一条记录。

此外，您实际上并不需要通过查找确切的第 n/2 条记录来实现二进制搜索。如果您只是寻找两个当前边界之间的字节，找到下一条完整记录并从中更新您的边界，那么应该没问题。

于 2012-08-27T19:16:38.107 回答
1

如果您有足够的地址空间，请考虑使用内存映射文件。它们往往是最简单、最有效的方法之一。使用 boost::iostreams::mapped_file 以获得可移植性。

于 2012-08-27T18:50:11.243 回答
0

你不需要中线。相反，您可以取中间字符，然后一次向后移动一个字符，直到找到换行符；那么你知道你有当前行的开始。如果该行的时间戳在未来太远，那么您可以丢弃该行及其之后的所有内容。如果它的时间戳在过去太远，丢弃它和它之前的所有东西。您可以重复此操作，直到找到所需的行。

这是标准的二分搜索算法。在二分查找中，您并不真的需要中间线 - 有大约在中间的东西就足够了。在某些极端情况下它可能会很慢，其中某些行比其他行长得多，但通常它会足够快。

于 2012-08-27T19:10:41.720 回答