fdict 0.8.1

与 dict 的区别

尽管最大兼容性是主要目标，但不同的实现当然会带来不可避免的差异。

主要区别是，调用 items()、keys()、values() 和 view* 方法将返回任何级别的嵌套的所有子叶，而 dict 只返回直接子叶。默认情况下，这些方法只返回叶（非字典对象）而不是节点，尽管您可以通过提供 nodes=True 参数来覆盖此行为。

另一个区别是冲突：您可以有一个既是叶也是节点的项，因为没有方法可以检查没有节点（即使用 viewitems()，这是 fdict 数据结构的限制）。

这也意味着，当分配一个已分配的项时，节点不会替换，但单例将被正确替换。更具体地说

这有效

d = fdict({'a': 1, 'b': {'c': 2}})
d['a'] = -1
print(d)
d['a'] = {'d': 3, 'e': 4}
print(d)

{'a': -1, 'b/c': 2} {'a/d': 3, 'a/e': 4, 'b/c': 2}

但这不会按预期工作

d = fdict({'a': 1, 'b': {'c': 2}})
d['b'] = -1
print(d)

{'a': 1, 'b': -1, 'b/c': 2}

一个小的区别是键的处理：将空字典分配给键不会创建键（例如，d['a'] = {} 不会创建键 a，它将保持不存在，直到它被分配一个非空字典值），并且分配不存在的子键而无需先创建父字典是允许的（例如，d = fdict(); d['a']['b']['c']['d']['e'] = 1 是允许的）。

同样，keys()、values() 和 items() 将遍历所有嵌套层级的所有嵌套叶。为了方便探索，如果您希望有类似于 dict 的行为，只显示直接子节点，可以使用 viewkeys_restrict()、viewitems_restrict()、viewvalues_restrict()、firstkey()、firstitem()、firstvalue()。但是请注意，遍历的速度不会比遍历所有项目更快（因为内部实际上就是这样做的），所以您不能通过这些方法优化速度，它们只是为了方便。

另一个细微的区别是 pop() 和 popitem() 的处理方式：它们将返回任何嵌套层级的下一个叶，而不是节点。因此，您不能获取特定层级的下一个项目，而只能获取任何嵌套层级的下一个项目。

性能

fdict 是通过与 dict 的最大兼容性以及合理的性能来制作的。理论上是这样，但实际上 fdict 在大多数情况下都比 dict 慢，除非您使用直接访问形式（例如，x[‘a/b/c’] 而不是 x[‘a’][‘b’][‘c’]）。

因此，您可以期望对叶（非 dict 对象）的任何操作都具有与 dict 相同的 O(1) 性能：getitem、setitem、delitem、eq contains。实际上，由于类开销和键字符串操作，fdict 大约比 dict 慢 10 倍，无论是间接访问（即 x['a']['b']['c']）还是直接访问叶（即 x['a/b/c']）都要慢 3 倍。因此，如果您想要更快的设置和获取，则可能更喜欢直接访问形式。由于构建和检索项目是最常见的操作，因此这种性能成本对于大数据数据库的快速原型来说是可接受的。

主要的缺点出现在您处理节点（嵌套 dict 对象）时：由于所有键都展平并在同一级别，获取嵌套 dict（即分支）的子节点的唯一方法是遍历所有键并过滤出不符合当前分支的键。这意味着对节点的任何操作都将以 O(n) 的速度进行，其中 n 是整个 fdict 中的项目总数。受影响的操作包括：items、keys、values、view*、iter*、节点上的 delitem、节点上的 eq、节点上的 contains。

有趣的是，节点上的 getitem 不受影响，因为我们使用了懒加载方法：获取嵌套 dict 不会构建任何内容，它只会生成一个新的具有不同过滤根路径的 fdict。不会进行任何评估，直到您要么到达叶（在这种情况下，我们返回非 dict 对象值），要么在节点上使用操作，例如 items()。请注意，任何嵌套的 fdict 都会共享相同的内部展平字典，因此任何嵌套的 fdict 都可以访问任何级别的所有项目！

这是有意为之：fdict 是为了在构建和检索叶方面尽可能快，以换取较慢的探索速度。换句话说，您可以期望 fdict 的创建速度非常快，并且可以快速获取任何嵌套层级的任何叶对象，但在探索时应该小心。然而，即使您的字典比 RAM 大，您也可以使用 view* 方法（viewitems、viewkeys、viewvalues）将所有项目作为生成器进行遍历。

为了克服这个缺陷，实施了以下两点：

• 可以使用 extract() 方法对嵌套 fdict 进行操作，以过滤所有键一次并构建一个包含所有相关嵌套项的新 fdict。用法为 extracted_fdict = fdict({'a': {'b': 1, 'c': [2, 3]}})['a'].extract()。

• 在创建fdict时，可以使用fastview=True参数来启用快速查看模式。此模式将增加存储节点的小内存/空间开销，并将节点上的setitem操作复杂度提高到O(m*l)，其中m是当前叶子添加的父节点数量，l是添加的叶子数量（通常为1，但如果设置了字典，它将转换为多个叶子）。另一方面，它将通过使用查找表直接访问直接子节点来使项目、键、值、view*和其他节点操作方法与dict一样快，这是O(n)，其中n是任何级别的fdict中项目列表的整个列表。可以通过仅将其作为初始化字典提供来将非快速查看fdict转换为快速查看fdict。

• nodel=True参数激活了特殊模式，其中delitem被置为空，但节点键查找（包含测试）时间为O(1)。在标准fdict中，contains测试对于叶子为O(1)，对于节点为O(n)，因为它调用viewkeys()。在此模式下，创建空节点元数据，因此节点存在性查找非常快，但代价是删除操作不可用，因为这会使数据库不一致（即没有叶子的节点）。但是，用叶子替换setitem的操作仍然有效。此模式特别适用于快速数据库构建，然后您可以使用您的最终nodel fdict初始化标准fdict，然后您可以delitem。

因此，如果您想在fdict上进行数据探索，您可以使用这两种方法中的任何一种来加快您的探索速度，性能接近dict。在实践中，如果您每个嵌套级别有很多项目，则extract更好，而如果您有一个非常嵌套的结构，每个级别只有少量项目但有很多级别，则fastview可能更好。

如果你们有任何想法，请自由在Github上提出问题，以进行速度优化。

请注意，此模块与PyPy兼容，因此您可能可以使用此解释器获得速度提升。

无论如何，此模块主要用于快速原型设计大数据数据库，然后您可以在稍微重构结构后将其切换到另一个更快的数据库。

一个好的例子是检索在线数据：在这种情况下，您不太关心数据结构性能，因为它与网络带宽和I/O相比微不足道。然后，当您拥有数据时，您可以重新设计它以将其转换为具有平面模式的其他类型的数据库（通过仅提取您感兴趣的字段）。

此外，您可以使用to_dict()方法将fdict或sfdict转换为平面dict，或使用to_dict_nested()转换为嵌套（自然）dict，然后您将获得一个存储在RAM中的标准dict，您可以以全速访问它，或将其用作初始化其他类型的离线数据库的输入。

文档

class fdict(dict):
    '''
    Flattened nested dict, all items are settable and gettable through ['item1']['item2'] standard form or ['item1/item2'] internal form.
    This allows to replace the internal dict with any on-disk storage system like a shelve's shelf (great for huge nested dicts that cannot fit into memory).
    Main limitation: an entry can be both a singleton and a nested fdict: when an item is a singleton, you can setitem to replace to a nested dict, but if it is a nested dict and you setitem it to a singleton, both will coexist. Except for fastview mode, there is no way to know if a nested dict exists unless you walk through all items, which would be too consuming for a simple setitem. In this case, a getitem will always return the singleton, but nested leaves can always be accessed via items() or by direct access (eg, x['a/b/c']).

    Fastview mode: remove conflicts issue and allow for fast O(m) contains(), delete() and view*() (such as vieitems()) where m in the number of subitems, instead of O(n) where n was the total number of elements in the fdict(). Downside is setitem() being O(m) too because of nodes metadata building, and memory/storage overhead, since we store all nodes and leaves lists in order to allow for fast lookup.
    '''

    def __init__(self, d=None, rootpath='', delimiter='/', fastview=False, nodel=False, **kwargs):

class sfdict(fdict):
    '''
    A nested dict with flattened internal representation, combined with shelve to allow for efficient storage and memory allocation of huge nested dictionnaries.
    If you change leaf items (eg, list.append), do not forget to sync() to commit changes to disk and empty memory cache because else this class has no way to know if leaf items were changed!
    '''

    def __init__(self, *args, **kwargs):

LICENCE

本库采用MIT许可。最初是为Coma Science Group - GIGA Consciousness - CHU de Liege，比利时制作的。

包括由bfontaine编写的flatkeys函数和由zuo编写的_count_iter_items。