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

[grimpil]

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

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

[rrfeng]

那要查的数字范围 6/8 的前 N 位枚举出来遍历一下做位置索引，N 取值可以做个测试找到空间和时间的平衡点。

盲猜你要查生日，那查询目标才没几个，全量索引都不为过。

[xiao109]

重点是查，所以建立索引结构的时间应该不会纳入耗时的计算。
按 6 或 8 位截取数字映射到索引中，然后再搜。

[arthurire]

这是啥算法题啊...
算法不就是 KMP 之类 你还能突破理论极限不成?
要是比速度就建立各种索引,然后 O(1)

别侮辱算法题啊

[xz410236056]

str.find() 是 Boyer-Moore 和 Horspool 算法的结合，这都慢用 KMP 能快吗？

[lizytalk]

如果是查多次的话, 可以把整个文档处理成后缀数组 (只需要常数空间), 然后每次查询可以做到对数时间 O(P log (T)), T 是整个文档的长度, P 是查询的长度.
至于建索引, 时间倒是 O(1)的, 但是索引的空间可是指数级别的.

[lesismal]

@c0xt30a 不用那么麻烦的 hash ，要查询的数字 n 具有上下限并且值范围不是特别巨大，用要查询的数字 n 作为数组下标就行了，数组的值就是 n 对应的在 pi 中的 index
@arthurire KMP 是 O(m+n) 的，字符串本身达到 10 亿量级，O(m+n) = 10y+8 也是没法接受的

#34 楼已经实现，建好数组就相当于位图了，时间复杂度 O(1)

[irobbin]

如果算生日的话，365*100= 36500 ，总共就这么点数据，找个时间整体遍历一遍，查完存起来搞定。

[neptuno]

遍历所有数字排列，存数据库

[asmoker]

sublime 或者 vim 😀

[MegrezZhu]

才 6 到 8 位…就算用上 O(n+m)的 kmp 也撑死优化几倍的时间，有这个工夫用 C++写个暴力就得了

[trcnkq]

https://www.angio.net/pi/how.html

[wnma3mz]

盲猜是查找生日字符串之类的，之前实现过，供参考
https://github.com/wnma3mz/birthday_in_pi/blob/master/read_large_pi.py#L20-L30
主要问题还是放到服务器里面内存问题啥的。
暴力的方法，还可以建表。。

[shm7]

@yianing
@GrayXu 厉害，用 trie