高效地对元组列表进行分组

Question

高效地对元组列表进行分组

4

我有一个包含元组的大列表，例如[ (1,2), (1,3), (1,4), (2,1), (2,3) ]等等。我希望高效地将其转换为[ (1, [1,2,3,4]), (2, [1,3] ) ]。我通过每个元组的第一个元素将元组分组，即(1,2), (1,3), (1,4)变为(1, [2,3,4])（请参见下面的Haskell版本）。我怀疑这可以一次完成吗？输入列表始终有序。 在Python中，我尝试使用defaultdict，我认为这是不重复发明轮子的自然解决方案。它工作得很好，但它不保留键的顺序。一种解决方法是使用有序的defaultdict，如此处所述。

无论如何，我想知道这个问题的语言无关和高效的解决方案。我的当前解决方案需要两个通行证和对列表的set()的一次调用。更新我正在考虑实现以下Haskell版本：

a = [ (1,2), (1,3), (1,4), (2,1), (2,3) ] 
b = groupBy (\ x y -> fst x == fst y ) 
b 
[[(1,2),(1,3),(1,4)],[(2,1),(2,3)]]  
map (\x -> (fst .head $ x, map snd x ) ) b 
[(1,[2,3,4]),(2,[1,3])]

答案的性能

我实现了两个答案（coldspeed和pm2ring）。在适中大小的列表上（最多10^4个元素），PM2 ring解决方案更快；在10^5大小时，两者时间相同，在更大的列表上COLDSPEED开始获胜。以下是数字（使用python3）。

第一列是列表中的条目数，第二列是 coldspeed 所花费的时间，第三列是pm2 ring解决方案所花费的时间。所有时间单位均为秒。

10 0.0001 0.0000
100 0.0001 0.0000
1000 0.0005 0.0001
10000 0.0044 0.0014
100000 0.0517 0.0452
1000000 0.5579 1.5249

脚本在这里 http://github.com/dilawar/playground/raw/master/Python/so_group_tuple.py

使用Ashwini优化

PM 2Ring的解决方案在Ashwini的建议下速度更快（大约快3倍-5倍）。

10 4.887580871582031e-05 1.2636184692382812e-05
100 0.00010132789611816406 2.0742416381835938e-05
1000 0.0005109310150146484 0.000110626220703125
10000 0.004467487335205078 0.0009067058563232422
100000 0.05056118965148926 0.017516136169433594
1000000 0.6100358963012695 0.26450490951538086
10000000 6.092756509780884 2.8253660202026367

使用PYPY

结果有些参差不齐。最后一列是第二列和第三列的比率。

pypy so_group_tuple.py 
(10, [1.6927719116210938e-05, 3.409385681152344e-05], 0.4965034965034965)
(100, [4.601478576660156e-05, 8.296966552734375e-05], 0.5545977011494253)
(1000, [0.010258913040161133, 0.0019040107727050781], 5.388054094665665)
(10000, [0.0002448558807373047, 0.00021600723266601562], 1.1335540838852096)
(100000, [0.002658843994140625, 0.0018231868743896484], 1.45834967961292)
(1000000, [0.0833890438079834, 0.02979302406311035], 2.7989452709245284)
(10000000, [1.0556740760803223, 0.6789278984069824], 1.5549133841124023)

我选择使用PM 2Ring的解决方案，因为它在列表大小达到10^5时速度更快。

- Dilawar

2

请提供您当前的解决方案，并澄清问题所在——我不清楚您是如何从第一个列表转换到第二个列表的。 - perigon

OrderedDict? - 101

输入列表总是那样排序的吗？顺便说一句，你在那个列表中有一个错别字。 - PM 2Ring

你期望的输出实际上是 [ (1, [2,3,4]), (2, [1,3] ) ] 吗？我不知道第一个元组中列表中的 1 是从哪里来的。 - Paco H.

1

感谢添加时间信息。你应该看一看 timeit，它比使用 time 模块手动计时更准确（且更方便）。 - PM 2Ring

现在字典保持插入顺序，那么 defaultdict 现在可以在这里使用吗？ - PaulMcG

3个回答

8

您可以使用 collections.OrderedDict（先导入import collections）：

o = collections.OrderedDict()

for x in t:
    o.setdefault(x[0], []).append(x[1])

现在，将o.items()转换为一个列表：

list(o.items())
# [(1, [2, 3, 4]), (2, [1, 3])]

- cs95

尽管这段代码很容易阅读，但在列表大小高达10^5-10^6时，它的执行速度比“PM 2Ring”解决方案要稍慢。我已经在问题描述中添加了一些基准测试数据。 - Dilawar

1

@Dilawar 不仅仅要考虑性能。如果你想要速度，就使用 C ;) 你应该选择最简单、最清晰、最易于阅读和理解的方式。可以理解，PM 2Ring 的解决方案可行且看起来不错，但是我真正想知道我的代码在做什么。最终决策取决于你。干杯。 - cs95

1

如果输入列表已经排序，那么不需要使用任何其他排序函数或功能来重新排序列表。下面的代码将自动给出您所示的输出。

mylistarr = ((1, 2), (1, 3), (1, 4), (2, 1), (2, 3))
output = dict()
for tuple in mylistarr:
    if tuple[0] not in anotherlist:
        output[tuple[0]] = list()
        output[tuple[0]].append(tuple[0])
    output[tuple[0]].append(tuple[1])
print output

输出： {1: [1, 2, 3, 4], 2: [2, 1, 3]}

- Milind Gokhale

1

anotherlist = dict() 这个命名不好。 - Ashwini Chaudhary

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PM 2Ring · Accepted Answer

你可以使用itertools.groupby来完成此操作，并使用zip重新排列收集到的组中的数据：

from itertools import groupby
from operator import itemgetter

a = [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3)]
b = [(k, list(list(zip(*g))[1])) for k, g in groupby(a, itemgetter(0))]
print(b)

输出

[(1, [2, 3, 4]), (2, [1, 3])]

这个列表推导式有点复杂。下面是一种使用传统的 for 循环的变体，它会打印出中间结果，使得代码更加易于理解。

b = []
for k, g in groupby(a, itemgetter(0)):
    t = list(zip(*g))
    print(t)
    b.append(list(t[1]))

print('Output', b)

输出

[(1, 1, 1), (2, 3, 4)]
[(2, 2), (1, 3)]
Output [[2, 3, 4], [1, 3]]

如评论中的Ashwini Chaudhary所提到的，将另一个列表内推导式嵌套在其中可以使代码更易读。这样做也可能更有效率，因为它避免了一些调用。

b = [(k, [x for _, x in g]) for k, g in groupby(a, itemgetter(0))]