Iterieren durch mehrere sortierte Listen in der Reihenfolge

Question

Angenommen, ich habe eine Anzahl von Listen von Paaren (int, str), nicht unbedingt von der gleichen Länge. Die einzige Einschränkung dabei ist, dass die Listen in aufsteigender Reihenfolge nach ihren ganzzahligen Teilen sortiert werden:

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

Was würde ich tun möchte, ist die Textelemente in der Reihenfolge zu emittieren, in denen ihre entsprechenden ganzzahligen Elemente in dieser dh auftreten Fall:

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

ich frage mich, ob es eine offensichtliche (schön + pythonic) Art und Weise ist dies nur mit Iteratoren von a, b und c zu tun? Ich habe mir itertools angesehen, kann aber nicht sofort sehen, wie man die Funktionalität in diesem Fall benutzt. Die Listen a, b könnte c sehr groß sein, so würde ich dies, ohne sie in den Speicher einzulesen zu tun und dann Sortierung ...

Answer 1

da die Listen bereits sortiert sind, können Sie 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') 
>>> 

Dies ist auch sehr effizient mit großen Listen, da es interne Iteratoren verwendet. Aus dem docs Link oben gegeben:

ähnlich sorted(itertools.chain(*iterables)) gibt aber ein iterable, hat die Daten nicht in dem Speicher ziehen auf einmal und geht davon aus, dass jeder der Eingabe bereits sortierte Ströme ist (kleinste zu größte).

Answer 2

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

ist bei weitem die meisten pythonic imho (obwohl Sie wahrscheinlich nur lassen Sie es als Liste und nicht wickeln Sie das zusätzliche iter

Sie sicher es bis beschleunigen könnte, wenn dies zu einem Engpass war (was ich bezweifle es ist)

Answer 3

heapq.merge ist wahrscheinlich die beste Wahl. FWIW more_itertools bietet auch ein mergesort Werkzeug, ähnlich wie die akzeptierte Antwort:

import operator as op 

import more_itertools 

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

Ausgabe

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

more_itertools docs für weitere Informationen.