Как разделить список на 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]

Если к = 2, то два подсписки с приблизительно равной ответа являются А и В:

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 

Единственное, что пришло на мой взгляд, было как-то использовать сортировку. Но, возможно, есть какой-то питонический способ сделать это. Поскольку список L может быть очень длинным, скажем, 10000, я ожидаю, что это будет эффективный способ.

Answer 1

Метод, который вы объяснили, на самом деле является одним из самых питонических/эффективных. Сортировка списка по значению ответа, а затем разделить отсортированный список в подсписков, получая каждый 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]] 

Answer 2

Я не очень понимаю, что ОП хочет но я могу показать сортировку списка списков со 100 000 элементов (т. е. 100 000 подписок) занимает медленную машину 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