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 · 75 天前 · 6500 次点击
    这是一个创建于 75 天前的主题,其中的信息可能已经有所发展或是发生改变。

    从网上下一个 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  
       75 天前 via Android
    用滑动窗口应该能稍微快一点
    Ediacaran
        2
    Ediacaran  
       75 天前 via iPhone   ❤️ 3
    000 ~ 999 所在位置索引一个表
    Junzhou
        3
    Junzhou  
       75 天前   ❤️ 1
    kmp
    vvhhaaattt
        4
    vvhhaaattt  
       75 天前 via Android   ❤️ 1
    没有限制的话,空间换时间,类似 ngram 索引
    hahasong
        5
    hahasong  
       75 天前
    读取文件了,直接操作内存,分片多线程查找
    cclin
        6
    cclin  
       75 天前 via Android
    KMP 么
    radiocontroller
        7
    radiocontroller  
       75 天前
    字符串查找子串,kmp 算法
    aircjm
        8
    aircjm  
       75 天前 via Android
    盲猜从圆周率里面取日期
    SmiteChow
        9
    SmiteChow  
       75 天前
    倒排
    cclin
        10
    cclin  
       75 天前
    我把文件下载下来了,用 str.find() 挺快的呀,读取文件 3.66s ,查找 0.007s
    Vegetable
        11
    Vegetable  
       75 天前
    都是什么宰牛刀啊都,直接全量塞数据库啊!才多大点啊
    3dwelcome
        12
    3dwelcome  
       75 天前
    PI 属于随机数那种,索引都不好建。

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

    请看 in 的实现
    oOoOoOoOoOo
        19
    oOoOoOoOoOo  
       75 天前 via Android
    分片 线程查找
    3dwelcome
        20
    3dwelcome  
       75 天前
    “这是题吗,没看出来啊,这种问题最优解就是空间换时间,再怎么做不还是索引吗”

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

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

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

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

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

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