Python. Cортировать в конце или держать отсортированным?

На днях я предложил подписчикам канала Oh My Py такую задачку:

Допустим, вы пишете программу, которой на вход последовательно, одно за другим, приходят числа. Ваша задача — накапливать их как-то, а потом, когда числа перестанут приходить — вернуть отсортированный список.

Как думаете, что будет работать быстрее:

  • Складывать приходящие числа в неупорядоченную кучу, отсортировать в конце.
  • Постоянно поддерживать отсортированный список (с помощью bisect), в конце просто вернуть его.

Вот результаты голосования:

Результаты голосования
Большинство решило, что быстрее постоянно поддерживать список отсортированным.

Давайте разберёмся, так ли это.

Решение

Сразу оговорюсь, что оценивать будем именно чистое время выполнения нашего обработчика. Понятно, что если источник будет присылать по одному числу в минуту, то общее время выполнения будет определяться именно скоростью источника, а не нашим обработчиком — вне зависимости от выбранного алгоритма. Поэтому исходим из того, что источник фигачит числами как из пулемёта.

Мы знаем, что сортировка на n числах занимает O(n logn) операций. Это сложность варианта «сортировать в конце».

Мы также знаем, что один бинарный поиск занимает O(log n) операций. В варианте «поддерживать отсортированным» мы выполняем поиск n раз, значит итоговая сложность O(n logn).

Там O(n logn) и тут O(n logn) — значит, варианты равнозначные, расходимся.

На самом деле нет ツ Посмотрите на реализацию варианта «поддерживать отсортированным»:

def keep_sorted(generator):
    collection = []
    for number in generator:
        index = bisect.bisect(collection, number)
        collection.insert(index, number)
    return collection

Да, бинарный поиск выполняется за логарифмическое время. Но после него идёт вставка в массив — она занимает линейное время.

Таким образом, на каждое число алгоритм тратит O(n) операций, а на n чисел — O(n²). Это сильно медленнее, чем O(n logn).

Проверка

Чтобы не быть голословным, я реализовал оба варианта и сравнил их в действии.

Подготовка

Сначала подготовим генератор чисел:

import random

# будем генерить числа от 1 до 1 млн
RANGE_SIZE = 1 * 10**6

def number_generator(count):
    for _ in range(count):
        number = random.randint(1, RANGE_SIZE)
        yield number

Затем реализуем алгоритм «сортировать в конце»:

from collections import deque

def sort_after(generator):
    collection = deque()
    for number in generator:
        collection.append(number)
    return sorted(collection)

И алгоритм «поддерживать отсортированным»:

import bisect

def keep_sorted(generator):
    collection = []
    for number in generator:
        bisect.insort(collection, number)
    return collection

Синхронная работа

Сначала рассмотрим вариант, когда генератор и обработчик работают строго последовательно: генератор присылает число, обработчик складывает его к себе, генератор присылает второе число, обработчик снова складывает, и так далее. Пока обработчик не закончил с числом, генератор не может прислать следующее.

Будем проверять на 1 млн чисел.

count = 1 * 10**6

Сортировать в конце:

%%time
sort_after(number_generator(count))
;
CPU times: user 1.33 s, sys: 20.1 ms, total: 1.35 s
Wall time: 1.35 s

Держать отсортированным:

%%time
keep_sorted(number_generator(count))
;
CPU times: user 1min 25s, sys: 74.9 ms, total: 1min 25s
Wall time: 1min 25s

Вариант «сортировать в конце» оказался быстрее в 63 раза (1.35 секунды против 85 секунд).

Асинхронная работа

Теперь пусть генератор и обработчик работают независимо. Генератор присылает числа с некоторым интервалом, а обработчик независимо складывает их к себе. Генератор не дожидается, пока обработчик закончит с очередным числом — он может прислать новое в любой момент.

Здесь придётся работать в два процесса (отдельно генератор, отдельно обработчик), так что будем использовать очередь для синхронизации. Генератор будет складывать в неё числа, а обработчик — забирать.

Кроме того, добавим генератору задержку:

import random
import time

def number_generator(queue, count, delay):
    for _ in range(count):
        number = random.randint(1, RANGE_SIZE)
        queue.put(number)
        time.sleep(delay)
    queue.put(None)

Алгоритмы «сортировать в конце» и «поддерживать отсортированным» не слишком поменяются. Просто теперь они получают числа не из генератора, а из очереди:

from collections import deque

def sort_after(queue):
    collection = deque()
    while True:
        number = queue.get()
        if number is None:
            break
        collection.append(number)
    return sorted(collection)
import bisect

def keep_sorted(queue):
    collection = []
    while True:
        number = queue.get()
        if number is None:
            break
        bisect.insort(collection, number)
    return collection

Добавим вспомогательную функцию, которая создаёт процессы и запускает тест:

from multiprocessing import Process, Queue

def main(processor, count, delay):
    print(f"count = {count}, delay = {delay}")
    queue = Queue()
    generator = Process(
        target=number_generator,
        args=(queue, count, delay),
        daemon=True,
    )
    consumer = Process(target=processor, args=(queue,), daemon=True)
    
    generator.start()
    consumer.start()
    generator.join()
    consumer.join()

Будем проверять на 1 млн чисел и интервале между приходом чисел в 1 микросекунду:

count = 1 * 10**6
delay = 1 * 10**(-6)
%%time
main(sort_after, count, delay)
;
count = 1000000, delay = 1e-06
CPU times: user 3.12 ms, sys: 5.48 ms, total: 8.6 ms
Wall time: 29.3 s
%%time
main(keep_sorted, count, delay)
;
count = 1000000, delay = 1e-06
CPU times: user 3.81 ms, sys: 6.43 ms, total: 10.2 ms
Wall time: 1min 43s

Кажется, что разрыв сократился (29 секунд против 103). Но на самом деле эти 29 секунд уходят не на полезную работу, а на «обвязку» — возню вокруг time.sleep() и межпроцессное взаимодействие. Чтобы убедиться в этом, сделаем ещё один алгоритм, который вообще не сортирует приходящие числа, а просто возвращает их в финале как есть:

def do_not_sort(queue):
    collection = deque()
    while True:
        number = queue.get()
        if number is None:
            break
        collection.append(number)
    return collection
%%time
main(do_not_sort, count, delay)
;
count = 1000000, delay = 1e-06
CPU times: user 2.93 ms, sys: 5.58 ms, total: 8.52 ms
Wall time: 29.1 s

Таким образом, «чистое» время работы «сортировать в конце» по-прежнему составляет около 1 секунды, а «держать отсортированным» — в десятки раз больше.

Ноутбук

⌘ ⌘ ⌘

Итого: чистая победа «сортировать в конце» над «держать отсортированным» с большим отрывом.

Специально для подписчиков «Oh My Py»