Sort after or keep sorted?

sort-after-or-keep-sorted.ipynb

{
 "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
}