延迟创建python dict直到set/upd

Question

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

理想情况下，我甚至希望延迟创建内部dict，直到在内部dict中设置了一个键值对。此对象的行为类似于get和getitem调用的空dict，但只要setitem或update调用进入，它就会创建一个空dict来代替它。我在让delaydict对象知道如何将新的空dict与dict结构的dict相连接时遇到了问题。你知道吗

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存储在dict of dict结构中，以便它将DelayDict类替换为内部dict。我知道属性可以做类似的事情，但我相信当我尝试在外部dict中替换自己时，同样的基本问题也会出现

Answer 1

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

如果你被一个又一个的格言困住了，这里有一个解决办法。你知道吗

首先，您需要一种方法来在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，谢谢！）。你得给我个建议 占位符，当有人要求的价值。占位符跟踪外部dict和外部dict中的键。它包装一个dict，并在赋值时将此dict赋给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，你 查看堆栈，如果占位符只有一个ref（sys.getrefcount(ph) == 1），则可以使用它。当你在寻找 一个免费的占位符，你可以记住最大refcount的占位符。您可以用这个“max refcount”占位符切换空闲占位符。因此，占位符的最大 refcount被发送到堆栈的底部。你知道吗