python内存使用dict和变量大数据集

Question

所以,我在Python 3.4中制作游戏.在游戏中我需要跟踪地图.它是连接房间的地图,从(0,0)开始并在每个方向继续,以过滤随机方式生成(下一个位置的正确匹配用于随机列表选择).

我有几种类型的房间,有名称和门列表:

RoomType = namedtuple('Room','Type,EntranceLst')
typeA = RoomType("A",["Bottom"])
...

对于目前的地图,我保留了一个位置和房间类型的字典:

currentRoomType = typeA
currentRoomPos = (0,0)
navMap = {currentRoomPos: currentRoomType}

我有循环,生成9.000.000个房间,以测试内存使用情况.当我运行它时,我得到大约600和800Mb.我想知道是否有办法优化它.

我尝试过而不是做

navMap = {currentRoomPos: currentRoomType}

我会做

navMap = {currentRoomPos: "A"}

但这并没有真正改变用法.

现在我想知道我是否能 - 并且应该 - 保留所有类型的列表,并且对于每种类型保持它发生的位置.但是我不知道它是否会对python管理变量的方式产生影响.

这几乎是一个思想实验,但如果有任何有用的东西来自它,我可能会实现它.

Answer 1

您可以使用sys.getsizeof(object)来获取 Python 对象的大小。但是，调用容器时必须小心sys.getsizeof：它只给出容器的大小，而不是内容 - 请参阅此配方以了解如何获取容器的总大小（包括内容）。在这种情况下，我们不需要太深入：我们只需手动添加容器的大小及其内容的大小即可。

相关类型的大小为：

# room type size
>>> sys.getsizeof(RoomType("A",["Bottom"])) + sys.getsizeof("A") + sys.getsizeof(["Bottom"]) + sys.getsizeof("Bottom")
233

# position size
>>> sys.getsizeof((0,0)) +  2*sys.getsizeof(0)
120

# One character size
>>> sys.getsizeof("A")
38

让我们看看不同的选项，假设你有 N 个房间：

1. 词典来自position -> room_type. 这涉及到N*(size(position) + size(room_type)) = 353 N在内存中保存字节。
2. 词典来自position -> 1-character string. 这涉及到N*158在内存中保存字节。
3. 词典来自type -> set of positions. 这涉及到保留N*120字节以及存储字典键的微小开销。

就内存使用而言，第三种选择显然更好。然而，通常情况下，您需要权衡 CPU 内存。值得简要考虑一下您可能执行的查询的计算复杂性。要在给定位置的情况下查找房间的类型，对于上述三个选择中的每一个，您必须：

1. 在字典中查找位置。这是一个 O(1) 查找，因此您将始终具有相同的运行时间（大约），与房间数量无关（对于大量房间）。
2. 相同的
3. 查看每种类型，并针对每种类型询问该位置是否在该类型的位置集中。这是一个O(ntypes)查找，也就是说，它所花费的时间与您拥有的类型数量成正比。请注意，如果您使用列表而不是集合来存储给定类型的房间，则该值将增长到O(nrooms * ntypes)，这会降低您的性能。

与往常一样，优化时，考虑优化对内存使用和 CPU 时间的影响非常重要。两人经常发生争执。

作为替代方案，如果您的地图足够矩形，您可以考虑将类型保留在二维 numpy 字符数组中。我相信这会更有效率。numpy 数组中的每个字符都是一个字节，因此内存使用量会少得多，并且从房间位置到类型查找的 CPU 时间仍然是 O(1)：

# Generate random 20 x 10 rectangular map
>>> map = np.repeat('a', 100).reshape(20, 10)
>>> map.nbytes
200 # ie. 1 byte per character.

一些额外的小规模优化：

将房间类型编码为 int 而不是字符串。整型的大小为 24 字节，而单字符字符串的大小为 38 字节。

将位置编码为单个整数，而不是元组。例如：

# Random position
xpos = 5
ypos = 92

# Encode the position as a single int, using high-order bits for x and low-order bits for y
pos = 5*1000 + ypos

# Recover the x and y values of the position.     
xpos = pos / 1000
ypos = pos % 1000

请注意，这会降低可读性，因此只有当您想充分利用最后一点性能时才值得这样做。实际上，您可能希望使用 2 的幂而不是 10 的幂作为分隔符（但 10 的幂有助于调试和可读性）。请注意，这会将每个位置的字节数从 120 增加到 24。如果您确实遵循此路线，请考虑定义一个 Position 类，用于__slots__告诉 Python 如何分配内存，并向该类添加xpos和属性。ypos您不想在代码中乱扔pos / 1000andpos % 1000语句。