使用字典将列表分组的Pythonic方式，其中字典的值为列表

Question

我希望能以更加Pythonic或者高效的方式解决这个问题。我有一个字典，其值为集合（重复值在不同键中可能会出现）。给定一个列表，我必须创建一个字典，将每个类别映射到使用主字典中的键来获取元素。下面是一个例子来说明。 主字典

{
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
}

输入

['Foo', 'Bar', 'Dog', 'Aron']

输出

{
    "KeyA": ['Aron'],
    "KeyB": ['Bar', 'Foo', 'Dog'],
    "KeyZ": ['Foo', 'Bar']
}

我的现在想法

将集合中的每个项反转为键，然后进行查找。

注：本文是关于IT技术的翻译，涉及到一些专业术语，请您谨慎使用。

{
     'Aron'         : ['KeyA'],
     'Foo'          : ['KeyB', 'KeyZ'],
     'Bar'          : ['KeyB', 'KeyZ'],
     'Random Value' : ['KeyA', 'KeyZ']
}

我会通过遍历每个集合中的每一项来初始化反转字典。创建这样一个字典的近似时间为O(n)。在创建的反转字典中查找列表中的项，比如值为“Bar”。使用信息'Bar': ['KeyB', 'KeyZ']创建一个新的字典。结果字典将是{'KeyB': ['Bar']，'KeyZ': ['Bar']}。对于下一个项，我需要对现有字典进行一些记账，例如检查键是否存在，如果存在，则附加到现有列表中等等。

在映射到每个键的集合中使用in运算符（检查成员身份）。

大多数情况下，主字典和输入列表都很小（所有集合中少于500个唯一项）。因此，我可以在每个键返回的集合中检查成员身份并创建字典。这显然效率较低，但适用于大多数情况。

我还有几个类似于上面示例的操作。我不想为它们手动记账，因为这样容易出错且速度比内置函数慢。

我需要什么？

1.更好的方法（更快的算法） 2.内置于itertools中的函数，因为这些函数更快 3.第三方库 4.一些普通Python用户不知道的深奥解析？

- Abhirath Mahipal

---

为什么“sets”是列表而不是实际的集合？ - Stefan Pochmann

你的第一种方法很好。实现它吧。 - Stefan Pochmann

@StefanPochmann 因为允许重复，但是它们发生的可能性非常小。 - Abhirath Mahipal

如果值允许重复，你不能使用集合（set）。列表（list）是可以的。 - pylang

Answer 1

在开始转换之前，将列表转换为集合会更好。使用集合进行查找比在列表中进行线性搜索要快。

input_set = set(input)

一旦你有了它，你可以使用普通的字典推导式，在我看来：

output = {key: [x for x in value if x in input_set] for key, value in master_dict.items()}

结果：

output == {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']}

- UltraInstinct

Answer 2

一种方法是使用Python中的交集，如下所示：

x={
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
   }
items = ['Foo', 'Bar', 'Dog', 'Aron']

{k:  set(items).intersection(set(v)) for k, v in x.items()}

- Amir Naimi

---

set(items) & set(v) - Stefan Pochmann

交集很整洁 :) - Abhirath Mahipal

Answer 3

使用defaultdict和列表推导式怎么样？

from collections import defaultdict

result = defaultdict(list)

d = {
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
   }
items = ['Foo', 'Bar', 'Dog', 'Aron']

[result[k].append(e) for k,v in d.items() for e in v if e in items]

print(result) # defaultdict(<type 'list'>, {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']})

print(dict(result)) # {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']}

- Vivek Harikrishnan

Answer 4

另一种可能的方法：

可能加快在input_set中检查值是否存在的搜索时间的一种方法是使用二分搜索，其时间复杂度为O(logn)。

以下是一些示例代码，还使用了方便的collections.defaultdict：

from collections import defaultdict

master = {
          "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
          "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
          "KeyZ": ['Random Value', 'Foo', 'Bar']
         }    

input_set = ['Foo', 'Bar', 'Dog', 'Aron']

sorted_list = sorted(input_set)

d = defaultdict(list)
for key, value in master.items():
    for v in value:
        if binary_search(sorted_list, v):
            d[key].append(v)

print(d)

哪些输出：

defaultdict(<class 'list'>, {'KeyA': ['Aron'], 'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyZ': ['Foo', 'Bar']})

以下是定义了 binary_search() 的代码：

def binary_search(item_list,item):
    first = 0
    last = len(item_list)-1

    while first <= last:
        mid = (first + last)//2
        if item_list[mid] == item :
            return True
        elif item < item_list[mid]:
            last = mid - 1
        else:
            first = mid + 1 
    return False

上述代码似乎是重复造轮子。您可以查看bisect模块，该模块提供了一些调用二分搜索的方法，而无需编写自己的函数。

注意：为了使用二分搜索，您还需要事先对值进行排序，这是O(nlogn)。我不确定这会产生多大的影响，您需要使用另一种方法运行一些测试以查看差异。

此外，正如@SuperSaiyan发布的那样，将input_set转换为集合是最有效的方法，因为在最好的情况下，集合查找为O(1)，在最坏的情况下为O(n)(很少发生)。

- RoadRunner

---

@AbhirathMahipal 不用担心，我尽力提供了一个好的方法。给你最喜欢的答案打个绿色勾勾吧。我觉得这是一个有趣的问题，所以只是为了好玩而回答了它。 - RoadRunner

会看一下 bisect 模块。我反对使用集合，因为它可能包含重复项，但很不可能包含重复项。 - Abhirath Mahipal

是的，看起来你有一个有趣的问题。祝你好运，所有这些答案都应该为解决你的问题提供一些好的选项。 - RoadRunner

来吧...你不能认真地写 binary_search(sorted(input_set)。每次二分查找都进行排序完全是自毁前功的行为。应该只在设置期间排序一次。 - Stefan Pochmann

但我的观点是，这确实需要使用真实数据进行基准测试和讨论，至少当列表长度仅达到几百时。简单地陈述二分查找可以加速这一过程是误导性的，还可能具有潜在的危害性，这就是我为什么会投反对票的原因。 - Stefan Pochmann

Answer 5

OP提出了一个反向字典的建议。可以说这仍然是Pythonic的，因此以下是如何实现它。 假设

import collections as ct


master_dict = {
    "KeyA": ['Aron', 'Random Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
}

input_list = ['Foo', 'Bar', 'Dog', 'Aron']

代码

我们使用 collections.defaultdict 来简化列表值的创建。

reverse_dict = ct.defaultdict(list)
for k, v in master_dict.items():
    for item in v:
        reverse_dict[item].append(k)
reverse_dict

输出

defaultdict(list,
            {'Abhishek': ['KeyA'],
             'Aron': ['KeyA'],
             'Badge': ['KeyB'],
             'Ball': ['KeyB'],
             'Bar': ['KeyB', 'KeyZ'],
             'Dog': ['KeyB'],
             'Foo': ['KeyB', 'KeyZ'],
             'Random Value': ['KeyA', 'KeyZ']})

现在，由于可以通过键搜索输入，查找速度比搜索每个字符串列表要快。我们从一个查找值的输入列表构建最终的字典。

final_dict = ct.defaultdict(list)
for v in input_list:
    for k in reverse_dict[v]:
        final_dict[k].append(v)

final_dict

输出

defaultdict(list,
            {'KeyA': ['Aron'],
             'KeyB': ['Foo', 'Bar', 'Dog'],
             'KeyZ': ['Foo', 'Bar']})

@SuperSaiyan提出了通过搜索输入列表的集合来重建主字典每个键的列表。对于这个特定的应用程序来说，这是一个聪明而优越的方法。

- pylang