Python中多个字典和列表字典的高效快速数据存储和处理，以及两个列表字典的交集。

Question

我有一个表单的字典，例如：

 all_ways = {key1:[list1], key2:[list2], ... keyN[listN]}

我想要找到第ith个列表中那些属于至少另一个列表，比如说第j个列表(i!=j)的元素，然后对于所有键只存储满足上述条件的元素。

除了使用多重循环外，还有没有好的方法来实现这一点？

示例：

key1: [1,2,3,4,5,100,111,123] 
key2: [1,2,3,13,15,17] 
key3:[100,110,111,1000] 

answer:

key1:[1,2,3,100,111] 
key2:[1,2,3]
key3:[100,111]

- Divyang Vashi

---

每个键平均有50个元素的列表，共有70,000个键。 - Divyang Vashi

可能可以使用字典推导式和单循环来高效处理。但我会等待看看是否有人提供其他的方法。 - jpp

键1：[1,2,3,4,5,100,111,123] 键2：[1,2,3,13,15,17] 键3：[100,110,111,1000]答案： 键1：[1,2,3,100,111] 键2：[1,2,3] 键3：[100,111] - Divyang Vashi

列表中是否会有重复项？ - Joe Iddon

每个键的元素顺序在答案字典中是否重要？ - MaxPowers

Answer 1

您可以按照列表元素的总数在线性时间内（无嵌套循环）实现此操作：

from collections import Counter
from itertools import chain

d = {'key1': [1,2,3,4,5,100,111,123],
     'key2': [1,2,3,13,15,17],
     'key3': [100,110,111,1000]}

# histogramm over the chained lists
c = Counter(chain(*d.values()))  
# c = Counter(chain(*map(set, d.values())))  # if there are duplicates in the lists

# for every key k in d, pick only those elements x from their value lists v
# that occur more than once overall (thus in multiple lists)
result = {k: [x for x in v if c[x] > 1] for k, v in d.items()}
# {'key1': [1, 2, 3, 100, 111], 
#  'key2': [1, 2, 3], 
#  'key3': [100, 111]}

collections.Counter 可以忽略单个列表内的重复项（通过 set），记录每个独特元素出现在多少个列表中。嵌套推导式仅选择计数大于 1 的元素，从而确保它们出现在多个列表中。

- user2390182

---

好的，这非常有帮助。如果您能告诉我算法是如何工作的，而不仅仅是实现，那就太好了。 - Divyang Vashi

性能方面的一个明显点。Counter在注册了2个项目后并不会停止计数。因此，它比应该做的多做了一些工作。 - jpp

@DivyangVashi，我加了一些解释。 - user2390182

@jp_data_analysis 这是正确的，但你无论如何都需要查看每个元素，才能知道是否已经看过两次。实现自己的检查几乎不可能超越优化的计数器。 - user2390182

@schwobaseggl，嗯，你每次都在保存更新字典值。在这个（相对较小的）数据集中，这是可以接受的。只是一个观察。我已经为你的答案点赞了，它是最干净的解决方案。 - jpp

Answer 2

以下是一些其他方法，并对真实数据集进行基准测试。本答案假设列表内没有重复项，并且输出的顺序（每个键的重复项）无关紧要。

import numpy as np
from itertools import groupby, chain
from collections import Counter

d = {'key'+str(i): list(np.random.randint(0, 1000000, 50)) for i in range(1, 50000)}

def return_dups_jp1(d):
    def get_dups(a):
        seen = set()
        dup = set()
        for x in a:
            if x not in seen:
                seen.add(x)
            else:
                dup.add(x)
        return dup

    def apply_dups(d, dups):
        return {k: list(set(v) & dups) for k, v in d.items()}

    return apply_dups(d, get_dups(chain.from_iterable(d.values())))

def return_dups_jp2(d):
    b = sorted(chain.from_iterable(d.values()))
    dups = {group[0] for group in groupby(b) if len(list(group[1])) > 1}
    return {k: list(set(v) & dups) for k, v in d.items()}

def return_dups_sch(d):
    c = Counter(chain(*d.values()))
    return {k: [x for x in v if c[x] > 1] for k, v in d.items()}

基准测试：

x = return_dups_jp1(d)
y = return_dups_jp2(d)
z = return_dups_sch(d)

assert all(set(x['key'+str(i)]) == set(y['key'+str(i)]) for i in range(1, 50000))
assert all(set(y['key'+str(i)]) == set(z['key'+str(i)]) for i in range(1, 50000))

%timeit return_dups_jp1(d)
# 1 loop, best of 3: 2.56 s per loop

%timeit return_dups_jp2(d)
# 1 loop, best of 3: 5.12 s per loop

%timeit return_dups_sch(d)
# 1 loop, best of 3: 2.66 s per loop

- jpp