Python - 按索引对列表列表中的重复项进行分组

Question

我见过很多关于从列表中删除重复项并计算它们的问题。但我正在尝试找到对它们进行分组的最佳方法 - 用于列表列表。

鉴于此示例，我想按第三个字段进行分组:

[[1, "text", "name1", "text"],
 [2, "text", "name2", "text"],
 [3, "text", "name2", "text"],
 [4, "text", "name1", "text"]]

我想得到这个:

[[[1, "text", "name1", "text"],
  [4, "text", "name1", "text"]],
 [[2, "text", "name2", "text"],
  [3, "text", "name2", "text"]]]

我可以通过循环并只跟踪找到的内容来想到天真的方法 (O(n^2))。但我认为有更好的方法。

Answer 1

您可以排序并使用 groupby 但那是 O(n log n):

from operator import itemgetter
from itertools import groupby

print([list(v) for _,v in groupby( sorted(l,key=itemgetter(2)),itemgetter(2))])

或者使用 OrderedDict通过使用第三个元素作为键并将子列表附加为值，按第三个元素对 O(n) 解决方案进行分组。 setdefault 将处理重复的键:

from collections import OrderedDict

od = OrderedDict()

for sub in l:
    od.setdefault(sub[2],[]).append(sub)
from pprint import pprint as pp
pp(od.values())
[[[1, 'text', 'name1', 'text'], [4, 'text', 'name1', 'text']],
[[2, 'text', 'name2', 'text'], [3, 'text', 'name2', 'text']]]

如果顺序无关紧要，您可以使用 defaultdict代替 OrderedDict。

如果顺序无关紧要，defaultdict 是迄今为止最有效的。

In [7]: from itertools import groupby

In [8]: from collections import OrderedDict, defaultdict                               

In [9]: l = [[1, "text", "name{}".format(choice(list(range(2000)))), "text"] for _ in xrange(40000)]

In [13]: from operator import  itemgetter

In [14]: timeit [list(v) for _,v in groupby( sorted(l,key=itemgetter(2)),itemgetter(2))]
10 loops, best of 3: 42.5 ms per loop

In [15]: %%timeit                                                                       
od = defaultdict(list)
for sub in l:
    od[sub[2]].append(sub)
   ....: 
100 loops, best of 3: 9.42 ms per loop

In [16]: %%timeit                                                                       
od = OrderedDict()
for sub in l:
     od.setdefault(sub[2],[]).append(sub)
   ....: 
10 loops, best of 3: 25.5 ms per loop

In [17]: lists = l

In [18]: %%timeit
   ....: groupers = set(l[2] for l in lists)
   ....: [filter(lambda x: x[2] == y, lists) for y in groupers]
   ....: 

1 loops, best of 3: 8.48 s per loop

In [19]: timeit l = [filter(lambda x: x[2] == y, lists) for y in   set(l[2] for l in lists)]
1 loops, best of 3: 8.29 s per loop

因此，如果顺序无关紧要，则 defaultdict 获胜，groupby 仍然表现得很好，因为与二次方法相比，排序仍然非常便宜。正如您所见，随着数据的增长，过滤器的二次复杂度表现不佳。