代码之家 › 专栏 › 技术社区 › Alex Osheter

比较三个(或更多)字典,如果至少两个字典相等,则查找匹配项

design-patterns algorithm python

Alex Osheter · 技术社区 · 7 年前

我面临着一个类似于 this one . 然而,这个问题严格地集中在三个变量上。我正在寻找一个解决方案,该方案也适用于三个以上。

这是我的两个变量代码:

for track_a in collection_a:
    for track_b in collection_b:

        t1 = track_a["tempo"]
        t2 = track_b["tempo"]
        k1 = track_a["key"]
        k2 = track_b["key"]
        m1 = track_a["mode"]
        m2 = track_b["mode"]

        if (t1 == t2) and (k1 == k2) and (m1 == m2):
            collection_c.append((track_a, track_b))

下面是我对三个变量的解决方案:

for track_a in collection_a:
    for track_b in collection_b:
        for track_c in collection_c:

            t1 = track_a["tempo"]
            t2 = track_b["tempo"]
            t3 = track_c["tempo"]
            k1 = track_a["key"]
            k2 = track_b["key"]
            k3 = track_c["key"]
            m1 = track_a["mode"]
            m2 = track_b["mode"]
            m3 = track_c["mode"]

            a = (t1 == t2) and (k1 == k2) and (m1 == m2)
            b = (t2 == t3) and (k2 == k3) and (m2 == m3)
            c = (t3 == t1) and (k3 == k1) and (m3 == m1)

            if a: collection_c.append((track_a, track_b))
            if b: collection_c.append((track_b, track_c))
            if c: collection_c.append((track_c, track_a))

显然,这个解决方案是不可扩展和缓慢的。考虑到我必须检查所有的组合,我怀疑它是否会很快,因为我们必须对所有可能的组合进行迭代,但我至少可以使其扩展吗?(至少5个)。此外,如果可能,允许以后添加更多比较特征。

3 回复 | 直到 7 年前

blhsing 7 年前

在线性时间内解决此问题的一种有效方法是将dict转换为冻结的键值元组集(在用于相等性测试的键上),以便它们本身可以散列并用作dict键(签名),这样您就可以简单地使用set的dict对它们进行分组:

groups = {}
for track in collections: # collections is a combination of all the collections you have
    groups.setdefault(frozenset((k, track[k]) for k in ('tempo', 'key', 'mode')), set()).add(track['name'])

以便:

[group for group in groups.values() if len(group) >= 3]

将返回签名相同的3个曲目的名称集列表。

btilly 7 年前

这里有一个逻辑上可扩展的解决方案 n 正在比较的词典 m 价值观需要时间 n*m 评估。

请注意,如果三个匹配,我将返回一组3。很容易,然后把它吹到所有匹配的对上。但是如果你这样做,那么你可以退回一些尺寸的东西 n*n . 我已经给你看了他们的样子。

def group_on(variables, *tracks):
    # Build a trie first.
    trie = {}
    for track in tracks:
        this_path = trie
        for variable in variables:
            value = track[variable]
            if value not in this_path:
                this_path[value] = {}
            this_path = this_path[value]
        if 'final' not in this_path:
            this_path['final'] = [track]
        else:
            this_path['final'].append(track)

    def find_groups(this_path, count):
        if 0 == count:
            if 1 < len(this_path['final']):
                yield this_path['final']
        else:
            for next_path in this_path.values():
                for group in find_groups(next_path, count-1):
                    yield group

    for group in find_groups(trie, len(variables)):
        yield group

def group_to_pairs(group):
    for i in range(len(group)-1):
        for j in range(i+1, len(group)):
            yield (group[i], group[j])

print('Efficient version')

for group in group_on(['tempo', 'key', 'mode'],
        {'track': 1, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 2, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 3, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 4, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 5, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        ):
    print(group)

print('Versus')

for group in group_on(['tempo', 'key', 'mode'],
        {'track': 1, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 2, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 3, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        {'track': 4, 'tempo': 1, 'key': 'A', 'mode': 'major'},
        {'track': 5, 'tempo': 1, 'key': 'A', 'mode': 'minor'},
        ):
    for pair in group_to_pairs(group):
        print(pair)

tnt 7 年前

找到一些有用的 itertools ,不确定这是否是您想要的:

from itertools import product, combinations

all_collections = [collection_a, collection_b, collection_c] # d, e, f, ...
for collections in combinations(all_collections, 2):         # Pick 2 (or any number) collections from all collections
    for tracks in product(*collections):                     # Cartesian product of collections or equivalent to for track1 in collection1: for track2 in collection2: ...
        if True:                                             # check if all tracks are matched
            print(*tracks)                                   # or append them to another collection