贪心算法求解TSP预计算距离时内存占用远超预期原因咨询

内存超预期的根本原因 #

你最初的预估是纯有效数据的理论存储大小，但完全没考虑Python runtime的对象开销和容器开销，实际占用高是必然的：

• Python中所有内置对象都有额外的元数据开销：你测试过frozenset作为键要占216字节，换成排序后的tuple也要56字节，哪怕是numpy的int16、float32标量，作为Python对象存储时也会带上几十字节的对象头，绝非只占2字节/4字节。
• Python字典本身是哈希表结构，开销远大于存储的键值对本身：每个字典条目需要额外存储哈希值、键指针、值指针，64位系统下这三项就占24字节；同时为了降低哈希冲突概率，哈希表的负载因子通常不会超过2/3，会预留1/3以上的空闲空间。
• 按你优化后的方案计算，5亿条条目光键的开销就达到5e8 * 56 = 28GB，再加上值的开销、字典的预留空间，实际占用超过30GB完全符合预期。

可行的优化方案 #

你完全不需要用字典存储所有距离，针对33708个城市的场景，有两种内存占用极低的方案可选：

方案1：用扁平化上三角矩阵存储预计算距离 #

33708个城市的两两组合刚好对应一维数组的n*(n-1)//2个位置，直接用numpy一维数组存储，没有任何额外对象开销，总内存仅为5.68e8 * 4Byte = ~2.27GB，远低于你的预期值。
示例代码：

import numpy as np

cities_arr = np.array(cities, dtype=np.float32)
n = cities_arr.shape[0]
# 预分配一维数组存储所有i<j的距离
dist_flat = np.zeros(n * (n - 1) // 2, dtype=np.float32)

offset = 0
for i in range(n - 1):
    # 向量化批量计算i到所有j>i点的距离，比逐点计算快数十倍
    delta = cities_arr[i+1:] - cities_arr[i]
    dist_flat[offset: offset + (n - i - 1)] = np.sqrt((delta ** 2).sum(axis=1))
    offset += n - i - 1

# 读取i,j距离的工具函数
def get_distance(i: int, j: int) -> np.float32:
    if i > j:
        i, j = j, i
    idx = i * n - i * (i + 1) // 2 + j - i - 1
    return dist_flat[idx]

方案2：放弃预计算，实时向量化算距离 #

贪心算法求解TSP的时间复杂度本身就是O(n²)，哪怕每一步都实时计算当前点到所有未访问点的距离，用numpy向量化实现的话速度也完全足够，连2GB的存储开销都可以省掉，适合内存更紧张的场景。

内容的提问来源于stack exchange，提问作者roberto tomás