面试题：Python优化圆周率查找生日的性能

Question

在Python实现从圆周率中查找生日的基础上，若圆周率数据量极大，如何优化程序性能以减少查找时间。请从算法优化、数据结构选择、Python特性利用等方面阐述，并给出关键代码示例。

Answer 1

算法优化

1. 前缀树（Trie树）：将圆周率的数字序列构建成前缀树。这样在查找生日（假设生日格式为8位数字）时，可以从根节点开始，沿着与生日数字匹配的路径快速查找，减少不必要的遍历。例如，如果生日是“19900101”，从根节点开始依次匹配“1”“9”“9”等节点。
2. 哈希表：对圆周率数据进行预处理，将每8位数字组合（对应生日格式）及其位置存储到哈希表中。哈希表的查找时间复杂度为O(1)，极大提高查找效率。

数据结构选择

1. 使用数组存储圆周率：Python中的列表可以存储大量数字字符，并且支持快速的索引访问。例如：

pi_digits = list('31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679')

2. 利用集合：如果只是判断生日是否在圆周率中，不关心位置，可以将所有可能的8位数字组合存入集合。集合的查找效率高，且能保证元素唯一性。

Python特性利用

1. 生成器：由于圆周率数据量极大，使用生成器可以按需生成数据，避免一次性加载大量数据到内存。例如：

def pi_generator():
    # 这里假设通过某种方式获取圆周率数据，每次生成一位数字
    pi_source = "31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
    for digit in pi_source:
        yield digit

2. 多线程或多进程：利用Python的threading或multiprocessing模块，将查找任务分发给多个线程或进程并行处理。但要注意GIL（全局解释器锁）对多线程的限制，对于CPU密集型任务，多进程可能更合适。例如使用multiprocessing模块：

import multiprocessing


def find_birthday_in_pi(birthday, pi_chunk):
    if birthday in pi_chunk:
        return pi_chunk.index(birthday)
    return -1


if __name__ == '__main__':
    birthday = "19900101"
    pi_digits = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
    num_processes = multiprocessing.cpu_count()
    chunk_size = len(pi_digits) // num_processes
    processes = []
    results = []
    for i in range(num_processes):
        start = i * chunk_size
        end = start + chunk_size if i < num_processes - 1 else len(pi_digits)
        pi_chunk = pi_digits[start:end]
        p = multiprocessing.Process(target=find_birthday_in_pi, args=(birthday, pi_chunk))
        processes.append(p)
        p.start()
    for p in processes:
        p.join()
        result = p.exitcode
        if result != -1:
            results.append(result)
    if results:
        print(f"生日在圆周率中的位置: {results}")
    else:
        print("未在圆周率中找到生日")

关键代码示例（以哈希表为例）

def find_birthday_in_pi_hash(birthday):
    pi_digits = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
    pi_hash = {}
    for i in range(len(pi_digits) - 7):
        eight_digits = pi_digits[i:i + 8]
        if eight_digits not in pi_hash:
            pi_hash[eight_digits] = i
    if birthday in pi_hash:
        return pi_hash[birthday]
    return -1


birthday = "19900101"
position = find_birthday_in_pi_hash(birthday)
if position != -1:
    print(f"生日在圆周率中的位置: {position}")
else:
    print("未在圆周率中找到生日")