Содержание¶

Оценка скорости алгоритмов¶

Как оценить скорость работы алгоритма¶

Если необходимо сделать оценку скорости, то нужно делать замеры для большого количества значений (размера входных данных). Чем больше точек - тем точнее данные
- можно брать значения по линейно
- можно брать по логарифмической шкале
- иногда итмеет смысл брать значения чуть ли не непрерывно, потому что в таком случае можно посмотреть на динамику, когда происходит выделение памяти etc
Также стоит делать $n$ замеров, чтобы получать усреденные значения
Просто замерять время между выполнением команд может быть недостаточно точно - т.к. в процесс мог влезть другой процесс и так далее. Нужно мерять cpu time

Какие есть интрументы для измерения¶

Python
- если вы используете ipython, есть magic %%time и %%timeit
- есть библиотека profile
C++
- функции из chrono :)
- vallgrind's callgrind
- gperftools
Java
- ссылка - список профайлеров

в начало

Разделяй и властвуй¶

Идея¶

Разбить большую задачу на такие же, но меньшие по размеру, и так далее
Решить задачу, когда размер станет мал
Объединить результаты

Работа mergesort

в начало

Mergesort¶

Краткое описание¶

Нужен механизм разделения
Алгоритм для сортировки минимальной подзадачи
Алгоритм объединения (merge)

Будем делить массивы ~пополам, учитывая, что один их размер может быть нечетным

Сколько всего будет разбиений?

Сам алгоритм:

1  MergeSort(Array, end):
2      Copy = CopyArray(Array)
3      SplitMerge(Copy, 0, n, Array)
4  
5 
6  SplitMerge(Copy, begin, end, Array):
7      if end - begin < 2
8         return
9      middle = (end + begin) // 2
10     SplitMerge(Array, begin, middle, Copy)
11     SplitMerge(Array, middle, end, Copy)
12     Merge(Copy, begin, middle, end, Array)

- постоянно меняются местами Array и Copy - данные копируются из одного в другой

Функция Merge - время работы $O(n)$

в начало

Достаем двойные листочки!¶

Давайте напишем Merge (и весь алгоритм), определение MergeSort выглядит довольно простым.

Идея: есть два массива одинакового рамера, второй разбит на две части
Переносим элементы в первый массив из второго либо из первой, либо из второй части

в начало

[[1, 1, 1, 1], [2, 3, 4, 5]]
[1, 1, 1, 1, 2, 3, 4, 5]

[["2",3,4,5], [1,1,1,"1"]]
[1,1,1,1,2,3,4,5]

Merge¶

1  Merge(Array, begin, middle, end, Copy):
2      fst, snd = begin, middle
3      for ptr in range(begin, end)
4          if fst < middle and (snd >= end or Array[fst] <= Array[snd])
5              Copy[ptr] = Array[fst]
6              fst += 1
7          else
8              Copy[ptr] = Array[snd]
9              snd += 1

Сложность, плюсы, минусы, стабильность¶

Если посмотреть еще раз на это изображение:

- становится интуитивно понятно, какая у алгоритма сложноcть.

$O(n)$ - на Merge на каждом "уровне"
$O(log(n))$ уровней

- получается $O(n \cdot log(n))$ сортировка

Плюсы сортировки¶

Гарантированная скорость $O(n \cdot log(n))$
Стабильность
Возможность параллелизации
Модификации используются для внешней сортировки
Подходит хорошо для списков (см. далее)

Минусы¶

$O(n)$ памяти - без оптимизаций
Немного медленнее Quicksort

в начало

Варианты¶

Как можно усовершенствовать Mergesort (много как, на самом деле)

Сделать параллельным¶

1  SplitMerge(Copy, begin, end, Array):
2      if end - begin < 2
3         return
4      middle = (end + begin) // 2
5      fork SplitMerge(Array, begin, middle, Copy)
6      join
7      SplitMerge(Array, middle, end, Copy)
8      Merge(Copy, begin, middle, end, Array)

Fork-join model¶

Это стандартный подход, исользующийся для алгоритмов "Divide-and-Conquer". На этот каркас можно "натянуть" и другие алгоритмы

1  Solve(problem):
2      if problem is small enough:
3          solve problem directly (sequential algorithm)
4      else:
5          for part in Subdivide(problem)
6              fork subtask to Solve(part)
7          join all subtasks spawned in previous loop
8          return combined results

Другие идеи¶

Использовать имеющиеся в данных убывающие / возрастающие посоледовательности (и не сортировать их)
Можно превратить в блочную сортировку
В модификации хорошо работает со списками - когда доступ по индексу закрыт. При этом можно обойтись без доп. памяти/

в начало

Quicksort¶

Идея¶

Выбрать стержневой элемент
Разбить массивы так, чтобы "слева" от стержневого были элементы $\leq$ , "справа" - большие
Повторять для "правой" и "левой" половин, пока длина массива > 1

Особенности алгоритма¶

Фичи и плюсы¶

Алгоритм придумал Хоар для быстрой сортировки словарей (1959)
Алгоритм обладает средним временем работы $O(n \cdot log(n))$ , но наихудшим $O(n^2)$
При этом у него хорошие константы
Не нужно дополнительно выделять память
Можно распараллелить

Недостатки¶

нестабилен
не гарантированно быстр (может "тормозить")
нестабилен

Псевдокод¶

1  Quicksort(Array, begin, end):
2      if begin < end:
3          pivot = Partition(Array, begin, end)
4          Quicksort(Array, begin, pivot)
5          Quicksort(Array, pivot+1, end)
</pre>
</font>
в начало

Процедура Partition¶

Итак, есть сигнатура: Partition(Array, begin, end) -> pivot

Что эта функция должна делать?
И как ее реализовать (как минимум один способ)?

На семинаре демонстрировалось неправильное изображение! Здесь приведен исправленный вариант.

Использовалось 1-индексирование, сказано про это не было - теперь псевдокод исправлен на 0-индексирование
Была показана работа Partition для создания убывающих массивов (вместо возрастающих, как в коде)
Если $j$ -й элемент меньше либо равен стержневого, то меняются местами $i$ +1 и $j$ -й элементы, а $i += 1$
Менябщиеся элементы выделены градиентом
Теперь изображение соответствует коду, приведенному ниже

Псевдокод Partition¶

Это один из вариантов. Мы можем реализовать рандомизированный вариант или схему Хоара.

Процесс происходит inplace
Процесс не гарантирует стабильности

Код:

1  Partition(Array, begin, end):
2      pivot = Array[end-1]  // например, мы можем взять элемент из конца
3      i = begin - 1  // да, он может быть < 0, это ОК
4      for j = begin to end-2  // имеется в виду "по элемент end-2 включительно"
5          if Array[j] ≤ pivot
6              i += 1
7              swap(Array, j, i)
8      swap(Array, i+1, end-1)  // ставим стержневой элемент на место
9      return i + 1

Список исправлений в псевдокоде:

Используется Array[end-1] вместо Array[end]
Используется swap(Array, i+1, end-1) вместо swap(Array, i+1, end)
Используется for j = begin to end-2 вместо for j = begin to end-1
Используется Quicksort(Array, begin, pivot) вместо Quicksort(Array, begin, pivot-1)
Последнее верно для Quicksort и TailQuicksort (см. ниже)

В начало

Здесь приведен код, который соответсвует иллюстрации с вебинара, и сама иллюстрация.

Оператор `≤` заменен на `≥`, располагающий меньший и больший массивы соответсвенно справа и слева и "сортирующий" в обратном порядке.

1  Partition(Array, begin, end):
2      pivot = Array[end-1]  // например, мы можем взять элемент из конца
3      i = begin - 1  // да, он может быть < 0, это ОК
4      for j = begin to end-2  // имеется в виду "по элемент end-2 включительно"
5          if Array[j] ≥ pivot
6              i += 1 
7              swap(Array, j, i)
8      swap(Array, i+1, end-1)  // ставим стержневой элемент на место
9      return i + 1

в начало

Код на python (с минимальными отличиями от псевдокода)¶

Код показывет разницу между decreasing и increasing partition

def quicksrot(array, begin, end, partition):
    if begin < end:
        pivot = partition(array, begin, end)
        quicksrot(array, begin, pivot, partition)
        quicksrot(array, pivot+1, end, partition)
        

def partition_increasing(array, begin, end):
    pivot = array[end-1]
    i = begin - 1
    for j in range(begin, end-1):
        if array[j] <= pivot:
            i += 1
            swap(array, i, j)
    swap(array, i+1, end-1)
    return i + 1


def partition_decreasing(array, begin, end):
    pivot = array[end-1]
    i = begin - 1
    for j in range(begin, end-1):
        if array[j] >= pivot:
            i += 1
            swap(array, i, j)
    swap(array, i+1, end-1)
    return i + 1


def swap(array, i, j):
    buff = array[i]
    array[i] = array[j]
    array[j] = buff

arr = list(range(10))
partition_increasing(arr, 0, 10)
arr

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Сортировка в убывающем порядке¶

quicksrot(arr, 0, 10, partition_decreasing)
arr

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Сортировка в возрастающем порядке¶

quicksrot(arr, 0, 10, partition_increasing)
arr

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Несколько примеров¶

def test(array, partition):
    quicksrot(array, 0, len(arr), partition)
    assert len(array) > 2
    for i, j in zip(array[:-1], array[1:]):
        assert i <= j if partition is partition_increasing else i >= j

        
for i in range(10):
    arr = list(range(20))
    np.random.shuffle(arr)
    cpy = [i for i in arr]
    print("unsorted: {}".format(arr))
    test(arr, partition_decreasing)
    test(cpy, partition_increasing)
    print("decreasing: {}".format(arr))
    print("increasing: {}".format(cpy))
    print("--------------------------")

unsorted: [10, 18, 2, 17, 0, 1, 19, 13, 15, 5, 12, 16, 14, 3, 9, 7, 11, 6, 4, 8]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [12, 2, 17, 8, 19, 10, 0, 1, 6, 9, 3, 4, 16, 13, 11, 14, 5, 15, 7, 18]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [19, 7, 13, 8, 12, 0, 14, 1, 10, 16, 11, 4, 3, 6, 2, 17, 15, 18, 5, 9]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [4, 8, 0, 12, 1, 10, 7, 2, 11, 17, 3, 5, 19, 9, 14, 13, 16, 6, 15, 18]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [19, 5, 18, 4, 3, 12, 10, 17, 13, 14, 11, 2, 1, 6, 0, 9, 7, 15, 16, 8]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [19, 2, 0, 12, 4, 11, 10, 8, 6, 14, 7, 9, 1, 3, 15, 16, 17, 13, 18, 5]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [7, 13, 17, 18, 16, 10, 0, 8, 19, 3, 14, 15, 12, 6, 4, 9, 11, 5, 1, 2]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [6, 2, 0, 13, 17, 12, 19, 4, 3, 8, 7, 1, 11, 15, 14, 18, 10, 9, 5, 16]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [15, 9, 2, 13, 12, 16, 10, 1, 8, 11, 4, 7, 19, 18, 6, 5, 17, 14, 3, 0]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------
unsorted: [7, 1, 13, 15, 11, 6, 3, 18, 19, 8, 17, 5, 0, 9, 14, 4, 12, 10, 2, 16]
decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
--------------------------

arr = [1, 1, 1, 1, -4, 5, 5, 5, 5, 56, 5, 5, 5, 5]
cpy = [i for i in arr]
quicksrot(arr, 0, len(arr), partition_increasing)
arr

[-4, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 56]

quicksrot(cpy, 0, len(arr), partition_decreasing)
cpy

[56, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, -4]

в начало

Варианты¶

Randomized¶

Если массив организован так, что pivot всегда неудачный - можно обойтись при помощи внесеня рандомизации

Немного вопросов:

Как сделать рандомизацию?
Сколько раз будет генерироваться случайное число?
Какова примерная оценка вероятности того, что всегда будет выбираться наихудший случай?

Hoare Partition¶

Оригинальная схема упорядочения значений, предложенная Хоаром.
Без псевдокода - но его легко найти

wiki/Quicksort - Hoare partition scheme

Хвостовая рекурсия¶

1  TailQuicksort(Array, begin, end):
2      while begin < end:
3          pivot = Partition(Array, begin, end)
4          TailQuicksort(Array, begin, pivot)
5          begin = pivot + 1

Какова будет глубина стека при использовании такого алгоритма?

В начало

Timsort¶

История¶

Алгоритм изобрел Тим Питерс в 2002 г. для использования в языке Python
Алгоритм является улучшением merge sort
ссылка

/* Lots of code for an adaptive, stable, natural mergesort. There are many

pieces to this algorithm; read listsort.txt for overviews and details. */ </pre> - здесь его даже Timsort не зовут

Особенности алгоритма¶

Это merge sort на стероидах
Алгоритм использует неубывающие и невозрастающие последовательности в данных (последние он разворачивает), которые называются run. Ссылки на run'ы отправляются в стек
Для сортировки маленьких подпоследовательностей < minrun используется insertion sort
minrun выбирается от 32 до 64 - из соображений, что лучше всего разбивать на части, близкие к степеням двойки
алгоритм адаптивный, стабильный
run'ы сливаются по очереди и по ссылкам, что позволяет не выделять большое количество памяти -

$$ |Z| > |Y| + |X| $$$$ |Y| > |X| $$$$ \rightarrow X, Y \ merged $$$$ else\ Y,\ smallest(Z, X) merged $$

Ссылки¶

Ссылки на статьи про Timsort на [hackernoon](https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399) и [dev.to](https://dev.to/s_awdesh/timsort-fastest-sorting-algorithm-for-real-world-problems--2jhd)

в начало

Домашняя работа¶

Реализовать:

MergeSort или QuickSort (рандомизированный и обычный)

алгоритм работает корректно, используется insertion sort: 3 балла
алгоритм работает корректно, но выполняет много лишних действий / отклоняется от реализации не в лучшую сторону - 2 балл

Дополнительно:

quicksort - сравнить рандомизированный и обычный варианты - 1 балл
mergsesort - добавить обработку run'ов - 1 балл
распараллелить алгоритм - 1 балл (если считаете, что этот материал надо разобрать отдельно - напишите в слак) - 1 балл
делать оба алгоритма не обязательно, но при желании можно, баллы ставятся за лучший :

в начало