Медианный выбор: не ваш средний алгоритм

Сегодня я хочу поговорить о решении проблем как алгоритмист. Моя программа проверки орфографии орет на меня красными закорючками, но алгоритмист — это всего лишь слово, а алгоритм — это просто последовательность шагов (рецепт, если хотите), чтобы перейти от проблемы к решению.

Кроме того, алгоритм должен:

  • решить обобщенную версию задачи и
  • быть эффективным

Это означает, что вместо того, чтобы думать о у Джека 7 яблок, у Джилл 10 яблок, сколько яблок они должны дать Терпению? мы хотим решить у Джека есть x яблок, у Джилл есть y яблок. , и цель алгоритма всегда состоит в том, чтобы решить, сколько еды должно быть у Терпения. Я шучу. Мы также хотели бы иметь возможность решить проблему быстро, и мы хотели бы иметь возможность выразить, что означает «быстро».

Теперь это похоже на математику, и это математика. Реализация алгоритма — это функция, и функция принимает входные данные (наша проблемная область, выраженная в виде некоторой переменной (переменных)) и возвращает результат (наше решение, выраженное в виде некоторой другой переменной (переменных)).

В оставшейся части этого поста я буду использовать стандартные обозначения для анализа алгоритмов (например, big-O), и мы просто будем говорить об анализе с точки зрения времени. По сути, big-O описывает производительность алгоритма в наихудшем случае, то есть сколько времени требуется для решения бесконечно большой версии нашей задачи. Обычно это время зависит от ввода, поэтому, например, если n описывает размер нашего ввода, говоря, что некоторый алгоритм O(n) означает, что время, которое требуется для запуска он имеет линейную связь с n (линейно растет с n). Вот вам и математическое определение.

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

Найти медиану списка чисел

Медиана — это «среднее» число в отсортированном списке чисел (не путать со средним/средним). Итак, если у нас есть отсортированный список (будет работать либо от меньшего к большему, либо от большего к меньшему), и мы знаем размер списка, давайте просто возьмем число в позиции size/2, а затем были сделаны. Если размер списка четный, мы возьмем два средних числа и усредним их. Бум.

Это слишком просто, поэтому давайте предположим, что список не отсортирован.

Вариант №1: грубая сила

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

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

Каковы все возможные решения задачи медианного поиска?

Что ж, наше решение — это число, и у нас есть список чисел для рассмотрения. Любое из них может быть медианой, так что давайте просто возьмем их все и проверим, спросив каждое число: являетесь ли вы медианой?

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

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

Возможность 2. Сортировка

Мы уже говорили о том, насколько замечательной была бы эта задача, если бы наш список чисел был отсортирован. Итак, давайте разберемся! И мы надеемся, что время, необходимое для сортировки, будет меньше O(n²).

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

Этот алгоритм называется сортировка выбором. Сколько времени это занимает?

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

Так что это не лучше грубой силы.

Что ж, я немного схвачусь. Оказывается, существует целый класс алгоритмов сортировки, некоторые из которых работают намного лучше, чем сортировка выбором. Одним из них является быстрая сортировка, и да, она быстрая — выполняется за O(nlogn). (Если вам интересно, это лучшее/самое быстрое, что мы можем сделать: ни один алгоритм сортировки не может сделать это более эффективно. Почему бы и нет? Вот отличное объяснение.)

Как работает быстрая сортировка?

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

Но теперь мы знаем, что опорное число находится в своем последнем правильном месте.

И мы разбили нашу проблему на две более мелкие подзадачи, и все, что нам нужно сделать, это запустить быструю сортировку этих более мелких подзадач. В какой-то момент у нас появятся подзадачи размера 1 (подсписок содержит только один элемент, который по определению отсортирован), и тогда мы закончим. Я оставлю это вам, чтобы понять, почему это O(nlogn).

Потрясающий!

Вариант №3: быстрый выбор

Жаль, меня все еще не устраивает O(nlogn). Что еще мы можем сделать?

Давайте вернемся к идее разделения списка, которую мы использовали при использовании быстрой сортировки. Быстрая сортировка – это алгоритм разделяй и властвуй, и самое интересное, что происходит всякий раз, когда мы делим список, заключается в том, что "стержень" оказывается на своем законном месте в окончательном отсортированном списке.

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

Мы уже говорили, что мы «случайно» выбираем опорные точки. Если бы мы могли каким-то образом всегда выбирать опорную точку, которая оказывается медианой, мы бы не пытались придумывать для этого алгоритмы ;).

Но это все еще полезно, потому что после того, как мы выберем точку опоры, мы знаем, в каком разделе находится медиана! Медиана всегда находится в size/2-ой позиции. Если наша точка поворота находится слева от этого, нам нужно сосредоточиться только на правом разделе. Если наша точка поворота находится справа, нам нужно смотреть только на левый раздел.

Таким образом, мы можем как бы отбросить и просто избежать работы над разделом, которому, как мы знаем, не принадлежит медиана. .

Разве это не O(nlogn), если мы делаем вещи для быстрой сортировки?

При первом запуске мы рассмотрим n чисел. Но во втором прогоне, сделав некоторые предположения о выборе разумных опорных точек в среднем по всем опорным точкам (довольно хорошее предположение, поскольку мы выбираем случайным образом), нам нужно будет просмотреть только n/2 числа. . На третьем — еще половина — n/4.

Итак, у нас есть n + n/2 + n/4 + … + n/xс x стремящимся к бесконечности.Это суммирование приближается к 2n,что равно O(n). Это фантастика — интуитивно мы как бы понимаем, что не можем быть лучше, чем линейное время, поскольку простой просмотр списка занимает nвремени, и мы определенно должны видеть все в список, чтобы найти медиану. Мы максимально оптимизировали этот алгоритм!

Возможность 4. Детерминированные медианы медиан

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

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

Можем ли мы придумать что-то детерминированное и работающее в линейном времени?

Если мы сможем гарантировать «разумный поворот», то концепция секционирования из quickselect по-прежнему будет работать. В частности, мы хотим иметь возможность выбрасывать множество чисел при каждом разбиении. Другими словами, хороший свод поможет нам быстро сократить список интересующих нас чисел (то есть подсписок, в котором находится медиана).

Это основа алгоритма медианы медиан:

  1. Разделите список чисел на небольшие и равные по размеру группы (группы по 5 — хороший выбор).
  2. Найдите медиану каждой группы. (Группы небольшие, поэтому мы можем предположить, что работа здесь O(n)).
  3. Найдите медиану всех этих медиан, назовем ее M.
  4. Используйте M в качестве опорной точки.

Откуда мы знаем, что M — хороший выбор для разворота?

Итак, мы знаем, что раздел слева от M содержит медианы примерно половины групп (поскольку M — это медиана этих медиан). И внутри этих групп около половины чисел в каждой группе меньше медианы (все еще используя определение медианы здесь). Так что кажется, что мы можем отбросить изрядное количество чисел, если медиана находится в разделе справа от M! Поскольку мы можем сделать то же самое для раздела справа от M, независимо от того, над каким разделом мы продолжаем работать, мы разумно уменьшили размер нашего списка.

Поскольку мы по-прежнему используем быстрый выбор, наша производительность по-прежнему составляет O(n). (Если вы не уверены, проверьте это для отличного строгого доказательства, использующего рекуррентные отношения и все такое хорошее!)

Мы сделали это, и НАСА должно нанять нас.

Это было много работы. Почему нас вообще волнует проблема медианного поиска?

Если вам наплевать на медианы, я вас не виню (мне они тоже не особо нужны). Но что меня определенно волнует, так это подход к созданию все лучших и лучших алгоритмов. Я представил эти четыре алгоритма таким образом, чтобы было несколько понятно, почему и как мы переходим от №1 к №4, но, к сожалению, не всегда есть систематический переход от грубой силы к чему-то умному. Иногда вы узнаете, какие оптимизации можно выполнить, взглянув на решение грубой силы, но чаще всего нет. (Вы видите большое сходство между грубой силой и медианой среди медиан? Я точно не вижу.)

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

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

Весь этот пост был вдохновлен разговором с моим другом Кубой. Спасибо за то, что всегда был готов сесть со мной и научить меня классным вещам. :)