Lặp lại qua nhiều danh sách được sắp xếp theo thứ tự

Question

Giả sử tôi có một số danh sách các cặp (int, str), không nhất thiết phải có cùng độ dài. Ràng buộc duy nhất ở đây là danh sách đều được sắp xếp theo thứ tự tăng dần theo phần nguyên của họ:

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

Những gì tôi muốn làm là để phát ra các yếu tố chuỗi theo thứ tự, trong đó yếu tố số nguyên tương ứng của họ xảy ra tức là trong này trường hợp:

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

tôi tự hỏi nếu có một rõ ràng (đẹp + pythonic) cách để làm điều này chỉ sử dụng vòng lặp của a, b và c? Tôi đã xem itertools nhưng không thể thấy ngay cách sử dụng chức năng trong trường hợp này. Các danh sách a, b, c có thể là rất lớn vì vậy tôi muốn làm điều này mà không cần đọc chúng vào bộ nhớ và sau đó sắp xếp ...

Answer 1

Kể từ khi danh sách đã được sắp xếp, bạn có thể sử dụng 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') 
>>> 

Điều này cũng rất hiệu quả với các danh sách lớn vì nó sử dụng trình vòng lặp nội bộ. Từ các tài liệu liên kết đưa ra ở trên:

Tương tự như sorted(itertools.chain(*iterables)) nhưng trả về một iterable, không kéo dữ liệu vào bộ nhớ cùng một lúc và giả định rằng mỗi người trong số các đầu vào suối đã được sắp xếp (nhỏ nhất đến lớn nhất).

Answer 2

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

đến nay là IMHO pythonic nhất (mặc dù bạn có thể có lẽ chỉ rời khỏi nó như là một danh sách và không quấn thêm iter

bạn chắc chắn có thể tăng tốc độ nó lên nếu điều này là một nút cổ chai (mà tôi nghi ngờ nó là)

Answer 3

heapq.merge có thể là lựa chọn tốt nhất. FWIW more_itertools cũng cung cấp một công cụ mergesort, tương tự như câu trả lời chấp nhận được chấp nhận:

import operator as op 

import more_itertools 

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

Output

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

Xem more_itertools docs để biết thêm thông tin.