1

我正在尝试编程珍珠之一：

给定一个最多包含一千万个没有重复的 7 位整数的文件。仅使用 1.5Mb RAM 并仅读取一次数据以升序打印这些数字的有效方法是什么？只有 1Mb 的 RAM 而没有其他存储的后果是什么？如果允许重复，您的答案将如何变化？

为了创建一个测试用例，我生成了 8999999 个数字并将它们写入一个文件。然后对于每一行，我开始将相同的插入到树中，最后创建一个 trie 结构。

示例代码：

from sys import getsizeof

tree = dict()
xtree = dict()
f = open("data2.txt", "r")
cnt = 0
for number in f:
    cnt += 1
    currTree = tree
    xtree[number] = dict()
    for n in number.strip():
        if n not in currTree:
            currTree[n] = dict()
        currTree = currTree[n]
f.close()

print(cnt)
print(getsizeof(tree))
print(getsizeof(xtree))
print(tree)

示例文件 data2.txt 有 20 条记录

生成的树是

生成的树

现在的问题是，当我对构建的树进行内存大小调整时，它在 20 行显示了 240 字节的内存占用空间

在 100 行，树的大小变为 368 字节

在 8999999 行也给出 368 个字节

我建立了一个名为的辅助地图xtree，它只提供数据

xtree 和 tree 的大小以字节为单位。

数据分析

谁能解释一下这是怎么回事..??

4

1 回答 1

4

你tree只是一个最多包含 10 个键值对的字典。在更大的树中，没有更多的键值对。键值对中的 ... 中的值内有更多值，但字典中仍然只有 10 个键值对。一个包含大约 10 个键值对、占用 368 个字节的 dict 似乎是您所期望的。1

正如文档getsizeof所说：

仅考虑直接归因于对象的内存消耗，而不考虑它所引用的对象的内存消耗。

…</p>

有关使用递归查找容器大小及其所有内容的示例，请参见recursive sizeof recipe 。getsizeof()

因为您实际上并没有完全任意的数据结构，而只是一个 dict 等的 dict。而且，虽然您确实有一些共享引用（例如，如果您在读取数字1234567时已经有一个 int 具有相同的值内存，Python 只会重用相同的对象），如果您尝试验证是否可以放入 1.5MB，那么您确实需要最坏情况的测量，因此您可能希望跳过对已经看到的值的检查。

所以，如果你愿意，你可以写一些更简单的东西而不是使用那个食谱。但想法是一样的：

def total_dict_size(d):
    size = sys.getsizeof(d)
    if isinstance(d, dict):
        for key, value in d.items():
            size += sys.getsizeof(key) + total_dict_size(value)
    return size

xtree另一方面，您的 dict 是一个包含 8999999 个键值对的字典。做同样的粗略计算，我预计会低于 300MB。相反，它有点超过 300MB。足够接近。

而且您还在堆上存储了 8999999 个 7 位整数。取一些漂亮的整数，假设有 5M 不同的整数不属于 CPython 预先创建和缓存的少数小值。这些整数中的每一个都小到可以放入一个 30 位数字，因此在 64 位 CPython 上它们每个占用 28 个字节。因此，如果您在或上调用上面的递归函数，那还有另外 140MB 没有被计入sys.getsizeof(xtree)（但它们被计入了——事实上，被多计了，给出了最坏情况的测量实现）。treextree

tree因此，您在、和实际整数之间的总内存使用xtree量可能在 750MB 左右，这不太符合< 1.5MB要求。

1. 每个 Python 对象都有一些固定的标头开销，例如引用计数、指向类型的指针等，以及特定于类型的东西，例如大多数容器类型的长度。称之为 64 字节。一个 dict 然后有一个哈希表。它需要比 10 个插槽大一点，以保持负载远低于 1.0；称之为 13 个插槽。每个插槽都需要一个哈希值、一个对键的引用和一个对值的引用，所以这是 3 个指针，或 24 个字节。64 + 13 * 24 = 376。所以粗略计算只减少了 8 个字节……</sub>

于 2018-07-31T18:30:59.360 回答