如何将列表划分为k个值大致相同的子列表？

Question

我想把一个列表分成 k 个子列表，每个子列表的最后一个元素（也就是响应值）大致相同。

我有这样的列表：

L = [[1,2,3,2], [4,5,2,2], [2,3,9,1], [5,7,2,1], [2,3,3,1]]

这里，响应值就是每个子列表的最后一个元素。响应值的范围在 [1,2] 之间。

如果 k = 2，那么大致相等的两个子列表是 A 和 B：

A = [[1,2,3,2], [2,3,3,1]                 # it has response values 1,2
B = [[2,3,9,1], [4,5,2,2], [5,7,2,1]]     # it has response values 1,2,1

我想到的唯一办法就是用排序。但可能还有其他更“pythonic”的方法。因为列表 L 可能很长，比如有 10000 个元素，所以我希望能找到一种高效的方法来实现这个。

Answer 1

我不太明白提问者想要什么，但我可以告诉你，排序一个包含10万个元素的列表（也就是10万个子列表）在一台比较慢的Atom电脑上只需要230毫秒。我希望提问者觉得这个速度“够快”了。

>>> x = [ [ random.randrange(100) for _ in xrange(random.randrange(1, 1000)) ] for _ in xrange(10**5) ]

>>> import time
>>> a=time.time(); x.sort(key=lambda sl: sl[-1]); b=time.time()
>>> 1e3*(b-a)
226.77206993103027

$ python -V
Python 2.7.8
$ head -10 /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 28
model name      : Intel(R) Atom(TM) CPU D510   @ 1.66GHz
stepping        : 10
microcode       : 0x107
cpu MHz         : 1662.623
cache size      : 512 KB
physical id     : 0

Answer 2

你提到的方法确实是最符合Python风格和高效的做法。首先根据响应值对列表进行排序，然后通过获取每个k个元素来将排序后的列表分成多个子列表：

def divideintokapprox(mylist, k):
    sortedlist = sorted(mylist, key=lambda x: -x[-1])
    return [sortedlist[i::k] for i in range(k)]

使用示例：

L = [[1,2,3,2], [4,5,2,2], [2,3,9,1], [5,7,2,1], [2,3,3,1]]

sublists = divideintokapprox(L, 2)
print(sublists[0])
#[[1, 2, 3, 2], [2, 3, 9, 1], [2, 3, 3, 1]]
print(sublists[1])
#[[4, 5, 2, 2], [5, 7, 2, 1]]