延迟创建 python 字典直到 set/update

Question

我有一个 Python dict-of-dict 结构，其中包含大量外部字典键（数百万到数十亿）。内部字典大部分是空的，但可以存储键值对。目前我创建了一个单独的字典作为每个内部字典。但它使用了很多我最终没有使用的内存。每个空字典都很小，但我有很多。我想延迟创建内部字典，直到需要时再创建。

理想情况下，我什至想延迟创建内部字典，直到内部字典中的键值对 set。我设想对所有外部字典值使用单个 DelayDict 对象。这个对象对于 get 和 getitem 调用来说就像一个空字典，但是一旦 setitem 或更新调用进来，它就会创建一个空的dict 取而代之。我运行遇到麻烦让 delaydict 对象知道如何将新的空字典与字典结构连接起来。

class DelayDict(object):    % can do much more - only showing get/set
    def __init__(self, dod):
        self.dictofdict = dod     % the outer dict
    def __getitem__(self, key):
        raise KeyError(key)
    def __setitem__(self, key, value):
        replacement = {key: value}
        % replace myself in the outer dict!!
        self.dict-of-dict[?????] = replacement

我想不出如何在 dict-of-dict 结构中存储新的替换字典，以便它替换 DelayDict class 作为内部字典。我知道属性可以做类似的事情，但我相信当我试图在外部字典中替换自己时，也会出现同样的根本问题。

Answer 1

老问题，但我遇到了类似的问题。我不确定这是一个尝试节省一些内存是个好主意，但如果你真的需要这样做，你应该尝试构建自己的数据结构。

如果你被 dict of dict 困住了，这里有一个解决方案。

首先，您需要一种方法来在 OuterDict 中创建没有值的键（默认值为 {}）。如果 OuterDict 是 dict __d:

的包装器

def create(self, key):
    self.__d[key] = None

你会节省多少内存？

>>> import sys
>>> a = {}
>>> sys.getsizeof(a)
136

正如您所指出的，None 仅创建一次，但您必须保留对它的引用。在 Cpython（64 位）中，它是 8 个字节。对于 10 亿个元素，您可以节省 (136-8)* 10**9 字节 = 128 Gb（而不是 Mb，谢谢！）。你需要给一个有人询问价值时的占位符。占位符跟踪外部字典和外部字典中的键。它包装了一个字典，并在你赋值时将这个字典赋值给 outer[key]。

不多说了，代码：

class OuterDict():
    def __init__(self):
        self.__d = {}

    def __getitem__(self, key):
        v = self.__d[key]
        if v is None: # an orphan key
            v = PlaceHolder(self.__d, key)
        return v

    def create(self, key):
        self.__d[key] = None

class PlaceHolder():
    def __init__(self, parent, key):
        self.__parent = parent
        self.__key = key
        self.__d = {}

    def __getitem__(self, key):
        return self.__d[key]

    def __setitem__(self, key, value):
        if not self.__d:
            self.__parent[self.__key] = self.__d  # copy me in the outer dict
        self.__d[key] = value

    def __repr__(self):
        return repr("PlaceHolder for "+str(self.__d))

    # __len__, ...

一个测试：

o = OuterDict()
o.create("a") # a is empty
print (o["a"])

try:
    o["a"]["b"] # Key Error
except KeyError as e:
    print ("KeyError", e)

o["a"]["b"] = 2
print (o["a"])

# output:
# 'PlaceHolder for {}'
# KeyError 'b'
# {'b': 2}

为什么它不使用太多内存？因为您没有构建数十亿个占位符。当您不再需要它们时，您可以释放它们。也许您一次只需要一个。

可能的改进：您可以创建 PlaceHolders 的池。堆栈可能是一个很好的数据结构：最近创建的占位符可能很快就会被释放。当你需要一个新的 PlaceHolder 时，你查看堆栈，如果占位符只有一个引用 (sys.getrefcount(ph) == 1)，则可以使用它。为了加快流程，当你在寻找一个免费的占位符，您可以记住具有最大引用计数的占位符。您将自由占位符与此 "max refcount" 占位符切换。因此，具有最大的占位符 refcount 被发送到堆栈底部。

延迟创建 python 字典直到 set/update

Delay creating python dict until set/update

python

dictionary

properties

lazy-initialization