效率：Python中将2D列表转换为字典

Question

我有一个二维列表。

l = [[100, 1], [43, 2], [201, 1], [5, 7], ...]

我希望将列表转换为字典，其中第二个元素作为键。每个键的值应该是一个包含所有第一个元素的列表，这些元素的第二个元素作为键。 对于这个样本列表，字典应该如下所示：

{
    1: [100, 201],
    2: [43],
    7: [5],
    ...
}

我有两个解决方案来进行这种转换。哪一个更有效，为什么？还有：是否有其他更有效的解决方案？

解决方案1：

d = {}
for elem in l:
    if elem[1] in d:
        d[elem[1]].append(elem[0])
    else:
        d[elem[1]] = [elem[0]]

解决方案2：

d = {}

for elem in l:
    d[elem[1]] = []

for elem in l:
    d[elem[1]].append(elem[0])

- sinaj

Answer 1

你的两种解决方案都没有问题，它们都很好并且高效：

1. 解决方案 1 一次迭代列表，但进行了两次字典查找。由于这是关于 O(1) 的，而你有 2 次，所以我会说这是 2xN。
2. 解决方案 2 两次迭代列表，每次查找一次 - 再次是 2xN。

从理论角度来看，它们是相同的。我敢打赌，它们的运行时间也非常接近。可能可以改进第一种解决方案的一种更 Pythonic 的方式（不需要先判断再执行，感谢 @tobias_k）：

d = {}
for elem in l:
    try:
        d[elem[1]].append(elem[0])
    except KeyError:
        d[elem[1]] = [elem[0]]

如果您有许多重复的键，这种方法会更好，因为异常的开销比所有的if语句小得多（只需一次查找），因此这将取决于实际的列表。如果您选择这种解决方案，您可能需要阅读关于defaultdict的内容。 一些新信息 我的猜测是错误的！尽管理论上它们是相同的，并且似乎操作的数量也是相同的，但它们之间存在差异。我猜这与Python优化if语句的能力有关。

将您的第一个方法命名为a，第二个方法命名为b，我提供的方法命名为c，使用timeit模块，我对这些方法进行了两个列表的计时。

l1=[(x,y) for x,y in zip(range(1000),range(1000,2000)]
l1=[(x,2) for x,y in range(1000)]

l1的结果:

方法a最快。比它慢30%的是b，再从那里慢30%的是c。

l2的结果:

方法a和b几乎相同（a仍然稍微快一点），而c比两者都要快一些（这是我们预料的）。

我认为从实际角度考虑，第一个版本比第二个版本更好，但如果你有很多重复的键，则第三个版本最好。底线是，理论固然好，但最佳方法实际上取决于列表。

- kabanus

---

@tobias_k 好的，谢谢。我（错误地）将try-except与鸭子类型视为同义词。我想你可以说“把它当作一个列表，如果不行就捕获异常”，但我同意这有些牵强。 - kabanus

这仍然不是完全正确的。问题不在于它不是列表——否则会引发 TypeError 或 AttributeError。问题是它_根本不存在_。我认为你要找的概念是“宁愿请求原谅，而非事先征得许可”之类的东西。（这个表达式通常与鸭子类型结合使用，例如这里，但在这种情况下不应该这样做。） - tobias_k

@pogothebear 请接受您选择的答案，以造福未来的读者。 - kabanus

@kabanus 我想最好等待其他解决方案。 - rpanai

@user32185 或许吧。无论如何，只要解决方案回答了问题就应该被接受——如果有更好的方案出现，总是可以进行更改的。我只是向声望较低的人提供这些意见，因为他们经常把点赞与接受混淆，或者忘记接受（从我的经验来看）。 - kabanus

Answer 2

l = [[100, 1], [43, 2], [201, 1], [5, 7]]
d = dict(l)
print(d)

它将会给你输出如下结果：{100: 1, 43: 2, 201: 1, 5: 7}

- Hariprasad

---

仅当一个键最多只有1个值时才有效。 - alercelik

Answer 3

第一种解决方案更加高效，因为它只需要O(n)的时间来完成： if语句是O(1)，因为字典查找是O(1)。

第二种解决方案也是O(n)，但是它运行了两次，所以是O(n+n)。

在第一种解决方案中，你可以跳过if语句直接添加elem[0]，并添加一个try except块。

- Sum of N upto Infinity

---

但是第一个循环在每次迭代中执行两个操作，因此也是O(2n)。 - tobias_k

@tobias_k 正是，它执行两个操作。但我的疑问是 if 比 for 循环快一点，对吧？ - Vikas Periyadath

@VikasDamodar 是的，第一个版本可能更快。循环本身可能有一些（恒定的？）开销，并且您只初始化所需的列表数量，但仍然：说“它循环两次，所以它必须比另一个循环一次慢”最多是误导性的。 - tobias_k

@tobias_k 我明白了，那么我的解决方案呢？需要更多时间吗？ - Vikas Periyadath

@VikasDamodar，你应该检查setdefault的复杂度，它可能比if更快，但可能无法胜任异常处理。 - Sum of N upto Infinity

Answer 4

我认为解决方案1比解决方案2更有效，因为它只有一个循环。我认为你可以尝试下面的代码，可能比解决方案1更有效。

l = [[100, 1], [43, 2], [201, 1], [5, 7]]
d = {}
for k, v in l:
    d.setdefault(v, []).append(k)
print(d)

它的输出如下所示：

{1: [100, 201], 2: [43], 7: [5]}

- Vikas Periyadath

---

在我看来，这个解决方案始终比 OP solution1 慢。 - rpanai

@user32185 在 OP 的解决方案 1 中，它通过一个 if:..else 进行处理。因此，当它与设置默认值一起执行时，时间可能会稍微减少，因为它在每个循环中只执行一次。 - Vikas Periyadath

Answer 5

你的两个解决方案的时间复杂度都是O(n)。但你可以使用collections.defaultdict:

from collections import defaultdict

l = [[100, 1], [43, 2], [201, 1]]

d = defaultdict(list)

for v, k in l:
    d[k].append(v)

# defaultdict(list, {1: [100, 201], 2: [43]})

一些基准测试：

from collections import defaultdict
import numpy as np

l = np.random.randint(1, 100, [int(1e7), 2])

def dd(l):
    d = defaultdict(list)

    for i in l:
        d[i[1]].append(i[0])

    return d

def op(l):
    d = {}
    for elem in l:
        if elem[1] in d:
            d[elem[1]].append(elem[0])
        else:
            d[elem[1]] = [elem[0]]    

    return d

%timeit dd(l)  # 1 loop, best of 3: 8.22 s per loop
%timeit op(l)  # 1 loop, best of 3: 9.47 s per loop

- jpp

---

我觉得这比原始方案慢了2倍。 - rpanai

我不确定那是一个好的基准列表。我使用了这个 l = np.random.randint(1, 100, [int(1e7), 2])。 - rpanai

@user32185，已根据您的输入进行了更新，并进行了微小的改进。 - jpp