KATTIS编程挑战优化：Ab Initio哈希计算性能优化求助

我正在解决KATTIS平台上的《Ab Initio》问题，目前代码整体速度过慢，尤其是顶点邻接表哈希值hᵢ的计算环节达不到理想速度。

hᵢ是顶点i邻接表的哈希值，定义如下：假设顶点i的出邻域顶点为n₁<n₂<⋯<n_dᵢ，则hᵢ=7⁰·n₁+7¹·n₂+7²·n₃+⋯+7^(dᵢ−1)·n_dᵢ，结果需取10⁹+7的模。

每个顶点的邻接表长度最多为2000，总共有最多2000个顶点需要计算哈希值。我当前的最优实现是预先生成7的幂次列表，通过zip计算，在2000×2000的随机图上耗时约0.25秒，寻求更优的优化方案。

附上测试代码：

import time, random

testgraph = []

for _ in range(2000):
    row = []
    testgraph.append(row)
    
for i in range(2000):
    for j in range(random.randint(500,1800)):
        if i!=j:
            testgraph[i].append(j)
            
MOD = 10**9 + 7
sevens = [1]*2500
for i in range(2499):
    sevens[i+1]=(sevens[i]*7) %MOD
    
t1 = time.time()    
for row in testgraph:
    hashv = 0
    row.sort()
    for a,b in zip(row, sevens):
        hashv +=a*b
        
    hashv = hashv % MOD
t2 = time.time()

print(t2-t1)

• 动态递推幂次，取消预存数组：预存幂次列表会占用额外内存，且zip配对会带来遍历开销。计算哈希时动态维护当前7的幂次，初始current_power=1，每遍历一个邻接点就更新hashv = (hashv + n * current_power) % MOD，再让current_power = (current_power *7) % MOD，既省内存又减少操作步骤。
• 提前维护邻接表有序性：原代码中每个邻接表单独排序的开销占比很高，可在构建邻接表时直接插入有序位置（比如用bisect.insort），避免后续排序的O(d log d)耗时。
• 逐步骤取模控制数值大小：原代码仅在最后取模，中间hashv会变成超大整数，拖慢计算速度。每一步计算都取模，保持数值始终在合理范围内。
• 用JIT编译加速循环（允许第三方库时）：Python原生循环速度有限，用numba对哈希计算函数做JIT编译，能大幅提升循环执行效率。

原生Python优化版本 #

import time, random
import bisect

MOD = 10**9 + 7

# 构建邻接表时直接保持有序
testgraph = []
for _ in range(2000):
    testgraph.append([])
    
for i in range(2000):
    count = random.randint(500, 1800)
    used = set()
    while len(used) < count:
        j = random.randint(0, 1999)
        if j != i and j not in used:
            bisect.insort(testgraph[i], j)
            used.add(j)

t1 = time.time()
hashes = []
for row in testgraph:
    hashv = 0
    current_power = 1
    for n in row:
        hashv = (hashv + n * current_power) % MOD
        current_power = (current_power * 7) % MOD
    hashes.append(hashv)
t2 = time.time()

print(t2 - t1)

Numba JIT加速版本（需安装numba库） #

import time, random
import bisect
from numba import jit

MOD = 10**9 + 7

# JIT编译哈希计算函数
@jit(nopython=True)
def compute_hash(row, mod):
    hashv = 0
    current_power = 1
    for n in row:
        hashv = (hashv + n * current_power) % mod
        current_power = (current_power *7) % mod
    return hashv

# 构建有序邻接表
testgraph = []
for _ in range(2000):
    testgraph.append([])
    
for i in range(2000):
    count = random.randint(500, 1800)
    used = set()
    while len(used) < count:
        j = random.randint(0, 1999)
        if j != i and j not in used:
            bisect.insort(testgraph[i], j)
            used.add(j)

t1 = time.time()
hashes = [compute_hash(row, MOD) for row in testgraph]
t2 = time.time()

print(t2 - t1)

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