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

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

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

[[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)）。但我认为有更好的方法。

您可以排序并使用 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))])

或者使用有序字典按第三个元素分组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']]]

如果顺序不重要，您可以使用默认字典代替 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 仍然表现得相当好，因为与二次方法相比，排序仍然相当便宜。正如您所看到的，随着数据的增长，过滤器的二次复杂度表现得很差。