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

- Sean Lynch

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 的表现仍然相当不错，因为排序相对于二次方方法来说还是非常便宜的。随着数据增长，可以看到 filter 的二次复杂度表现很差。

- Padraic Cunningham

---

使用 for _,v in groupby 会更好！ - Mazdak

@Kasra，是的。太习惯检查 if k 了！ - Padraic Cunningham

子列表长什么样？ - Stefan Pochmann

是的，我得到了类似的结果，使用defaultdict最快。我也喜欢它的代码最好，所以它是我的获胜者。 - Stefan Pochmann

@StefanPochmann，是的，defaultdict通常更快，我已经添加了答案，在某些情况下它打败了numpy和pandas，唯一的问题是如果顺序很重要，但无论如何最坏的情况下，OP可以使用OrderedDict仍然提供线性解决方案。 - Padraic Cunningham

Answer 2

这是您需要的：

在这里：

>>> lists = [[1, "text", "name1", "text"],
...  [2, "text", "name2", "text"],
...  [3, "text", "name2", "text"],
...  [4, "text", "name1", "text"]]
>>> groupers = set(l[2] for l in lists)
>>> groupers
set(['name2', 'name1'])
>>> l = [filter(lambda x: x[2] == y, lists) for y in groupers]
>>> pprint.pprint(l)
[[[2, 'text', 'name2', 'text'], [3, 'text', 'name2', 'text']],
 [[1, 'text', 'name1', 'text'], [4, 'text', 'name1', 'text']]]

当然，您可以在一行中编写整个分组逻辑：

>>> l = [filter(lambda x: x[2] == y, lists) for y in set(l[2] for l in lists)]
>>> pprint.pprint(l)
[[[2, 'text', 'name2', 'text'], [3, 'text', 'name2', 'text']],
 [[1, 'text', 'name1', 'text'], [4, 'text', 'name1', 'text']]]

- Anshul Goyal

Answer 3

使用sorted函数，以要排序的元素为key参数，并使用itertools.groupby函数对它们进行分组：

>>> from itertools import groupby
>>> sl = sorted(your_list, key=lambda your_list: your_list[2])
>>> [list(v) for k,v in groupby(sl, key=lambda sl:sl[2])]
[[[1, 'text', 'name1', 'text'], 
  [4, 'text', 'name1', 'text']], 
 [[2, 'text', 'name2', 'text'], 
  [3, 'text', 'name2', 'text']]]

- Shan Valleru

---

是的，这样就排好序了。那分组呢？ - Sean Lynch

没有注意到分组，可以使用itertools库中的groupby函数；已更新解决方案。 - Shan Valleru

Answer 4

以下函数将通过指定索引的键快速地（无需排序）将任意长度的子序列分组：

# given a sequence of sequences like [(3,'c',6),(7,'a',2),(88,'c',4),(45,'a',0)],
# returns a dict grouping sequences by idx-th element - with idx=1 we have:
# if merge is True {'c':(3,6,88,4),     'a':(7,2,45,0)}
# if merge is False {'c':((3,6),(88,4)), 'a':((7,2),(45,0))}
def group_by_idx(seqs,idx=0,merge=True):
    d = dict()
    for seq in seqs:
        if isinstance(seq,tuple): seq_kind = tuple
        if isinstance(seq,list): seq_kind = list
        k = seq[idx]
        v = d.get(k,seq_kind()) + (seq[:idx]+seq[idx+1:] if merge else seq_kind((seq[:idx]+seq[idx+1:],)))
        d.update({k:v})
    return d

在你的问题中，关键是具有索引2的元素，因此。

group_by_idx(your_list,2,False)

提供

{'name1': [[1, 'text', 'text'], [4, 'text', 'text']],
 'name2': [[2, 'text', 'text'], [3, 'text', 'text']]}

这不完全是您要求的输出，但可能也能满足您的需求。

- mmj

Answer 5

最简单的方法是使用sorted()函数的key参数。在您的示例中：

>>> a = [[1, "text", "name1", "text"], [2, "text", "name2", "text"], [3, "text", "name2", "text"], [4, "text", "name1", "text"]]

>>> sorted(a[:], key=lambda item:item[2])

>>> [[1, 'text', 'name1', 'text'], [4, 'text', 'name1', 'text'], [2, 'text', 'name2', 'text'], [3, 'text', 'name2', 'text']]

您可以在this link找到更多关于此参数的信息。

- tomasyany

---

分组在哪里？ - Stefan Pochmann

是的，但那只是排序。我认为接下来需要使用groupby()函数。 - Sean Lynch