c - 在 C 中对文件运行二进制搜索的最快方法？

Question

例如，假设我想在文件中查找特定的单词或数字。内容按排序顺序（显然）。由于我想对文件运行二进制搜索，因此将整个文件复制到数组中然后运行二进制搜索似乎真的是浪费时间......我已经有效地将其设为线性时间算法，因为我'在运行搜索之前，我必须花费 O(n) 时间复制该死文件。

有没有更快的方法来做到这一点？是否有类似 lseek 的东西可以使用行而不是字节？

如果没有，我是否最好只进行线性搜索（假设我在整个程序期间只运行一次搜索）？

Answer 1

你不能按行搜索。仔细想想就很明显了。

但是您可以对文本文件进行某种二进制搜索。

你要做的是：

• 统计文件以获取长度或搜索到末尾并获取位置。
• 内存映射文件。
  （我认为这是最好的，但如果必须，您可以使用 lseek 和阅读。）
• 寻找文件的中间，减去你的平均行长。只是猜测。
• 向前扫描换行符，除非您在位置 0。
• 阅读您的台词并进行比较。
• 重复 1/4 或 3/4、1/8、1/16 等。

Answer 2

基于磁盘的二分搜索至少在最初需要是“块感知的”，即知道无论您是否读取一大堆的单个字节，I/O 成本都是相同的。另一个需要注意的是，与顺序读取操作相比，查找操作的成本相对较高。

它可以通过以下几种方式使用对磁盘 I/O 特性的这种认识：

• 在搜索结束时，倾向于线性搜索（扫描）而不是搜索。
• 在开始时检查块中的第一个和最后一个元素，这可能有助于推断下一个拆分的更好猜测
• 缓存文件中不同位置的一些项目的树（甚至是简短的平面列表）（有点像正式 btree 结构中的中间节点）
• 声明并使用适当的缓冲区大小

Answer 3

如果文件很小，比如不到几百千字节，那么将整个文件读取（或虚拟内存映射）到内存中几乎肯定会更快。这是因为执行多个 i/o 操作来查找和传输的开销比仅读取整个文件要糟糕得多，这是大多数程序所做的并且大多数操作系统都假设已完成。

除非所有行的长度相同，或者具有非常可预测的长度，否则很难找到第 #n 行。但是，为了执行二进制搜索，我会在二进制搜索中使用字节偏移量，并在偏移量之前和之后读取 100 个字节（如果单词的长度都小于 100 个字符）——总共 200 个字节。然后扫描它中间前后的换行符以提取单词。

Answer 4

是的，您可以 lseek 但如果每行每个单词/数字的大小是固定的，这将有所帮助，如果不是这种情况，则更有可能，那么您必须按文件大小查找并查找最近的单词开头仍然达到接近二进制搜索的典型 O(log n) 时间复杂度。

Answer 5

不会有“lseek”函数，因为文件命令没有“行”的概念这个概念存在于与原始文件命令不同的抽象层中。

至于它是否更快，答案将取决于许多因素，包括文件大小、磁盘驱动器速度和可用 RAM 量。如果它不是一个大文件，我的猜测是将整个文件加载到内存中会更快。

如果它是一个大文件，我会使用二进制搜索算法将其缩小到更小的范围（例如，几兆字节），然后加载整个块。

Answer 6

这里有如此多的性能权衡，以至于在您对典型数据进行测量之前，不可能知道什么是有意义的。

如果您要维护此代码，它需要很简单。 如果搜索很少或文件很小，请使用线性搜索。如果成本真的很重要，您将不得不做一些实验。

在线性搜索之后我会尝试的第二件事是mmap对文件进行扫描以查找换行符。这确实需要线性时间，但strchr可能非常快。如果您可以保证文件以换行符结尾，这会有所帮助。一旦你划定了界限，你可以通过二分查找来减少比较的次数。

您应该考虑的另一个选项是 Boyer-Moore 字符串搜索。这是一种亚线性时间搜索，根据搜索模式的大小，它可能比对数二分搜索更快。Boyer-Moore 特别擅长处理长搜索字符串。

最后，如果您确定二进制搜索确实很好，但识别行是性能瓶颈，您可以预先计算每行的起始位置，并将这些预先计算的位置以二进制格式存储在辅助文件中。

我觉得只做一个预测很舒服：几乎可以肯定的是，避免一次读一行像readline()or这样的东西是值得的fgets()，因为这种策略总是涉及调用malloc()来保存该行的内容。调用malloc()每条线路的成本可能会超过任何搜索或比较的成本。

Answer 7

如上所述，由于文件是文本文件，因此无法可靠地预测文件中给定行开始的字节。ersatz 二进制搜索的想法是一个非常好的想法。但考虑到现在顺序 I/O 有多快以及随机 I/O 有多慢，除非文件很大，否则它真的不会为您节省很多。

正如您所提到的，如果您要阅读它，您不妨边走边线性搜索它。所以这样做，在阅读时使用修改后的 Boyer-Moore 搜索，你会做得很好。