4

是否有一个库可用于在非常大的文本文件（可以是 10GB）中执行二进制搜索。

该文件是一种日志文件 - 每行都以日期和时间开头。因此行是有序的。

4

6 回答 6

4

由于不能保证行长度相同，因此您将需要某种形式的可识别行分隔符，例如回车或换行。

然后，二进制搜索模式几乎可以成为您的传统算法。查找文件的“中间”（按长度），向后查找（逐个字节）到您碰巧进入的行的开头，如行分隔符序列所标识的那样，读取该记录并进行比较。根据比较，向上或向下（以字节为单位）搜索并重复。

当您确定记录的起始索引时，请检查它是否与最后一次查找相同。您可能会发现，当您拨入目标记录时，中途移动不会让您进入另一条记录。例如，您分别有 100 字节和 50 字节的相邻记录，因此在 75 字节处跳转总是带您回到第一条记录的开头。如果发生这种情况，请在进行比较之前阅读下一条记录。

你会发现你会很快达到你的目标。

于 2010-04-13T16:23:10.260 回答
4

我开始编写伪代码来说明如何做到这一点，但我放弃了，因为它可能看起来居高临下。您可能知道如何编写二进制搜索，它真的不复杂。

您不会在图书馆中找到它，原因有两个：

  1. 这不是真正的“二分查找”——行大小不同，因此您需要调整算法（例如，查找文件的中间部分，然后查找下一个“换行符”并将其视为“中间部分”）。
  2. 您的日期时间日志格式很可能是非标准的（好吧，它可能看起来“标准”，但想一想......您可能使用 '[]' 或其他东西将日期与日志消息分开，例如 [10 /02/2001 10:35:02] 我的消息）。

总而言之-我认为您的需求太具体且太简单，无法在自定义代码中实现，以至于有人费心编写库:)

于 2010-04-13T16:40:57.030 回答
2

您需要能够流式传输文件，但您还需要随机访问。我不确定您是如何做到这一点的，但不能保证文件的每一行都包含相同的字节数。如果你有这个，你可以得到一个对象的 Stream 并使用 Seek 方法在文件中移动，然后你可以通过读取构成一行的字节数来进行二进制搜索。但同样，这仅在行的字节数相同时才有效。否则，你会跳进跳出行的中间。

就像是

byte[] buffer = new byte[lineLength];
stream.Seek(lineLength * searchPosition, SeekOrigin.Begin);
stream.Read(buffer, 0, lineLength);
string line = Encoding.Default.GetString(buffer);
于 2010-04-13T15:36:14.043 回答
0

在您为文件中的每个换行符在内存中保存一个 Int64 的约束下，这应该不会太糟糕。这实际上取决于文本行的平均长度，给定每行 1000 个字节，您正在查看大约 (10,000,000,000 / 1000 * 4) = 40mb。非常大，但可能。

所以试试这个：

  1. 扫描文件并将每个换行符的序号偏移量存储在列表中
  2. 使用自定义比较器对列表进行二进制搜索，该比较器扫描到文件偏移量并读取数据。
于 2010-04-13T16:23:58.073 回答
0

如果您的文件是静态的（或很少更改）并且您必须对其运行“足够”的查询，我相信最好的方法是创建“索引”文件：

  1. 扫描初始文件并获取文件的日期时间部分以及它们在原始文件中的位置（这就是为什么必须是相当静态的）对它们进行一些编码（例如：unix 时间（全 10 位）+纳秒（零填充 4位）和行位置（零归档 10 位）。这样您将获得具有一致“行”的文件

  2. 在该文件上执行二进制搜索（您可能需要有点创意才能实现范围搜索）并在原始文件中获取相关位置

  3. 从给定位置开始直接从原始文件读取/读取给定范围

您已经使用 O(log(n)) 运行时进行范围搜索:)（并且您已经创建了原始数据库功能）

不用说，如果文件数据文件更新“过于”频繁，或者您没有对索引文件运行“足够”查询，那么您最终会花费更多时间来创建索引文件而不是从查询文件中保存.

顺便说一句，使用此索引文件不需要对数据文件进行排序。由于日志文件往往只追加和排序，您可以通过简单地创建仅包含数据文件中 EOL 标记（零填充的 10 位）位置的索引文件来加快整个过程 - 这样您就可以执行直接在数据文件上进行二进制搜索（使用索引文件来确定原始文件中的查找位置），如果将行附加到日志文件中，您可以简单地将其 EOL 位置添加（附加）到索引文件中。

于 2013-06-18T11:37:00.403 回答
-2

List 对象有一个 Binary Search 方法。

http://msdn.microsoft.com/en-us/library/w4e7fxsh%28VS.80%29.aspx

于 2010-04-13T15:29:08.830 回答