{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Содержание\n", "\n", "1. [План на сегодня](#agenda)\n", "2. [Еще раз о сложности](#complexity)\n", " 1. [Нотация](#notation)\n", " 2. [Минимально возможная сложность сортировки сравнением](#minimal_complexity)\n", " 3. [Анализ MergeSort](#mergesort_analysis)\n", "3. [Внешняя сортировка](#external_sort)\n", " 1. [External memory](#external_memory)\n", " 2. [Описание алгоритма внешней сортировки](#description)\n", " 3. [K-way merge](#k_way_merge)\n", "4. [Алгоритм поиска медианы](#element)\n", " 1. [Краткое описание](#radix_sort_description)\n", " 2. [Историческая справка](#history)\n", " 3. [Алгоритм Radix Sort](#radix_sort_code)\n", " 4. [Trie-based Radix Sort](#radix_sort_trie)\n", "5. [Домашняя работа](#homework)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# План занятия\n", "\n", "\n", "\n", "Сегодня будут две основные части: \n", "\n", "- Ответы на вопросы, повторение пройденного: минимальная сложность сортировки сравнениями\n", "- Новые материалы: внешняя сортировка, поиск заданного по порядку элемента\n", " \n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Еще раз о сложности\n", "\n", "\n", "## Нотация\n", "\n", "\n", "\n", " \n", "**$O, \\Theta, \\Omega$ - нотация**\n", " \n", "**$O$ - нотация** \n", "Обычно в оценке сложности алгоритмов ограничиваются именно ей, так как $O(g(n))$ показывает, что функция $f(n)$, описывающая скорость роста алгоритма, растет _не быстрее_, чем заданная $g(n)$.\n", "\n", "Отсюда \"раcтут\" линейный, квадратичный, $n \\cdot log\\ n$ и другие порядки роста\n", "\n", "Математическая формулировка: существют такие $C_1$ и $n_0$, что $0 \\leq |f(n)| \\leq C_1 \\cdot |g(n)| $ для всех $ n > n_0 $\n", "\n", "\n", "\n", "**$\\Theta$ - нотация** \n", "Это запись для ограничения роста функции сверху и снизу:\n", "\n", "Существют такие константы $C_1$, $C_2$ и $n_0$, что $ 0 \\leq C_1 \\cdot |g(n)| \\leq |f(n)| \\leq C_2 \\cdot |g(n)| $ для всех $ n > n_0 $\n", "\n", "\n", "\n", "\n", "**$\\Omega$ - нотация** \n", "Ограничение скорости роста \"снизу\" (наверное, наиболее редкий вариант), может быть полезно при оценке адаптивных алгоритмов:\n", "\n", "\n", "Есть такие константы $с$ и $n_0$, что $ 0 \\leq с \\cdot |g(n)| \\leq |f(n)| $ для всех $ n > n_0 $\n", "\n", "\n", " \n", "\n", "Итак, $O$ - это ограничение сверху, $\\Theta$ - тот же порядок роста, $\\Omega$ - ограничение снизу.\n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Минимально возможная сложность сортировки сравнением\n", "\n", "\n", "\n", " \n", "**Дерево решений** \n", "\n", "Имеется в виду не решающее дерево - алгоритм машинного обучения, но очень похожая структура.\n", "\n", "Дерево является бинарным (т.е. из каждого узла выходят по две ветви). В узлах находятся проверки - сравнение двух элементов массива по определенным индексам.\n", "\n", "При прохождении узла два элемента сравниваются, скажем, на то, какой из них больше. В зависимости от резултьтата проверки выбирается следующий узел.\n", "\n", "\n", "\n", "Для массива размером $n$ существует $n!$ перестановок. На исслюстрации изображены $3!$ перестановки для массива длиной 3 и пути, ведущие к ним: сравнение разных пар элементов массива.\n", "\n", "Дойдя до листа, мы получаем информацию о _порядке_ всех элементов, что необходимо для упорядочивания массива.\n", "\n", "Поскольку алгоритм должен корректно обрабатывать _все_ возможные перестановки, для оценки границы снизу $\\Omega$ нам нужно ориентироваться на максимальную глубину дерева - максимальное количество сравнений.\n", "\n", "$$ n! \\leq 2^h,$$где $h$ - высота дерева\n", "\n", "При этом, $h \\geq log_2(n!) \\geq \\Omega (n \\cdot log\\ n))$. Доказательство последнего тождества можно посмотреть [здесь](\"http://sites.math.rutgers.edu/~ajl213/CLRS/Ch3.pdf\") (задача 3.2-3) либо попробовать самостоятельно доказать c помощью формулы Стирлинга. \n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Анализ MergeSort\n", "\n", "\n", "\n", "\n", "\n", "\n", "**Как оценить $O()$ для Merge Sort** \n", "\n", "Простой способ:\n", "- посчитать стоимость операций Merge на каждом \"уровне\" дерева\n", "- Посчитать глубину дерева, сложить стоимость Merge для всех уровней\n", "\n", "**Можно применить метод деревьев рекурсии**\n", "\n", "(да, деревья и рекурсия очень часто применяются при анализе алгоритмов)\n", "\n", "- на верхнем уровне выполняется задача, допустим, за $f(n)$\n", "- она разбивается на $k$ подзадач, выполняющихся за $f(n/d)$\n", "- граничное условие выполняется за $T(1)$ - константное время\n", "\n", "\n", "\n", "\n", "> Количество операций, последний уровень - $\\Theta(1) \\cdot n^{log_d\\ k} = \\Theta(n^{log_d\\ k})$\n", "\n", "
\n", "Общее количество операций в дереве описывается рекуррентным соотношением \n", "\n", "$$ T(n) = kT(n/d) + f(n) $$\n", "\n", "Для вычисления сложности методом рекурсии применяются следующие выражения (в Кормене это называется \"Основная теорема\"):\n", "\n", "Для констант $k, d$ и функции $f(n)$ для неотрицательных $n$ определено рекуррентное выражение \n", "\n", "$$ T(n) = kT(n/d) + f(n),$$ где $n/d$ округляется до целого.\n", "\n", "Для $Т(n)$ верны следующие ассимптотические границы:\n", "\n", "1. Если $f(n) = O(n^{log_d k - \\epsilon})$ для константы $\\epsilon > 0$, то $T(n) = \\Theta(n^{log_d k - \\epsilon})$ \n", "2. Если $f(n) = O(n^{log_d k})$ для константы $\\epsilon > 0$, то $T(n) = \\Theta(n^{log_d k} \\cdot log\\ n)$ \n", "3. Если $f(n) = O(n^{log_d k + \\epsilon})$ для константы $\\epsilon > 0$, и $kf(n/d) \\leq cf(n)$ для $c < 1$, то $T(n) = \\Theta(f(n))$ \n", "\n", "
\n", "
\n", "\n", "\\- случай Merge Sort - второй, с константами $d = 2, k = 2$, то есть\n", "\n", "$$f(n) = O(n^{log_2 2} \\cdot log\\ n) = O(n \\cdot log\\ n)$$\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Внешняя сортировка (External sorting)\n", "\n", "\n", "\n", "\n", "В ситуациях, когда массив обрабатываемых (например, сортируемых) данных не помещается в (быструю) оперативную память, приходится привлекать внешние ресурсы (как правило, это жесткий диск; для многих задач они \"неограничены\")\n", "\n", "## External memory\n", "\n", "\n", "\n", "Не физическое представление, а \"математическая\" модель. \n", "\n", "Важно, что одним из критических мест в производительности становится процесс записи/чтения во внешнюю память.\n", "\n", "Будем обозначать ограниченный объем оперативной памяти как $M$, и будем считать, что внешняя память разбита на неогрниченный набор блоков размера $B$.\n", "\n", "\n", "## Описание процесса сортировки\n", "\n", "\n", "\n", "В начала сортировки массив $S$ хранится во внешней памяти, отсортированный массив записывается туда же. \n", "\n", "- Считываем первые $N$ байт данных из внешней памяти, сортируем (напр., _Quicksort_), записываем во внешнюю память отсортированные данные\n", "- Повторяем так $K$ раз ($K\\cdot N \\geq S$) - получаем $K$ отсортированных массивов во внешней памяти\n", "- Merge!\n", " - Возьмем из каждого массива $N / (K+1)$ байт c наибольшими значениями, и выделим еще столько же под выходной буфер. \n", " - Делаем _K-way merge_\n", " \n", " \n", "\n", "\n", "> Вопрос: почему берутся первые $N / (K+1)$ байт?\n", "\n", "\n", "\n", "\n", "\n", "\n", "**will fix typos here**\n", "\n", "\n", "## K-way merge\n", "\n", "\n", "\n", "**K-way merge (без heap'ов)**\n", "\n", "Упрощенный вариант, не учитывающий то, что переодически массивы будут обновляться, а данные надо писать в буфер меньшего размера, чем сам массив\n", "\n", "
\n",
    "1  KWayMerge(Sorted, ArrayOfArrays, k):\n",
    "2      Ptrs = новый массив из k указателей на k массивов, инициализирован 0 \n",
    "3      for i = 0 to length(Sorted):\n",
    "4          index_of_array = FindMinArrayIndex(ArrayOfArrays, Ptrs)\n",
    "5          Sorted[i] = ArrayOfArrays[index_of_array][Ptrs[index_of_array]]\n",
    "6          Ptrs[index_of_array] += 1\n",
    "\n",
    "
\n", "\n", "`FindMinArrayIndex` возвращает индекс массива, в котором сейчас находится минимальный элемент. `Ptrs` модифицируется далее в коде, чтобы снизить риск сайд-эффектов.\n", "\n", "Для упрощения туда не передается набор индексов-ограничений, чтобы случайно не выйти за пределы массива.\n", "\n", "Сложность алгоритма $O(n \\cdot k)$\n", "\n", "**K-way merge (с heap'ами)**\n", "\n", "Идея: сделать heap размера k, где _ключами_ будут минимальные элементы каждого из списков, а ассоциированными с ними значениями - списки.\n", "\n", "Напоминаю, как выглядит heap:\n", "\n", "\n", "\n", "_- только в нашем случае будет не max heap, a min heap_\n", "\n", "Сложность:\n", "\n", "- BuildHeap за $O(k)$\n", "- Минимальный элемент извлекается за $O(1)$, новый мимнимум в списке, из которого извлекли элемент - тоже\n", "- За $O(log\\ k)$ можно восстановить _heap property_\n", "- Наконец, надо извлечь всего $n$ элементов, т.е. повторить перечисленные выше операции $n$ раз. Итого, сложность:\n", "\n", "$$O(k) + n \\cdot (O(log\\ k) + O(1)) = O(k) + O(n \\cdot log\\ k) = O(n \\cdot log\\ k) $$\n", "\n", "\\- это ощутимая экономия при больших значениях k\n", " \n", "**Наконец, K-way merge разделяй-и-властвуй**\n", "\n", "Предлагается использовать стратегию разделяй-и-властвуй для попарного слияния массивов из _массива массивов_ в памяти.\n", "\n", "\n", "\n", "В теории, надо сделать $O(n \\cdot log\\ k)$ операций, сливая попарно массивы (практически полный аналог merge sort). \n", "\n", "> В чем отличия от heap-based K-way merge?\n", "\n", "1. Меньше сравнений - процедура восстановления свойсти кучи требует ~ $2 \\cdot log\\ k$ сравнений, а одна процедура слияния массивов (всех, на одном уровне) - ~ $n$ сравнений, и $log(k)$ уровней. В итоге получается ~ $2n \\cdot log\\ k$ у heap-based против $n \\cdot log\\ k$ у divide-and-conquer.\n", "2. Однако способ \"разделяй-и властвуй\" требует дополнительной памяти; в целом сравнение скорости требует экспериментальных проверок.\n", "\n", "Псевдокод Merge:\n", "
\n",
    "1  Merge(Array, begin, middle, end, Copy):  // ← Copy - это дополнительная память!\n",
    "2      fst, snd = begin, middle\n",
    "3      for ptr in range(begin, end)\n",
    "4          if fst < middle and (snd >= end or Array[fst] <= Array[snd])\n",
    "5              Copy[ptr] = Array[fst]\n",
    "6              fst += 1\n",
    "7          else\n",
    "8              Copy[ptr] = Array[snd]\n",
    "9              snd += 1\n",
    "\n",
    "
\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Алгоритм поиска заданного элемента\n", "\n", "\n", "\n", " \n", "**Описание алгоритма** \n", "\n", "Функция `Select(Array, i)`: Данный алгоритм использует метод \"разделяй-и-властвуй\".\n", "\n", "1. _Разделение_: оригинальный массив делится на $\\lceil n/5 \\rceil$ частей\n", "2. Для каждого подмассива находится медиана; они объединяются в _массив медиан_\n", "3. В _массиве медиан_ рекурсивно при помощи `Select` ищется медиана медиан, далее $x$\n", "4. Применяется Partition (как в Quicksort) для разделения массива на две части - меньше либо равных $x$, и больших элементов.\n", " - Получим $k$ \"меньших\" элементов, и $(n-k)$ \"больших\". \n", "5. Если $k = i$, то возвращаем $x$ как целевой элемент.\n", " - Иначе, ищем либо $i$-й среди меньшей части, либо, если $i > k$, $(i - k)$-й - среди большей\n", "\n", "**Как это выглядит**\n", "\n", "\n", "\n", "_- в $k$ элементов входит и сам $x$_\n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$k = 3 \\cdot \\lceil(n/5)/2\\rceil$\n", "\n", "$n - k$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$T(n) = T(\\lceil n / 5 \\rceil) + T(3 \\cdot \\lceil(n/5)/2\\rceil)\\ or \\ T(\\lceil n / 5 \\rceil) + T(n - 3 \\cdot \\lceil(n/5)/2\\rceil)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Домашняя работа\n", "\n", "\n", "\n", "\n", "\n", "- Основное: реализовать Select: 3 балла максимум; 2 балла - если есть недочеты, влияющие на производительность, но элемент выбирается за $O(n)$\n", "- Дополнительное: \n", " - реализовать сортировку, использующую (возможно, искуственные - я понимаю, что она сортировка будет работать _долго_, и тестировать будет непросто, если сортировать несколько Gb) ограничения по памяти, любым из алгоритмов k-way merge (2 балла).\n", " - Сравнить работоспособность сортировки для разного количества блоков во внешней памяти - 10, 20, 50, 100.. или другая подобная последовательность (1 балл)\n", " \n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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.6.7" } }, "nbformat": 4, "nbformat_minor": 2 }