时间戳

首页 > 解决方案 > 快速查找所有子集

python - 快速查找所有子集

问题描述

我有带有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 来说也是非常昂贵的。

标签： python

解决方案

根据字典的大小和键的长度，既不检查字典中的所有键也不枚举所有子集并检查它们是一个很好的解决方案。相反，您可以将“平面”字典重组为Trie 或 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)

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

推荐阅读