为什么我的内存足迹在这种贪婪的 tsp 方法中爆炸了？

Question

我有一个作业要使用贪婪的方法来满足 TSP。问题有33708个城市。因为我从之前的任务中获得了很多有用的工具，所以我决定重用该方法并预先计算距离。

所以这仅仅超过 50 亿个条目（33708 选择 2），每个条目都适合 float32。同样，x 和 y 坐标是数字 $|n| < 10000 $，小数点后不超过 4 位。

我的 python 同样是：

def get_distance(left, right):
  """ return the euclidean distance between tuples left and right, which are coordinates"""
  return ((left[0] - right[0]) ** 2 + (left[1] - right[1]) ** 2) ** 0.5

# precompute all distances
distances = {}
for i in range(len(cities)):
  for j in range(i + 1, len(cities)):
    d = get_distance(cities[i], cities[j])
    distances[frozenset((i, j)))] = d

我预计这会占用 (3 * 32b) * 568m ≈ 6.7 GB 的内存。但事实上，在我的 jupyter notebook 中观看实时运行时，它似乎甚至超过了 35GB。（442s 和计数）我不得不杀死它，因为我已经进入我的交换 space 并且它慢了很多。有谁知道为什么它这么大？

更新：再次尝试使用 tuple(sorted((i,j))) -- 但已经达到 110s，它是 15GB 并且还在计算中

尺码

>>> import sys
>>> a = frozenset((1,2))
>>> sys.getsizeof(a)
216
>>> sys.getsizeof(tuple(sorted((1,2))))
56
>>> sys.getsizeof(1)
28

python有没有float32和int16之类的东西？？ -- 答：numpy 有它们

更新尝试：

from numpy import float32, int16
from itertools import combinations
import sys

def get_distance(left, right):
  """ return the euclidean distance between tuples left and right, which are coordinates"""
  return float32(((left[0] - right[0]) ** 2 + (left[1] - right[1]) ** 2) ** 0.5)

# precompute all distances
distances = {}
for i, j in combinations(range(len(cities)), 2):
    distances[tuple(sorted((int16(i), int16(j))))] = get_distance(cities[i], cities[j])

print(sys.getsizeof(distances))

观察到的尺寸：

与 cities = cities[:2] : 232
与 cities = cities[:3] ：还有 232
与 cities = cities[:10] : 2272
与 cities = cities[:100] : 147552
与 cities = cities[:1000]：20971608 (20MB)
与 cities = cities[:10000]：2684354656 (2.6GB)

请注意，即使我们接近 5000 万个条目，即 10000 个选择 2（数据总大小的 10%），增长率也不会随数据缩放：

2684354656/(1000选2 / 100选2 * 20971608) ≈ 1.27
20971608/(1000选2 / 100选2 * 147552)≈1.4

我决定停止对完整城市列表的尝试，因为我的 OS 内存快照增长到远远超过 30GB，我打算交换。这意味着，即使最终对象有那么大，笔记本所需的内存量仍然要大得多。

Answer 1

Python 对象由于动态类型和引用计数而产生开销。绝对最小对象 object() 的大小为 16 字节（在 64 位机器上）。 8 字节引用计数，8 字节类型指针。没有 python 物体可以比那个小。 float 和 int 稍大，至少 24 字节。 list 至少是一个指针数组，它增加了一个额外的 8 字节。因此，十亿个整数列表的小内存占用可能是 32 * 500_000_000 ~= 16Gb。 sets 和 dicts 甚至比那个更大，因为它们每个元素存储的不仅仅是一个指针。

使用numpy（也许stdlib array模块已经足够了）

（注意：numpy的float32类型也不能小于16字节）

为什么我的内存足迹在这种贪婪的 tsp 方法中爆炸了？

why is my memory footprint blowing up in this greedy approach to tsp?

python

jupyter-notebook

np-complete

尺码

更新尝试：