根据共同的第一项将子列表排序为新的子列表。

Question

我有大量的双成员子列表，这些子列表的成员是一个叫做 mylist:

mylist = [['AB001', 22100],
          ['AB001', 32935],
          ['XC013', 99834],
          ['VD126', 18884],
          ['AB001', 34439],
          ['XC013', 86701]]

我想排序 mylist 到新的子列表中，根据子列表是否包含与第一个项目相同的字符串。例如，这就是我希望我的代码输出的结果。

newlist = [['AB001', 22100], ['AB001', 32935], ['AB001', 34439]],
          [['XC013', 99834], ['XC013', 86701]],
          [['VD126', 18884]]

这就是我的代码。

mylist = sorted(mylist)
newlist = []
for sublist in mylist:
    id = sublist[0]
if id == next.id:
    newlist.append(id)
print newlist

我也想知道如果 itertools.groupby() 是解决这个问题的正确工具。谁能帮我解决这个问题？

Answer 1

你说的没错，这是为 groupby:

from itertools import groupby
from operator import itemgetter

mylist = [['AB001', 22100],
          ['AB001', 32935],
          ['XC013', 99834],
          ['VD126', 18884],
          ['AB001', 4439],
          ['XC013', 86701]]

print([list(value) for key, value in groupby(sorted(mylist), key=itemgetter(0))])

这将给你一个列表的列表，按子列表中的第一个项目分组。

[[['AB001', 4439], ['AB001', 22100], ['AB001', 32935]], 
 [['VD126', 18884]], 
 [['XC013', 86701], ['XC013', 99834]]]

Answer 2

collections.defaultdict

一个 itertools.groupby 解决方案将导致O(n 原木 n)的成本，因为输入必须进行排序 第一. 你可以使用 defaultdict 的列表，以保证O(n)的解决方案。

from collections import defaultdict

dd = defaultdict(list)
for item in mylist:
    dd[item[0]].append(item)

res = list(dd.values())

print(res)

[[['AB001', 22100], ['AB001', 32935], ['AB001', 34439]],
 [['XC013', 99834], ['XC013', 86701]],
 [['VD126', 18884]]]

Answer 3

解决这个问题的方法有很多。

def regroup_by_di(items, key=None):
    result = {}
    callable_key = callable(key)
    for item in items:
        key_value = key(item) if callable_key else item
        if key_value not in result:
            result[key_value] = []
        result[key_value].append(item)
    return result

import collections


def regroup_by_dd(items, key=None):
    result = collections.defaultdict(list)
    callable_key = callable(key)
    for item in items:
        result[key(item) if callable_key else item].append(item)
    return dict(result)  # to be in line with other solutions

def regroup_by_sd(items, key=None):
    result = {}
    callable_key = callable(key)
    for item in items:
        key_value = key(item) if callable_key else item
        result.setdefault(key_value, []).append(item)
    return result

import itertools


def regroup_by_it(items, key=None):
    seq = sorted(items, key=key)
    result = {
        key_value: list(group)
        for key_value, group in itertools.groupby(seq, key)}
    return result

def group_by(
        seq,
        key=None):
    items = iter(seq)
    try:
        item = next(items)
    except StopIteration:
        return
    else:
        callable_key = callable(key)
        last = key(item) if callable_key else item
        i = j = 0
        for i, item in enumerate(items, 1):
            current = key(item) if callable_key else item
            if last != current:
                yield last, seq[j:i]
                last = current
                j = i
        if i >= j:
            yield last, seq[j:i + 1]


def regroup_by_gb(items, key=None):
    return dict(group_by(sorted(items, key=key), key))

可以分为两类:

1. 循环通过输入创建一个 dict-样的结构(regroup_by_di(), regroup_by_dd(), regroup_by_sd())
2. 对输入进行排序，然后用 uniq-类函数（如 itertools.groupby()) (regroup_by_it(), regroup_by_gb())

第一类方法有 O(n) 而第二类方法的计算复杂度则为："在计算过程中，我们会发现，这些方法的计算复杂度很高。O(n log n).

所有拟议的方法都需要指定一个 key.对于OP的问题。operators.itemgetter(0) 或 lambda x: x[0] 就可以了。此外，要想得到OP想要的结果，应该只得到 list(dict.values())，例如：。

from operator import itemgetter


mylist = [['AB001', 22100],
          ['AB001', 32935],
          ['XC013', 99834],
          ['VD126', 18884],
          ['AB001', 4439],
          ['XC013', 86701]]


print(list(regroup_by_di(mylist, key=itemgetter(0)).values()))
# [[['AB001', 22100], ['AB001', 32935], ['AB001', 4439]], [['XC013', 99834], ['XC013', 86701]], [['VD126', 18884]]]

---

计时的结果是所有的人都快 dict-基于（一级）的解决方案，所有的解决方案都比较慢。groupby-基于（二级）的解决方案。dict-的解决方案，它们的性能将略微取决于。"碰撞率"对于较高的碰撞率，则会采用以下方法 regroup_by_di() 可能是最快的，而对于较低的碰撞率来说。regroup_by_dd() 可能是最快的。

基准出来的结果如下。

• 0.1%的碰撞率(每组约1000个元素)

• 10%的碰撞率（每组约10个元素

• 50%的碰撞率（每组约2个元素

• 100%的碰撞率（每组约1个元素

(更多详情可查询) 此处.)

Answer 4

不需要导入任何包。

• 构建一个字典，然后把值放到一个列表中。
  • 使用 .get 来确定一个键是否存在，并返回一些指定的值。None 在这种情况下，如果密钥不存在。
  • dict.get 默认为 None，所以这个方法永远不会引发一个 按键错误.
    • 如果 None 是字典中的一个值，那么就改变由 .get.
      • test.get(t[0], 'something here')
• 因为。基于共同的第一项的子清单.
  • 添加指数0为 key，然后加上 list, t作为 dict 价值。

test = dict()
for t in mylist:
    if test.get(t[0]) == None:
        test[t[0]] = [t]
    else:
        test[t[0]].append(t)
        
final = list(test.values())

# print final results in

[[['AB001', 22100], ['AB001', 32935], ['AB001', 34439]],
 [['XC013', 99834], ['XC013', 86701]],
 [['VD126', 18884]]]