在已排序的文本文件中实现二进制搜索?

问题描述 投票:0回答:2

有没有一种方法可以直接在其中复制文件数据来实现搜索?

c++ file search
2个回答
0
投票

理论上:是的,但效率很低。

我建议将数据放在一个sqlite数据库中,这样你仍然只有一个文件,但可以很好地查询/搜索条目。


-1
投票

tl;博士:是的,但通常不值得

您忽略了文本文件的排序方式,确切地说,是否存在转义字符,引号,多字节字符等等 - 这些都会影响答案。

但是我们做出以下假设:

  • 普通的可打印ASCII文本,每个字符串中没有换行符。
  • 换行符(即0xA字符)分隔字符串。

对于一组假设,这仍然是不够的,因为 - 也许某些字符串比其他字符串长得多?事实上,整个n字符串的非极端情况怎么样呢,但是其中一些字符占据了大部分字符?如果您开始在文件中对字符进行采样,则需要前后线性地,至少向单个字符串的两个边缘前进(或转发,直到您按两次换行)。

所以让我们添加更多的假设,虽然坦率地说 - 它们非常无效:

  • 您知道最小最小和最大最大字符串长度。
  • 最小长度与最大长度之比R不是很​​高

这使得从理论上讲,从文件中的某个任意点开始读取并查找完整的字符串至少是合理的。但是,文件通常在磁盘上;和磁盘由块访问。因此,为了从文件中读取单个字符,您需要读取整个B大小的块(将B视为1 KiB作为一个合理的例子)。我们假设Max <B,否则你就处于大字符串的情况下。

另一个要点是磁盘延迟很高。对于磁性(或光盘)尤其如此,您可以在一次读取时等待多达10毫秒!如果按顺序阅读,则无需“寻找”或查找您感兴趣的位置,并且可以利用磁盘的全部带宽。这对SSD来说不是一个问题,但它仍然不容忽视。

所以,正如你所看到的,你的二进制搜索有相当多的开销。可能仍然值得你的文件相对于Min,Max,R和B非常大。所以在几千兆字节的文件中,我当然会考虑它。否则 - 可能不值得打扰。

© www.soinside.com 2019 - 2024. All rights reserved.