Wnma's Blogs
0%

Birthday in Pi：查找日期在Pi中的位置

发表于 更新于 分类于

想知道自己的生日在圆周率π的第几位出现吗？本文介绍了从思路到实现所遇到的问题，详细分析了如何使用迭代器优化性能，并改用Python语言实现了类似“ 锁”内存等操作。最终，将函数打包成了exe程序，在公众号内提供查询服务，还提供了一个不断更新的生日与位置的查表。

完整的项目代码均开源: https://github.com/wnma3mz/birthday_in_pi

想法

于我而言，很多项目的出发点都是源于浏览东西时所想，觉得有意思就去实现。比如这次是在即刻上看到北大数院公众号，可以回复生日（如20000101）就可以知道这串数字在Pi的第多少位出现。更详细的例子：已知3.1415926...，那么1415就是出现在第1位（从1开始计数，小数点后开始计数）。但该公众号仅在Pi的2亿位数中进行查找，所以有即友回复，搜不到结果。故想到可以试试更长的数据集是否能够搜到。

背景知识

理论上，Pi里面可以查找所有人的电话号码、生日、银行卡密码等等。

行动

数据

巧妇难为无米之炊，这里最重要的就是Pi这个无理数数据。

  1. 是否有现成的数据文本->没搜到，搜到的位数都很小，不足以满足需求
  2. 计算Pi（生成超过2亿数的文本）
    1. 自己手写
    2. 找程序。对于计算Pi的项目，本身就是一个科学问题，故一定有现有程序可以辅助完成。所以找到了y-cruncher项目。具体是否为当前最快的生成程序，未深究，不过实际测试，效率已经可以满足需求。（用i5-1035G1的CPU，生成25亿数，8个线程计算用了10分钟不到，文本大小2.4G）

编码

该问题本身简单来看就是一个字符串查找问题，所以用Python的话，find函数可以直接完成这项任务。但一旦问题变"大"（数据集变大、机器变多......），就是一个"难"题了。

当然，先不管如何，试试最粗暴的解法看看性能如何。根据测试结果，有两个问题，时间超过5s, 内存占用2G（文本大小2G）。就算时间可以接受，那么这个空间占用也很难接受。试想，每查询一次都需要占用2G内存，查询完再释放。所以直接想到的优化点有以下几个

  1. "锁"内存，即每次查询完不释放这个内存，这样IO时间就可以大大减小
  2. "做表"，查询的生日数字是有限的，无非就是(19700101-20101231有限数据)，就算100年，也只是36500个数据（实际会略高，因为有闰年）。查表的效率就非常快了
  3. 从根本上优化这个程序

优化

首先排除2，因为最终还是想查找任意数字，2不便于后续扩展，而且根据现有的性能，做表也需要很长时间。

其次对于1，如果考虑对外开放，服务器占用2G内存空间，实在是太"奢侈"了

所以最后就只能考虑3。

迭代器

Python有个关键词是 yield，它可以实现迭代器这个功能。说人话就是，它不是一次性把数据加载出来，而且每次只加载一部分。下面是一个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def yield_func(lst):
    for i in lst:
        yield i

def for_return_func(lst):
    for i in lst:
        return i

def return_func(lst):
    return lst

if __name__ == "__main__":
    lst = list(range(10))
    print(yield_func(lst))
    print(for_return_func(lst))
    print(return_func(lst))
    for x in yield_func(lst):
        print(x, end=" ")
1
2
3
4
5
# 输出如下
<generator object yield_func at 0x000001644AF624F8>
0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
0 1 2 3 4 5 6 7 8 9

所以肯定是要利用这个方法来帮助优化程序。在Python操作文件的时候 readline()函数就是一个生成器，一行一行的返回，查找速度比直接 read()或者 readlines()更快。

但这里的问题是，输出的Pi文本是一行。。。所以没法直接使用。当然也可以手动把这个文本按行切割后，再用 readline()函数。

这里我找到的解决方案[1]可以更方便的解决这个问题，详见博客or项目源码。

bug

把程序写好之后，可以发现一个很明显的bug，就是查询的字符串如果在两个 chunk之间，是会直接跳过。比如 12345678，block_size=4，那么就是 1234和 5678。如果查找 45是找不到的。

所以这里需要做两个额外的处理

  1. 加上上一个 block_size的字符串 old_chunk = copy.deepcopy(chunk[-len(target_str) :])。这里为了省空间和时间，只加上了需要查询字符串的长度，就可以满足需求
  2. 返回查找位数时需要额外 -len(old_chunk)。（注：这里一开始忘了操作，故前几位查询的既有会发现结果与北大数院查询的结果差10位，在这里致歉）

最后经过测试后，性能基本达到预期（见项目README，有说明具体结果）。

部署

至此，核心程序已经完成，接下来需要考虑一种方式来给其他人方便使用了。最直接的其实就是写一个Web，前端去调用后端返回结果。但同样的，这里还是考虑到网站流量等原因，跟北大数院一样放到公众号上也很方便，开发上也只需要完成后端即可，无需考虑前端UI啥的。

查询公众号文档后，一通操作，就把功能完成了（文案直接"抄"了北大数院的文案）。代码见flask_server.py

这里需要在微信公众号后台配置开发者模式，然后把token复制进代码。

Tip

公众号开发要求是80端口，但这里通过子域名的方式+nginx反代就可以直接用域名访问，而无需80端口。nginx配置见下

1
2
3
4
5
6
7
8
9
10
server {
    listen       80;
    server_name  xxx.yyy.zzz;

    location / {
        uwsgi_pass 0.0.0.0:port;
        proxy_pass http://0.0.0.0:port/wx_api;
    }
  
}

这里的 xxx.yyy.zzz就是域名，port就是 flask开启的端口

其他

查表

当然，查表的方式还是最快的，所以还是建了一个表，并且做了一个简单的分析。分析内容如下

最近只需246位能够找到, 最远需要近9亿位。列出Top10（左侧为年月日，右侧为第x位）

日期范围为19700101-20091231

日期 位数
20190914 246
20190516 5364
19910403 8365
20141020 9813
19950728 1,3874
20121031 1,4538
19990814 2,5593
19810705 2,7202
19921122 3,0884
19930509 3,6615
.......... ..........
19941227 7,1993,2960
20080923 7,2930,2729
19911201 7,2985,0775
20071206 7,3782,1997
20090220 7,5402,4215
19730829 7,7357,0338
20070526 7,8655,8038
19951122 8,2582,0139
20140407 8,7320,8091
19730521 8,8950,7619

为什么4位分隔，而不是3位？

因为我觉得这样看的更舒服，读万、亿更方便。。。

程序打包

为方便没有Python程序的用户，同时也不想使用公众号。在Windows上打包了一份exe程序。命令也很简单 pyinstaller -F .\read_large_pi.py。

最后的最后，该程序尚存在优化空间，当查询数字较长（超过8位）时，时间花费也更久（超过1s）。

参考文章

[1] python-如何流式读取大文件