V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
grimpil
V2EX  ›  Python

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

  •  
  •   grimpil · 2021-11-10 17:42:13 +08:00 · 7585 次点击
    这是一个创建于 869 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    53 条回复    2021-11-21 18:31:53 +08:00
    renmu123
        1
    renmu123  
       2021-11-10 17:45:01 +08:00 via Android
    用滑动窗口应该能稍微快一点
    Ediacaran
        2
    Ediacaran  
       2021-11-10 17:46:44 +08:00 via iPhone   ❤️ 3
    000 ~ 999 所在位置索引一个表
    Junzhou
        3
    Junzhou  
       2021-11-10 17:48:48 +08:00   ❤️ 1
    kmp
    vvhhaaattt
        4
    vvhhaaattt  
       2021-11-10 17:49:53 +08:00 via Android   ❤️ 1
    没有限制的话,空间换时间,类似 ngram 索引
    hahasong
        5
    hahasong  
       2021-11-10 17:51:47 +08:00
    读取文件了,直接操作内存,分片多线程查找
    cclin
        6
    cclin  
       2021-11-10 17:52:25 +08:00 via Android
    KMP 么
    radiocontroller
        7
    radiocontroller  
       2021-11-10 17:53:43 +08:00
    字符串查找子串,kmp 算法
    aircjm
        8
    aircjm  
       2021-11-10 17:54:20 +08:00 via Android
    盲猜从圆周率里面取日期
    SmiteChow
        9
    SmiteChow  
       2021-11-10 17:54:43 +08:00
    倒排
    cclin
        10
    cclin  
       2021-11-10 18:12:52 +08:00
    我把文件下载下来了,用 str.find() 挺快的呀,读取文件 3.66s ,查找 0.007s
    Vegetable
        11
    Vegetable  
       2021-11-10 18:24:49 +08:00
    都是什么宰牛刀啊都,直接全量塞数据库啊!才多大点啊
    3dwelcome
        12
    3dwelcome  
       2021-11-10 18:26:06 +08:00
    PI 属于随机数那种,索引都不好建。

    怕是没什么好办法。只能挨个查找。
    ppcoin
        13
    ppcoin  
       2021-11-10 18:29:39 +08:00   ❤️ 1
    @Vegetable 算法题哥哥
    xx6412223
        14
    xx6412223  
       2021-11-10 18:30:31 +08:00
    都是 O(n),
    事先加载文件并事先分段并多线程
    hidemyself
        15
    hidemyself  
       2021-11-10 18:31:41 +08:00
    楼上说 kmp 的有没有看过 python 对于 find 的实现哇。。
    Vegetable
        16
    Vegetable  
       2021-11-10 18:33:44 +08:00
    @ppcoin 这是题吗,没看出来啊,这种问题最优解就是空间换时间,再怎么做不还是索引吗
    nazor
        17
    nazor  
       2021-11-10 18:35:06 +08:00
    有个数据结构叫后缀数组,特别适合你提出的这种文本不变,模式串不同的查询需求。
    oOoOoOoOoOo
        18
    oOoOoOoOoOo  
       2021-11-10 18:39:10 +08:00 via Android
    @hidemyself

    请看 in 的实现
    oOoOoOoOoOo
        19
    oOoOoOoOoOo  
       2021-11-10 18:40:13 +08:00 via Android
    分片 线程查找
    3dwelcome
        20
    3dwelcome  
       2021-11-10 18:44:04 +08:00
    “这是题吗,没看出来啊,这种问题最优解就是空间换时间,再怎么做不还是索引吗”

    问题的关键,是如何去建索引。完全乱序的数字,没办法建立有效的索引结构。
    datou
        21
    datou  
       2021-11-10 18:50:05 +08:00
    两秒出结果,很慢么?
    djFFFFF
        22
    djFFFFF  
       2021-11-10 18:50:29 +08:00
    预处理,用空间换时间是最优解法。只是六位到八位(而且盲猜是出生日期?那更简单了)的话存一张表轻松解决。

    @hidemyself cpython 我印象里 str.find() 是用的 BMH 算法?反正虽然这个题面是个标准的 KMP 算法的场景,现实生产环境谁用谁是傻子。
    546L5LiK6ZOt
        23
    546L5LiK6ZOt  
       2021-11-10 18:59:37 +08:00 via iPhone   ❤️ 4
    https://nullprogram.com/blog/2014/09/18/
    这个老外尝试了多种方法,可以参考下
    lonenol
        24
    lonenol  
       2021-11-10 20:21:46 +08:00
    最粗暴的就是 hash 呗,key 是数字,value 是位置,第一次构建比较慢,剩余的查询就都是 O(1)的了
    lonenol
        25
    lonenol  
       2021-11-10 20:22:30 +08:00
    不好意思,python 里叫字典,我习惯用 hash 指代 Java 里的 HashMap 了
    yianing
        26
    yianing  
       2021-11-10 20:28:46 +08:00
    trie 就行了吧,只是加载需要点时间,搞个常驻进程就行,我用 go 试了下内存大约 1G ,加载不到 10 分钟
    ![stats]( https://imgur.com/GjcslkB)
    GrayXu
        27
    GrayXu  
       2021-11-10 20:42:48 +08:00
    这如果是个题,考的自然是子串匹配,Boyer-Moore 等。
    就算建索引,也是用 trie 树系列,用 hash 有点太异想天开。。。
    tianq
        28
    tianq  
       2021-11-10 20:57:58 +08:00 via iPhone   ❤️ 5
    好久以前研究过在 pi 里找生日:
    https://lil-q.github.io/blog/pi/
    searene
        29
    searene  
       2021-11-10 21:08:07 +08:00
    我也把文件下下来了,1.6 秒左右就找到了。如果是题目的话,这道题目是不合格的,因为现实情况就是用 find 就可以了,建索引还更慢
    Jelebi
        30
    Jelebi  
       2021-11-10 22:32:26 +08:00
    Ctrl + F
    vanton
        31
    vanton  
       2021-11-10 22:36:15 +08:00
    本地跑 str.find() 最多几秒种,速度足够了。

    如果你有特别的需求,比如高并发服务,那就索引,数据库或者 hash 都行,不要读文本。
    lesismal
        32
    lesismal  
       2021-11-10 23:46:44 +08:00
    用数据库存上也是慢,内存里缓存起来性能最好了,下面代码大概意思是 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
        33
    lesismal  
       2021-11-10 23:53:39 +08:00
    #32 文件尾、打开写文件的好像都有问题,平时不写 py ,实在不熟悉,v 站发代码也确实难受,对齐好像都没了
    lesismal
        34
    lesismal  
       2021-11-11 00:22:06 +08:00   ❤️ 1
    算了,忍不住还是调试了下,完整版的:
    https://gist.github.com/lesismal/c4528eacc35db33f754ac2f8eb9e7634
    c0xt30a
        35
    c0xt30a  
       2021-11-11 02:03:53 +08:00
    我提一个用素数来 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
        36
    c0xt30a  
       2021-11-11 05:45:27 +08:00
    当然 直接乘以 10 加上新来的数字再对 10^7 取 mode 以更新 hash 也行
    kuangwinnie
        37
    kuangwinnie  
       2021-11-11 05:51:31 +08:00
    950MB 塞内存里也没多大啊。
    murmur
        38
    murmur  
       2021-11-11 08:28:30 +08:00
    950m 进内存配合现在的处理器可能有发帖时间都做出来了吧,这是跑 leetcode 限制内存了?
    gulugu
        39
    gulugu  
       2021-11-11 08:42:44 +08:00
    分割了,然后分布式查询
    ihainan
        40
    ihainan  
       2021-11-11 08:52:56 +08:00
    固定 6 位和 8 位的话或许可以考虑 Rabin-Karp 算法求哈希值。
    rrfeng
        41
    rrfeng  
       2021-11-11 09:12:37 +08:00 via Android
    那要查的数字范围 6/8 的前 N 位枚举出来遍历一下做位置索引,N 取值可以做个测试找到空间和时间的平衡点。

    盲猜你要查生日,那查询目标才没几个,全量索引都不为过。
    xiao109
        42
    xiao109  
       2021-11-11 09:30:00 +08:00
    重点是查,所以建立索引结构的时间应该不会纳入耗时的计算。
    按 6 或 8 位截取数字映射到索引中,然后再搜。
    arthurire
        43
    arthurire  
       2021-11-11 09:36:19 +08:00
    这是啥算法题啊...
    算法不就是 KMP 之类 你还能突破理论极限不成?
    要是比速度就建立各种索引,然后 O(1)

    别侮辱算法题啊
    xz410236056
        44
    xz410236056  
       2021-11-11 10:34:23 +08:00
    str.find() 是 Boyer-Moore 和 Horspool 算法的结合,这都慢用 KMP 能快吗?
    lizytalk
        45
    lizytalk  
       2021-11-11 10:35:47 +08:00
    如果是查多次的话, 可以把整个文档处理成后缀数组 (只需要常数空间), 然后每次查询可以做到对数时间 O(P log (T)), T 是整个文档的长度, P 是查询的长度.
    至于建索引, 时间倒是 O(1)的, 但是索引的空间可是指数级别的.
    lesismal
        46
    lesismal  
       2021-11-11 10:37:33 +08:00
    @c0xt30a 不用那么麻烦的 hash ,要查询的数字 n 具有上下限并且值范围不是特别巨大,用要查询的数字 n 作为数组下标就行了,数组的值就是 n 对应的在 pi 中的 index
    @arthurire KMP 是 O(m+n) 的,字符串本身达到 10 亿量级,O(m+n) = 10y+8 也是没法接受的

    #34 楼已经实现,建好数组就相当于位图了,时间复杂度 O(1)
    irobbin
        47
    irobbin  
       2021-11-11 10:40:03 +08:00   ❤️ 3
    如果算生日的话,365*100= 36500 ,总共就这么点数据,找个时间整体遍历一遍,查完存起来搞定。
    neptuno
        48
    neptuno  
       2021-11-11 11:18:18 +08:00
    遍历所有数字排列,存数据库
    asmoker
        49
    asmoker  
       2021-11-11 11:48:47 +08:00
    sublime 或者 vim 😀
    MegrezZhu
        50
    MegrezZhu  
       2021-11-11 11:50:58 +08:00
    才 6 到 8 位…就算用上 O(n+m)的 kmp 也撑死优化几倍的时间,有这个工夫用 C++写个暴力就得了
    trcnkq
        51
    trcnkq  
       2021-11-11 15:48:31 +08:00
    wnma3mz
        52
    wnma3mz  
       2021-11-12 09:36:49 +08:00
    盲猜是查找生日字符串之类的,之前实现过,供参考
    https://github.com/wnma3mz/birthday_in_pi/blob/master/read_large_pi.py#L20-L30
    主要问题还是放到服务器里面内存问题啥的。
    暴力的方法,还可以建表。。
    shm7
        53
    shm7  
       2021-11-21 18:31:53 +08:00
    @yianing
    @GrayXu 厉害,用 trie
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3030 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 14:52 · PVG 22:52 · LAX 07:52 · JFK 10:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.