python 内存使用字典和变量大型数据集

Question

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

我有几种类型的房间，它们都有名称和门列表：

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 时必须小心：它只给出容器的大小，而不是内容——有关如何获取容器总大小的说明，请参见 this 方法容器，包括内容物。在这种情况下，我们不需要进行得如此深入：我们可以手动将容器的大小与其内容的大小相加。

相关类型的大小是：

# 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 个房间：

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

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

查字典。这是一个复杂度为 O(1) 的查找，因此您将始终拥有相同的运行时间（大约），与房间数量无关（对于大量房间）。
相同
查看每种类型，并针对每种类型询问该位置是否在该类型的位置集中。这是一个 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。如果您确实沿着这条路走下去，请考虑使用 __slots__ 定义位置 class 来告诉 Python 如何分配内存，并将 xpos 和 ypos 属性添加到 class。您不想在代码中乱扔 pos / 1000 和 pos % 1000 语句。

python 内存使用字典和变量大型数据集

python memory usage dict and variables large dataset

python

python-3.4