从 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]

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

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

[datou]

两秒出结果,很慢么?

[djFFFFF]

预处理，用空间换时间是最优解法。只是六位到八位（而且盲猜是出生日期？那更简单了）的话存一张表轻松解决。

@hidemyself cpython 我印象里 str.find() 是用的 BMH 算法？反正虽然这个题面是个标准的 KMP 算法的场景，现实生产环境谁用谁是傻子。

[546L5LiK6ZOt]

https://nullprogram.com/blog/2014/09/18/
这个老外尝试了多种方法，可以参考下

[lonenol]

最粗暴的就是 hash 呗，key 是数字，value 是位置，第一次构建比较慢，剩余的查询就都是 O(1)的了

[lonenol]

不好意思，python 里叫字典，我习惯用 hash 指代 Java 里的 HashMap 了

[yianing]

trie 就行了吧，只是加载需要点时间，搞个常驻进程就行，我用 go 试了下内存大约 1G ，加载不到 10 分钟

[GrayXu]

这如果是个题，考的自然是子串匹配，Boyer-Moore 等。
就算建索引，也是用 trie 树系列，用 hash 有点太异想天开。。。

[tianq]

好久以前研究过在 pi 里找生日：
https://lil-q.github.io/blog/pi/

[searene]

我也把文件下下来了，1.6 秒左右就找到了。如果是题目的话，这道题目是不合格的，因为现实情况就是用 find 就可以了，建索引还更慢

[Jelebi]

Ctrl + F

[vanton]

本地跑 str.find() 最多几秒种，速度足够了。

如果你有特别的需求，比如高并发服务，那就索引，数据库或者 hash 都行，不要读文本。

[lesismal]

用数据库存上也是慢，内存里缓存起来性能最好了，下面代码大概意思是 converter 先统计好索引到数组，然后把数组写入到文件，finder 读入文件初始化数组，然后再查找。没仔细调试，因为太烧机器了，有兴趣的同学可以完善下：

1. converter.py
```python
# -*- coding:utf-8 -*-
#!/usr/bin/python3

import datetime

class PIConverter:
def __init__(self, minNum=100000, maxNum=99999999):
self.minNum = minNum
self.maxNum = maxNum
self.positions = [0]*(self.maxNum+1-self.minNum)

def convert(self, srcFile, dstFile):
fsrc = open(srcFile,'r')
fsrc.read(2)
try:
lastStr = ""
readSize = 1024*8
currPos = 0
readed = 0

starttime = datetime.datetime.now()

offset = len(str(self.minNum)) - 1
while True:
s = fsrc.read(readSize)
s = lastStr + s # 这里可以再优化下
currPos -= len(lastStr)
for i in range(len(s)-8):
strLen = len(str(self.minNum))
while strLen <= len(str(self.maxNum)):
subs = s[i:i+strLen]
strLen += 1
num = int(subs)
index = num - self.minNum
if self.positions[index] == 0:
self.positions[index] = currPos + i

if len(s) == 0:
break

lastStr = s[len(s)-5:]
currPos += readSize
readed += readSize
if readed % (1024*1024*8) == 0:
print("total read: {}, time used: {}s".format(readed, (datetime.datetime.now() - starttime).seconds))

print("total read: {}, time used: {}s".format(readed, (datetime.datetime.now() - starttime).seconds))
print("done")

try:
fdst = open(dstFile,'rw+')
for index in range(self.positions):
fdst.write(str(index)+"\n")
finally:
fdst.close()
finally:
fsrc.close()

def find(self, n):
if n < self.minNum or n > 99999999:
return -1
return self.positions[n - self.minNum]

piConverter = PIConverter()

# 把已经统计出来的生成更小的文件
piConverter.convert("./pi-billion.txt", "./pi-position.txt")

# converter 初始化太慢了，所以最好还是先 piConverter.convert 把已经统计出来的生成更小的文件，finder.py 用该文件初始化和做查找
# print("141592:", piConverter.find(141592))
# print("415926:", piConverter.find(415926))
```

2. finder.py
```python
# -*- coding:utf-8 -*-
#!/usr/bin/python3

class PIFinder:
def __init__(self, fname, minNum=100000, maxNum=99999999):
self.minNum = minNum
self.maxNum = maxNum
self.positions = [0]*(self.maxNum+1-self.minNum)
f = open(fname,'r')
try:
i = 0
for line in f:
num = int(line)
self.positions[i] = num
finally:
f.close()

def find(self, n):
if n < self.minNum or n > 99999999:
return -1
return self.positions[n - self.minNum]

piFinder = PIFinder("./pi-position.txt")
print("141592:", piFinder.find(141592))
print("415926:", piFinder.find(415926))
```

[lesismal]

#32 文件尾、打开写文件的好像都有问题，平时不写 py ，实在不熟悉，v 站发代码也确实难受，对齐好像都没了

[lesismal]

算了，忍不住还是调试了下，完整版的：
https://gist.github.com/lesismal/c4528eacc35db33f754ac2f8eb9e7634

[c0xt30a]

我提一个用素数来 Hash 查找的方法，大致如下：

1. 将 0-9 映射为 前 10 个素数 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2. 用一个定长为 6/8 的滑动窗口遍历这个 pi 的字符串，每次增长的时候，当前的 hash 先除以最后一位数字对应的素数再乘以新增数字对应的素数，可以得到最新的 hash 数值
3. 如果当前 hash 数值与要寻找的数字的 hash 相等，则停下来进一步比对字符串

[c0xt30a]

当然 直接乘以 10 加上新来的数字再对 10^7 取 mode 以更新 hash 也行

[kuangwinnie]

950MB 塞内存里也没多大啊。

[murmur]

950m 进内存配合现在的处理器可能有发帖时间都做出来了吧，这是跑 leetcode 限制内存了？

[gulugu]

分割了，然后分布式查询

[ihainan]

固定 6 位和 8 位的话或许可以考虑 Rabin-Karp 算法求哈希值。

[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