На этом шаге мы рассмотрим использование функции heapq.merge().

Задача

    У вас есть коллекция отсортированных последовательностей, и вы хотите проитерировать по отсортированной последовательности этих последовательностей, слитых воедино.

Решение

    Функция heapq.merge() делает именно это:

>>> import heapq
>>> a = [1, 4, 7, 10]
>>> b = [2, 5, 6, 11]
>>> for c in heapq.merge(a, b):
	print(c)

	
1
2
4
5
6
7
10
11
>>> 

Обсуждение

    Итеративная природа heapq.merge() подразумевает, что она никогда не читает ни одну из переданных ей последовательностей сразу до конца. Это значит, что вы можете использовать ее на длинных последовательностях с очень незначительным перерасходом ресурсов. Вот, например, как вы можете слить воедино два отсортированных файла:

import heapq
with open('sorted_file_1', 'rt') as file1, \
    open('sorted_file_2', 'rt') as file2, \
    open('merged_file', 'wt') as outf:

for line in heapq.merge(file1, file2):
    outf.write(line)

    Важно отметить, что heapq.merge() требует, чтобы все передаваемые ей последовательности уже были отсортированы. Она не читает предварительно данные в кучу, не выполняет предварительную сортировку. Также она не выполняет никакой валидации входных данных на соответствие требованиям упорядоченности. Она просто проверяет набор элементов из "голов" каждой переданной последовательности и выдает минимальный из найденных. Далее читается новый элемент из выбранной последовательности, и процесс повторяется до тех пор, пока все входные последовательности не будут полностью потреблены.

    На следующем шаге мы рассмотрим замену бесконечных циклов while итератором.

Предыдущий шаг Содержание Следующий шаг