快速遍历大型二进制文件的算法

标签 algorithm large-files binary-search

我有一个涉及读取大文件的问题需要解决,并且我大致了解如何处理它,但希望看到可能有更好的方法。

问题如下:我有几个巨大的磁盘文件(每个 64GB),每个文件都包含 2.5KB 的记录(大约 25,000,000记录总数)。除其他字段外,每条记录还具有时间戳和指示时间戳是否有效的isValid标志。当用户输入时间跨度时,我需要返回时间戳在指定范围内的所有记录。

数据的布局是这样的,对于标记为“有效”的所有记录,时间戳单调增加。无效记录根本不应该被考虑。因此,文件通常如下所示(尽管范围要大得多):

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=13, IsValid = true };
a[3]  = { Time=401, IsValid = false }; // <-- should be ignored
a[4]  = { Time=570, IsValid = false }; // <-- should be ignored
a[5]  = { Time=16, IsValid = true }; 

a[6]  = { Time=23, IsValid = true };  // <-- time-to-index offset changed 
a[7]  = { Time=24, IsValid = true };
a[8]  = { Time=25, IsValid = true };
a[9]  = { Time=26, IsValid = true };

a[10] = { Time=40, IsValid = true };  // <-- time-to-index offset changed 
a[11] = { Time=41, IsValid = true };
a[12] = { Time=700, IsValid = false };  // <-- should be ignored 
a[13] = { Time=43, IsValid = true };

如果时间戳和计数器之间的偏移量是恒定的,则查找第一条记录将是一个 O(1) 操作(我将简单地跳转到索引)。由于事实并非如此,我正在寻找一种不同的方法来(快速)找到此信息。

一种方法可能是修改后的二分搜索,但我不完全确定如何处理更大的无效记录 block 。我想我还可以创建一个“索引”来加快查找速度,但是由于会有很多这样的大文件,并且提取的数据大小将比整个文件小得多,所以我不想遍历这些文件中的每一个,逐条记录,生成索引。我在想二分搜索在构建索引时是否也有帮助。

更不用说我不确定索引的最佳结构是什么。平衡二叉树?

最佳答案

您可以使用修改后的二分搜索。这个想法是进行通常的二分搜索来找出下限和上限,然后返回有效的条目之间的内容。

修改的是当前条目无效的部分。在这种情况下,您必须找出有有效条目的两个端点。 例如,如果中点是 3,

a[0]  = { Time=11, IsValid = true };
a[1]  = { Time=12, IsValid = true };
a[2]  = { Time=401, IsValid = false };
a[3]  = { Time=570, IsValid = false }; // <-- Mid point.
a[4]  = { Time=571, IsValid = false };
a[5]  = { Time=16, IsValid = true }; 
a[6]  = { Time=23, IsValid = true };

在上述情况下,算法将返回两个点 a[1] 和 a[5]。现在算法将决定二分搜索下半部分或上半部分。

关于快速遍历大型二进制文件的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12619769/

相关文章:

java - 没有两个连续对象相同的随机选择序列

java - 如何使用 java 将十六进制转换为十进制 rgb565?

c - 为什么 minizip 不归档大文件(大于 4 GB)

algorithm - Ladder/Eggs 测试无限阶梯和无限数量的鸡蛋

java - 如何使用二进制搜索来查找具有特定权重的数组中的第一个元素(不同数组中的另一个元素)?

algorithm - 如何找到依赖树中的哪些作业可以并行运行?

c++ - 二进制搜索插入字符字符串。错误在哪里?

java - 使用 Apache Camel,如何向已经很大的文件添加一些行?

http - 为(可能)非常大的文本文件发送部分更新/添加

arrays - 二分搜索与基于键的搜索