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

Question

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

我有几种类型的房间，它们有一个名称和一个门列表:

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

对于目前的 map ，我保留了位置和房间类型的字典:

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)查找，也就是说，它所花费的时间与您拥有的类型的数量成正比。请注意，如果您使用 list 而不是 set 来存储给定类型的房间，这将增长到 O(nrooms * ntypes) ，这会扼杀你的表现。

与往常一样，在优化时，重要的是要考虑优化对内存使用和 CPU 时间的影响。两人经常不和。

作为替代方案，如果您的 map 足够矩形，您可以考虑将类型保存在二维 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__ 定义 Position 类告诉 Python 如何分配内存，并添加 xpos和 ypos类的属性。您不想在代码中乱扔 pos / 1000和 pos % 1000陈述。