效率:2D列表到python中的字典

Question

我有一个2D列表.

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

Answer 1

你有两个解决方案没有错,它们很好而且效率很高:

1. 解决方案1迭代列表一次,但执行两次字典查找.既然这是O(1),你有2,我会说这是2xN.
2. 解决方案2迭代列表两次,每次一次查找 - 再次2xN.

从理论的角度来看,这些是相同的.运行时我会打赌他们也非常接近.更可靠的方式(请求宽恕而不是许可,感谢@tobias_k)可以改进第一个解决方案:

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

如果你有许多重复键,这会更好,因为异常的开销会比所有ifs(并且只有一个查找)小得多,所以这将取决于所讨论的实际列表.如果您使用此解决方案,您可能需要阅读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最快.比较慢30%b,另外30%c.

结果l2:

方法a和b几乎相同(仍然快一点),并且c比两者(我们预期的)快一点.

我会说实际上第一个版本比第二个版本更好,但如果你有很多重复键,那么3d会是最好的.最重要的是,理论一切都很好,但实际上最好的方法依赖于列表.

Answer 2

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

它会给你输出为 {100: 1, 43: 2, 201: 1, 5: 7}