Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sort after or keep sorted?
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Отсортировать в конце или держать отсортированным?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Вы пишете программу, которой на вход последовательно, одно за другим, приходят числа. Ваша задача — накапливать их как-то, а потом, когда числа перестанут приходить — вернуть отсортированный список.\n",
"\n",
"Вопрос — что будет работать быстрее:\n",
"\n",
"- Складывать приходящие числа в неупорядоченную кучу, отсортировать в конце.\n",
"- Постоянно поддерживать отсортированный список (с помощью bisect), в конце просто вернуть его.\n",
"\n",
"Давайте проверим!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Подготовка"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Сначала подготовим генератор чисел:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"\n",
"# будем генерить числа от 1 до 1 млн\n",
"RANGE_SIZE = 1 * 10**6\n",
"\n",
"def number_generator(count):\n",
" for _ in range(count):\n",
" number = random.randint(1, RANGE_SIZE)\n",
" yield number"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Затем реализуем алгоритм «сортировать в конце»:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"from collections import deque\n",
"\n",
"def sort_after(generator):\n",
" collection = deque()\n",
" for number in generator:\n",
" collection.append(number)\n",
" return sorted(collection)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"И алгоритм «поддерживать отсортированным»:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"import bisect\n",
"\n",
"def keep_sorted(generator):\n",
" collection = []\n",
" for number in generator:\n",
" bisect.insort(collection, number)\n",
" return collection"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Синхронная работа"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Сначала рассмотрим вариант, когда генератор и обработчик работают строго последовательно: генератор присылает число, обработчик складывает его к себе, генератор присылает второе число, обработчик снова складывает, и так далее. Пока обработчик не закончил с числом, генератор не может прислать следующее."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Будем проверять на 1 млн чисел."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"count = 1 * 10**6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Сортировать в конце:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 1.33 s, sys: 20.1 ms, total: 1.35 s\n",
"Wall time: 1.35 s\n"
]
}
],
"source": [
"%%time\n",
"sort_after(number_generator(count))\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Держать отсортированным:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 1min 25s, sys: 74.9 ms, total: 1min 25s\n",
"Wall time: 1min 25s\n"
]
}
],
"source": [
"%%time\n",
"keep_sorted(number_generator(count))\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Результат**\n",
"\n",
"Вариант «сортировать в конце» оказался быстрее в 63 раза (1.35 секунды против 85 секунд)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Асинхронная работа"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Теперь пусть генератор и обработчик работают независимо. Генератор присылает числа с некоторым интервалом, а обработчик независимо складывает их к себе. Генератор не дожидается, пока обработчик закончит с очередным числом — он может прислать новое в любой момент.\n",
"\n",
"Здесь придётся работать в два процесса (отдельно генератор, отдельно обработчик), так что будем использовать очередь для синхронизации. Генератор будет складывать в неё числа, а обработчик — забирать."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Кроме того, добавим генератору задержку:"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import time\n",
"\n",
"def number_generator(queue, count, delay):\n",
" for _ in range(count):\n",
" number = random.randint(1, RANGE_SIZE)\n",
" queue.put(number)\n",
" time.sleep(delay)\n",
" queue.put(None)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Алгоритмы «сортировать в конце» и «поддерживать отсортированным» не слишком поменяются. Просто теперь они получают числа не из генератора, а из очереди:"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [],
"source": [
"from collections import deque\n",
"\n",
"def sort_after(queue):\n",
" collection = deque()\n",
" while True:\n",
" number = queue.get()\n",
" if number is None:\n",
" break\n",
" collection.append(number)\n",
" return sorted(collection)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [],
"source": [
"import bisect\n",
"\n",
"def keep_sorted(queue):\n",
" collection = []\n",
" while True:\n",
" number = queue.get()\n",
" if number is None:\n",
" break\n",
" bisect.insort(collection, number)\n",
" return collection"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Добавим вспомогательную функцию, которая создаёт процессы и запускает тест:"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [],
"source": [
"from multiprocessing import Process, Queue\n",
"\n",
"def main(processor, count, delay):\n",
" print(f\"count = {count}, delay = {delay}\")\n",
" queue = Queue()\n",
" generator = Process(target=number_generator, args=(queue, count, delay), daemon=True)\n",
" consumer = Process(target=processor, args=(queue,), daemon=True)\n",
" \n",
" generator.start()\n",
" consumer.start()\n",
" generator.join()\n",
" consumer.join()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Будем проверять на 1 млн чисел и интервалом между приходом чисел в 1 микросекунду:"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [],
"source": [
"count = 1 * 10**6\n",
"delay = 1 * 10**(-6)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"count = 1000000, delay = 1e-06\n",
"CPU times: user 3.12 ms, sys: 5.48 ms, total: 8.6 ms\n",
"Wall time: 29.3 s\n"
]
}
],
"source": [
"%%time\n",
"main(sort_after, count, delay)\n",
";"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"count = 1000000, delay = 1e-06\n",
"CPU times: user 3.81 ms, sys: 6.43 ms, total: 10.2 ms\n",
"Wall time: 1min 43s\n"
]
}
],
"source": [
"%%time\n",
"main(keep_sorted, count, delay)\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Кажется, что разрыв сократился (29 секунд против 103). Но на самом деле эти 29 секунд уходят не на полезную работу, а на «обвязку» — возню вокруг time.sleep() и межпроцессное взаимодействие. Чтобы убедиться в этом, сделаем ещё один алгоритм, который вообще не сортирует приходящие числа, а просто возвращает их в финале как есть:"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [],
"source": [
"def do_not_sort(queue):\n",
" collection = deque()\n",
" while True:\n",
" number = queue.get()\n",
" if number is None:\n",
" break\n",
" collection.append(number)\n",
" return collection"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"count = 1000000, delay = 1e-06\n",
"CPU times: user 2.93 ms, sys: 5.58 ms, total: 8.52 ms\n",
"Wall time: 29.1 s\n"
]
}
],
"source": [
"%%time\n",
"main(do_not_sort, count, delay)\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Таким образом, «чистое» время работы «сортировать в конце» по-прежнему составляет около 1 секунды, а «держать отсортированным» — в десятки раз больше."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Вывод\n",
"\n",
"Чистая победа «сортировать в конце» над «держать отсортированным» с большим отрывом.\n",
"\n",
"*Специально для подписчиков [Oh My Py](http://ohmypy.ru)*"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment