python - 快速找到所有子集

Question

我有带 frozenset 键的大字典。我需要找到属于给定键子集的所有键。我看到了显而易见的方法:

dictionary = {
    frozenset([1]): 1,
    frozenset([2]): 2,
    frozenset([3]): 3,
    frozenset([3, 4]): 34
}
biglist= [3, 4, 5]
results = {k: v for k, v in dictionary.items() if k.issubset(biglist)}
assert results == {frozenset([3]): 3, frozenset([3, 4]): 34}

但是对于百万键来说它是非常慢的。问题是:这种类型的快速搜索是否有任何结构？

UPD:基本上，我不想遍历在每个键上执行 issubset 的所有键。相反，我可以从 biglist 生成所有可能的集合并检查它是否在字典中:

results = {}
maxkey = max(dictionary, key=len)
maxlen = len(dictionary[maxkey])
for lenght in range(1, maxlen):
    for subset in itertools.combinations(biglist, lenght):
        key = frozenset(subset)
        if key in dictionary:
            results[key] = dictionary[key]

但是这种方法对于长biglist也是非常昂贵的。

Answer 1

根据字典的大小和键的长度，检查字典中的所有键或枚举所有子集并检查它们都不是一个好的解决方案。相反，您可以将“平面”字典重组为类似 Trie, or Prefix Tree 的内容。 .在这里，集合中的每个元素都将指向树的另一个分支和/或实际值:

dictionary = {
    frozenset([1]): 1,
    frozenset([2]): 2,
    frozenset([3]): 3,
    frozenset([3, 4]): 34
}

def totree(d):
    tree = {}
    for key in d:
        t = tree
        for x in sorted(key):
            t = t.setdefault(x, {})
        t["value"] = d[key]
    return tree

tree = totree(dictionary)
# {1: {'value': 1}, 2: {'value': 2}, 3: {'value': 3, 4: {'value': 34}}}

现在，您可以递归地检查这些树并yield 每个有值的键。除了枚举所有子集之外，这只会扩展那些到目前为止所有元素都在树中的分支。

def check_subsets(tree, key, prefix=[]):
    if "value" in tree:
        yield prefix, tree["value"]
    for i, x in enumerate(key):
        if x in tree:
            yield from check_subsets(tree[x], key[i+1:], prefix+[x])

biglist= [3, 4, 5]
res = list(check_subsets(tree, sorted(biglist)))
# [([3], 3), ([3, 4], 34)]

请注意，按排序顺序添加/检查树中的键和查找键非常重要，否则可能会遗漏相关子树。

附录 1:这应该很清楚，但只是为了确保:当然，如果您为每次查找重新构建树，这种方法将无济于事，否则您也可以做一个线性的扫描所有键。相反，您必须创建一次树，然后重复使用它进行多次查找，并可能使用添加到集合中的新元素更新它。

附录 2:除了 "value"，您当然可以使用任何键作为前缀树中该节点的实际值。您可以使用 None，或者一个非常长的字符串或保证不会成为您的任何键集中的元素的大随机数。通过对 totree 和 check_subtree 函数进行一些调整，您还可以定义一个自定义的 Tree 类...

class Tree:
    def __init__(self, value=None, children=None):
        self.value = value
        self.children = children or {}
    def __repr__(self):
        return "Tree(%r, %r)" % (self.value, self.children)

...但是恕我直言，仅使用带有一些特殊值键的嵌套字典更简单。