Powtarzanie wielu sortowanych list w kolejności

Question

Załóżmy, że mam wiele list par (int, str), niekoniecznie tej samej długości. Jedynym ograniczeniem jest to, że listy są sortowane w kolejności rosnącej ich części całkowitych:

a = [(1, 'a'), (4, 'a'), (6, 'b'), (7, 'c'), (12, 'a')] 
b = [(5, 'd'), (10, 'c'), (11,'e')] 
c = [(0, 'b'), (3, 'd')] 

Co chciałbym zrobić, to emitują elementy ciągów w kolejności, w jakiej ich odpowiednie elementy całkowite występują czyli w tym sprawa:

(0, 'b'), (1, 'a'), (3, 'd'), (4, 'a'), ... 

Zastanawiam się, czy istnieje oczywista (miły + pythonic) sposób to zrobić tylko za pomocą iteratorów z a, b i c? Przyjrzałem się itertools, ale nie mogę od razu zobaczyć, jak korzystać z funkcji w tym przypadku. Wykazy a, b, c może być bardzo duży, więc chciałbym to zrobić bez czytania ich w pamięci, a następnie sortowania ...

Answer 1

Ponieważ listy są już posortowane, można użyć heapq.merge:

>>> import heapq 
>>> a = [(1, 'a'), (4, 'a'), (6, 'b'), (7, 'c'), (12, 'a')] 
>>> b = [(5, 'd'), (10, 'c'), (11,'e')] 
>>> c = [(0, 'b'), (3, 'd')] 
>>> for i in heapq.merge(a, b, c): 
...  i 
... 
(0, 'b') 
(1, 'a') 
(3, 'd') 
(4, 'a') 
(5, 'd') 
(6, 'b') 
(7, 'c') 
(10, 'c') 
(11, 'e') 
(12, 'a') 
>>> 

Jest to również bardzo wydajne w przypadku dużych list, ponieważ używa wewnętrznie iteratorów. Od docs link podany powyżej:

podobne do sorted(itertools.chain(*iterables)) ale zwraca iterable, nie pobiera dane do pamięci wszystkie naraz i zakłada, że ​​każdy z strumieni wejściowych jest już posortowana (najmniejszy na największy).

Answer 2

my_iterator = iter(sorted(a+b+c)) 

jest zdecydowanie najbardziej pythonic IMHO (choć prawdopodobnie można po prostu zostawić go w postaci listy i nie owijać dodatkowy iter

można z pewnością ją przyspieszyć, jeśli to był wąskim gardłem (w co wątpię to jest)

Answer 3

heapq.merge to prawdopodobnie najlepszy wybór. FWIW more_itertools oferuje również narzędzie mergesort, podobny do Przyjmujemy odpowiedź:

import operator as op 

import more_itertools 

list(more_itertools.collate(a, b, c, key=op.itemgetter(0))) 

Wyjście

[(0, 'b'), 
(1, 'a'), 
(3, 'd'), 
(4, 'a'), 
(5, 'd'), 
(6, 'b'), 
(7, 'c'), 
(10, 'c'), 
(11, 'e'), 
(12, 'a')] 

Zobacz more_itertools docs aby uzyskać więcej informacji.