从 10 亿位数字里查找指定的数字，怎样才能快一些？

[grimpil]

从网上下一个 950M 的 txt 文件，里面保存的是圆周率小数点后的 10 亿位数字。想使用 python 查找某个指定的 6 位或 8 位数字在其中的位置，现在直接读文件后用 str.find()查找实在太慢了，请教各位有什么比较快的办法吗？

文件下载地址： https://stuff.mit.edu/afs/sipb/contrib/pi/pi-billion.txt

[renmu123]

用滑动窗口应该能稍微快一点

[Ediacaran]

000 ～ 999 所在位置索引一个表

[Junzhou]

kmp

[vvhhaaattt]

没有限制的话，空间换时间，类似 ngram 索引

[hahasong]

读取文件了，直接操作内存，分片多线程查找

[cclin]

KMP 么

[radiocontroller]

字符串查找子串，kmp 算法

[aircjm]

盲猜从圆周率里面取日期

[SmiteChow]

倒排

[cclin]

我把文件下载下来了，用 str.find() 挺快的呀，读取文件 3.66s ，查找 0.007s

[Vegetable]

都是什么宰牛刀啊都，直接全量塞数据库啊！才多大点啊

[3dwelcome]

PI 属于随机数那种，索引都不好建。

怕是没什么好办法。只能挨个查找。

[ppcoin]

@Vegetable 算法题哥哥

[xx6412223]

都是 O(n),
事先加载文件并事先分段并多线程

[hidemyself]

楼上说 kmp 的有没有看过 python 对于 find 的实现哇。。

[Vegetable]

@ppcoin 这是题吗，没看出来啊，这种问题最优解就是空间换时间，再怎么做不还是索引吗

[nazor]

有个数据结构叫后缀数组，特别适合你提出的这种文本不变，模式串不同的查询需求。

[oOoOoOoOoOo]

@hidemyself

请看 in 的实现

[oOoOoOoOoOo]

分片 线程查找

[3dwelcome]

“这是题吗，没看出来啊，这种问题最优解就是空间换时间，再怎么做不还是索引吗”

问题的关键，是如何去建索引。完全乱序的数字，没办法建立有效的索引结构。