python - 效率 : 2D-list to dictionary in python

Question

我有一个二维列表。

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

我想将列表转换为字典，其中第二个元素作为键。每个键的值应该是所有第一个元素的列表，将键作为第二个元素。此示例列表的字典应如下所示:

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

对于这种转换，我有两种解决方案。其中哪一个更有效，为什么？另外:还有其他更有效的解决方案吗？

解决方案一:

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])

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 语句的能力有关。

使用 timeit 标记您的第一个方法 a、第二个方法 b 和我提供的方法 c模块我为两个列表计时这些方法:

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

l1 的结果:

方法 a 最快。 b 慢 30%，c 慢 30%。

l2 的结果:

方法 a 和 b 几乎相同(仍然快一点)，而 c 比两者都快一点(我们预期)。

出于实用目的，我会说第一个版本比第二个版本好，但如果您有很多重复键，3d 版本会是最好的。归根结底，理论很好，但实际上最好的方法是依赖于列表。