Алгоритм быстрого отбора и оптимизация BFPRT для быстрого отсеивания лучших

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

В предыдущей серии статей о Python мы представили использование библиотеки heapq, которую можно найти в O(nlogn) Отфильтруйте лучшие K больших или лучших K маленьких элементов во времени. Сегодня мы рассмотрим алгоритм быстрого выбора, который позволяет добиться более быстрого выбора.

вывод мышления

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

Предполагая, что мы не знаем, какое решение является правильным в данный момент, мы хотим как можно быстрее найти K лучших элементов. Если мы будем искать один за другим, этот процесс будет очень медленным, если мы не сможем сделать O(1) Находить. Очевидно, что это невозможно, потому что, даже если это быстрый поиск дерева баланса, поиск слова также требует O(logn) . Так что невозможно найти их один за другим. Тогда осталось только партии поисков, и есть два типа пакетных поисков, один - это поиск k напрямую, а другой - это поиск несколько раз, и, наконец, получите положительное решение.

Мы не знаем, какой метод более надежен, но первый кажется менее выполнимым, потому что это сама проблема, а второй кажется чуть более выполнимым. В этой задаче у нас нет лишней информации, и найти K элементов напрямую не должно быть легко. Так что это может быть лучший способ получить решение с помощью нескольких поисков. Множественные поиски также можно просто разделить на два случая: один — искать пакет за раз и, наконец, объединять их вместе, а другой — каждый раз сужать диапазон поиска и, наконец, блокировать ответ.

На этом этапе, если вы знакомы с алгоритмом «разделяй и властвуй», вы почувствуете, что он очень похож на сценарий применения алгоритма «разделяй и властвуй». Мы хотим решить относительно большую проблему, но решить ее напрямую сложно, поэтому мы разбираем ее, разбираем большую проблему на маленькие и решаем исходную большую проблему, решая маленькую.

Алгоритмы «разделяй и властвуй», с которыми мы сейчас знакомы, кажутся только сортировкой слиянием и быстрой сортировкой Мы можем попытаться применить эти два алгоритма к этой проблеме. Основная идея сортировки слиянием состоит в том, чтобы разделить массив на две части за раз, а затем найти нужное решение в процессе слияния двух массивов. Это решение работает, но ничем не отличается от сортировки. Как мы сказали в начале этой статьи, мы ищем алгоритмы, которые работают быстрее, чем сортировка. Давайте посмотрим на быструю сортировку: она каждый раз устанавливает контрольный показатель, а затем настраивает элементы в массиве таким образом, чтобы элементы, меньшие контрольного, находились слева от него, а те, что больше, — справа. Последняя позиция эталона является правильной позицией после упорядочения данных. Этот метод кажется очень близким к тому, что мы хотим.

Итак, мы просто следовали подсказкам и нашли правильный путь. Конечно, реальный процесс мышления может быть более сложным, и будет рассмотрено больше ситуаций, но общий процесс вывода мыслей должен быть аналогичным. То же самое и с решением задач: новички часто полагаются на озарение, а у экспертов есть целая цепочка мышления. Многие алгоритмические проблемы кажутся запутанными, но на самом деле есть следы, по которым нужно следовать. Обучение ментальной модели нахождению правильного решения — единственный способ для новичка стать мастером, а также основа способности алгоритма.

Принцип алгоритма

Давайте внимательно проанализируем его, после быстрой настройки сортировки мы можем определить положение бенчмарка, так что есть три случая. Во-первых, его позиция просто K, что означает, что массив перед ним является ответом, и его можно вернуть напрямую. Если он меньше K, значит, бенчмарк меньше, и нужно повторно выбрать бенчмарк в массиве справа от него. Если он больше К, значит эталон слишком велик, и мы можем напрямую игнорировать элемент справа от него, потому что элемент справа от него не должен быть в ответе.

Мы можем обратиться к следующей картине:

С идеей код написать не сложно:

def quick_select_without_optimizer(arr, k):
    n = len(arr)
    # 如果k大于n，没啥好说的，直接返回
    if k >= n:
        return arr

    # 缓存
    buffer = []
    while arr:
        # 选择最后一个元素作为标杆
        mark = arr.pop()
        less, greater = [], []
        # 遍历数组，将元素分为less和greater
        for x in arr:
            if x <= mark:
                less.append(x)
            else:
                greater.append(x)
        # 判断三种情况，如果相等直接返回
        if len(less) == k:
            return less
        # 如果小于，将less存入buffer，因为它一定是答案的一部分，可以简化计算
        elif len(less) < k:
            buffer += less
            # k要减去less的长度
            k -= len(less)
            arr = [mark] + greater
        else:
            # 如果大于，直接舍弃右边
            arr = less

Анализ сложности

После написания кода проанализируем сложность алгоритма. У некоторых студентов могут возникнуть сомнения, этот алгоритм в основном такой же, как и быстрая сортировка, почему он быстрее?

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

Видно, что хотя общее количество итераций по-прежнему log_2n раз, но число элементов, пройденных в каждом слое, уже не равно n. Мы предполагаем, что длина массива будет уменьшаться наполовину на каждой итерации, и она завершится, когда длина массива будет равна 1. Складываем все длины обхода каждого слоя, и получаем пропорциональную последовательность:

Длина этой пропорциональной последовательности равна log_2n , применим формулу суммирования пропорциональных рядов:

\displaystyle S=\frac{a_1(1-q^n)}{1-q}=\frac{1(1-2n)}{1-2}\approx 2n

То есть, хотя его форма очень похожа на быструю сортировку, поскольку мы сужаем область обхода каждый раз в процессе обхода, общая сложность контролируется внутри O(n) . Конечно, это только сложность в идеальной ситуации, как правило, при различном распределении данных реальная сложность будет немного колебаться. Это можно понимать как умножение на плавающую константу.

Когда мы анализировали быструю сортировку ранее, мы пришли к выводу, что если исходный массив находится в обратном порядке, сложность быстрой сортировки снизится до O(n^2) . Наш текущий алгоритм быстрого выбора и алгоритм быстрой сортировки почти одинаковы, и вся идея та же, то есть, когда массив находится в обратном порядке, также возникает проблема снижения сложности. К счастью, эта проблема не является неразрешимой, давайте проанализируем оптимизацию этой ситуации.

Оптимизация исследования

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

По сравнению с выбором реперных точек оценка обратного порядка массива не является предпочтительной. Потому что для массивов, которые строго не перевернуты, тоже может быть много сложностей. Если мы будем судить об обратном порядке массива по номеру обратного порядка, это принесет дополнительные накладные расходы, поэтому мы можем начать только с выбора эталонов. Раньше мы выбирали последний элемент по умолчанию.На самом деле, это не проблема позиции элемента.Независимо от того, какая позиция выбрана, могут быть соответствующие крайние случаи, которые увеличат сложность, поэтому простое изменение выбранной позиции не решит Нам нужно разработать алгоритмы отдельно для этой проблемы.

Относительно простая идея заключается в том, что мы можем выбрать элементы в первой, последней и средней позициях, а затем выбрать второй по величине элемент в качестве эталона. Это решение простое в реализации и эффект хороший, но если его проанализировать, то принципиально проблемы оно не решает, потому что все же могут быть экстремальные ситуации, типа первый, последний и средний — это всего лишь три самых больших элемента. Хотя эта вероятность намного ниже, чем максимальное появление одного элемента. Другая проблема заключается в том, что выбранные таким образом бенчмарки не могут гарантировать сбалансированность разделенных массивов.

Алгоритм BFPRT

Здесь я познакомлю вас с потрясающим алгоритмом не потому, что он сложный, а потому, что он действительно потрясающий. Его зовут BFPRT, и он был изобретен Блюмом, Флойдом, Праттом, Ривестом и Тарьяном. Если вы читали «Введение в алгоритмы», вы обязательно найдете названия некоторых из них. Алгоритм может найти более подходящий ориентир для разбиения массива при быстрой сортировке и быстром выборе.

Алгоритм очень прост, всего несколько шагов:

Определить, больше ли элемент массива 5, если меньше 5, отсортировать его и вернуть медиану массива
Если элементов больше 5, сгруппируйте массив в группы по 5 элементов, чтобы последний сгруппированный элемент был меньше 5.
Для каждой группы выполните сортировку вставками.
Выберите отсортированную медиану каждой группы, чтобы сформировать новый массив
Повторите вышеуказанную операцию

Идея алгоритма очень проста, по сути, это процесс непрерывного выбора медианы. Давайте сначала докажем его правильность.Предположим, что окончательное выбранное число равно x, а массив длины n даст n/5 групп. Поскольку мы берем медиану медиан, у половины из n/5 групп медианы меньше x, а у половины больше x. В группе, медиана которой больше, есть по крайней мере 3 элемента, большие или равные ей, поэтому в целом не менее n/10 * 3 = 0,3n элементов больше или равны х. Точно так же это может быть доказал, что 30% элементов меньше или равны x. Таким образом, наихудший выбранный случай x — это число в позиции 70%.

Наконец, давайте проанализируем его сложность, мы можем получить неравенство:

\displaystyle T(n) \leq T(\frac{n}{5}) + T(\frac{7n}{10}) + cn

в $T(\frac{n}{5})$ ищет $\frac{n}{5}$ средняя сложность, $T(\frac{7n}{10})$ является наихудшим случаем рекурсии, т.е. может уменьшить длину массива только на 30%.— сложность многократной сортировки с использованием сортировки вставками, где c — константа.

Мы можем легко доказать $T(n)=T(\frac{n}{2}) + cn$ и $T(n)=T(\frac{7n}{10}) + cn$ оба O(n) Сложность , здесь докажем первую на примере:

\displaystyle\begin{aligned} T(n) &= T(\frac{n}{2}) + cn \\ T(\frac{n}{2}) &= T(\frac{n}{4}) + \frac{cn}{2} \\ \vdots \\ T(2) &= T(1) + c \end{aligned}

Складываем эту формулу, чтобы получить:

T(n)=c(1 + 2 + 4 + \cdots + n) \approx 2cn

Аналогично можно доказать и $T(n)=T(\frac{7n}{10})+cn$ Слишком O(n) алгоритм, так $\displaystyle T(n) \leq T(\frac{n}{5}) + T(\frac{7n}{10}) + cn$ Слишком O(n) алгоритм.

Код легко написать в соответствии с определением алгоритма BFPRT:

def bfprt(arr, l=None, r=None):
    if l is None or r is None:
        l, r = 0, len(arr)
    length = r - l
    # 如果长度小于5，直接返回中位数
    if length <= 5:
        arr[l: r] = insert_sort(arr[l: r])
        return l + length // 2
    medium_num = l
    start = l
    # 否则每5个数分组
    while start + 5 < r:
        # 对每5个数进行插入排序
        arr[start: start + 5] = insert_sort(arr[start: start + 5])
        arr[medium_num], arr[start + 2] = arr[start + 2], arr[medium_num]
        medium_num += 1
        start += 5
    # 特殊处理最后不足5个的情况
    if start < r:
        arr[start:r] = insert_sort(arr[start:r])
        _l = r - start
        arr[medium_num], arr[start + _l // 2] = arr[start + _l // 2], arr[medium_num]
        medium_num += 1
    # 递归调用，对中位数继续求中位数
    return bfprt(arr, l, medium_num)

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

def quick_select(arr, k):
    n = len(arr)
    if k >= n:
        return arr

    # 获取标杆的下标
    mark = bfprt(arr)
    arr[mark], arr[-1] = arr[-1], arr[mark]
    buffer = []

    while arr:
        mark = arr.pop()
        less, greater = [], []
        for x in arr:
            if x <= mark:
                less.append(x)
            else:
                greater.append(x)
        if len(less) == k:
            return buffer + less
        elif len(less) < k:
            k -= len(less)
            buffer += less
            arr = [mark] + greater
        else:
            arr = less

Если посмотреть на код, то разницы от вышеприведенной в принципе нет, разница только в том, что перед выбором вы получаете бенчмарк. Здесь я вызываю его только один раз в начале, и, конечно, я могу вызывать его каждый раз в цикле while, но лично я не считаю это нужным, потому что при получении бенчмарка все массивы будут нарушены, что достаточно, чтобы избежать крайних случаев.

Сегодняшняя статья немного длинновата, но с содержанием все в порядке, особенно алгоритм BFPRT, который действительно классический, не сложный, но очень гениальный. Заинтересованные студенты могут узнать об историях пяти больших мужчин, стоящих за ним, которые, вероятно, намного интереснее, чем моя статья.

Ну вот и все на сегодняшнюю статью.Если вы чувствуете, что что-то приобрели, пожалуйста, отсканируйте код и обратите внимание.Ваши усилия очень важны для меня.