基于信息论的Wordle求解Python程序性能优化求助

翻出学生时代完成的Wordle求解旧Prolog项目，该项目需要对含7980个单词的文件按“价值”排序，当时配套了一段基于信息论生成该文件的Python代码。由于已看不懂旧代码，且其运行缓慢、质量不佳，决定重写，但遇到严重性能问题：计算单个单词的熵最快需0.5秒，7980个单词总耗时超1小时！

测试代码如下：

import math
import time

def read_words(path):
    words = []

    with open(path, "r") as file:
        while line := file.readline():
            line = line.replace("word([", "").replace("]).", "").replace("\n", "")
            words.append("".join([l.strip().replace("'", "") for l in line.split(",")]))
    
    return words

def get_int_pattern(soluce, w):
    res = [0, 0, 0, 0, 0]
    used = [False, False, False, False, False]
    wrange = range(len(w))

    for i in wrange:
        if w[i] == soluce[i]:
            res[i] = 2
            used[i] = True
        
    for i in wrange:
        if used[i]:
            continue

        for j in wrange:
            if not used[j] and w[i] == soluce[j]:
                res[i] = 1
                used[j] = True
                break

    res_value = 0
    for i, r in enumerate(res):
        res_value += r * 3 ** i
    
    return res_value

def generate_int_pattern_matrix(all_words):
    wlen = len(all_words)
    matrix = {}
    start_time = time.time()

    for i, w in enumerate(all_words):
        matrix[w] = {}

        for w2 in all_words:
            matrix[w][w2] = get_int_pattern(w, w2)

        print("\rGenerating int matrix {}/{} {}s".format(i+1, wlen, round(time.time() - start_time, 1)), end="")
    
    print()
    return matrix

def int_pattern_match(word, pattern, test):
    return get_int_pattern(test, word) == pattern

def int_pattern_match2(matrix, word, pattern, test):
    return matrix[test][word] == pattern


all_words = read_words("../save/word_origin.pl")
wlen = len(all_words)

all_patterns = range(243)
pattern_matrix = generate_int_pattern_matrix(all_words)

HTimeC = HTimeL = HTimeS = 0
start_time = time.time()

for w in all_words:
    H = 0
    HTimeS = time.time()

    for p in all_patterns:
        count = 0

        for w2 in all_words:
            if int_pattern_match2(pattern_matrix, w, p, w2):
                count += 1
        
        if count == 0:
            continue
    
        proba = count / wlen
        H += proba * -math.log2(proba)

    HTimeC += time.time() - HTimeS
    HTimeL += 1

    print("\r{}/{} H={} averageHTime={} totalSec={}s".format(HTimeL, wlen, H, round(HTimeC/HTimeL, 3), round(time.time() - start_time, 1)), end="")

print()

原理说明 #

计算每个单词的熵（使用该单词作为猜测时能获得的平均信息量），逻辑如下：

• 针对所有可能的颜色模式（绿色、橙色、黑色的5位组合，共243种），统计该模式出现时可能作为答案的单词数量
• 单个模式的信息量为 -log2(p)（其中p = 统计数 / 总单词数）
• 单词的熵为所有模式的信息量乘以其概率后的总和

将模式编码为3进制整数以加快比较速度，例如：189 = 23^4 + 13^3 + 03^2 + 03^1 + 0*3^0，对应模式为“绿色、橙色、黑色、黑色、黑色”。

相关函数说明：

• int_pattern_match2：验证若以test为答案，猜测word得到的模式是否等于给定pattern，若是则test可能是答案
• generate_int_pattern_matrix：预计算所有模式矩阵耗时约2分钟，尝试保存复用但加载更慢且导致Codium崩溃

参考了ScienceEtonnante（法语）和3Blue1Brown的YouTube视频，前者提到其代码计算第一回合仅需约1分钟，而当前程序慢得多，卡了两天，恳请提供优化方案。

内容的提问来源于stack exchange，提问作者Louloukit