Разделите и покорите алгоритмы - Почему бы не разделить больше частей, чем два?

В алгоритмах разделения и покорения, таких как quicksort и mergesort, вход обычно (по крайней мере во вступительных текстах) разделен на два , а затем два меньших набора данных обрабатываются рекурсивно. Для меня имеет смысл, что это ускоряет решение проблемы, если две половины занимают менее половины работы с целым набором данных. Но почему бы не разбить набор данных на три части? Четыре? п

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

Я также видел много ссылок на 3-way quicksort. Когда это происходит быстрее? Что используется на практике?

31 голос | спросил beta 5 Maypm13 2013, 22:21:31

5 ответов


48
  

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

Это not суть алгоритмов разделения и покорения. Обычно дело в том, что алгоритмы вообще не могут «обрабатывать весь набор данных». Вместо этого он разбивается на кусочки, которые тривиальны для решения (например, сортировка двух чисел), затем они решаются тривиально, а результаты рекомбинируются таким образом, что дает решение для полного набора данных.

  

Но почему бы не разбить набор данных на три части? Четыре? п?

В основном потому, что он разбивает его на более чем две части и рекомбинирует более двух результатов приводит к более сложной реализации, но не меняет фундаментальной (Big O) характеристики алгоритма - разница является постоянным фактором и может привести к замедлению, если деление и рекомбинация более чем 2 подмножеств создают дополнительные накладные расходы.

Например, если вы делаете сортировку с тремя способами, то на этапе рекомбинации вам нужно найти самый большой из 3 элементов для каждого элемента, для чего требуется 2 сравнения вместо 1, поэтому вы будете делать дважды многие сравнения в целом. Взамен вы уменьшаете глубину рекурсии на коэффициент ln (2) /ln (3) == 0.63, поэтому у вас на 37% меньше свопов, но 2 * 0,63 == 26% больше сравнений (и обращения к памяти). Будет ли это хорошо или плохо, зависит от того, что более дорого стоит на вашем оборудовании.

  

Я также видел много ссылок на 3-way quicksort. Когда это происходит быстрее?

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

  

Что используется на практике?

В наши дни вряд ли кто-либо программирует свои собственные алгоритмы сортировки; они используют один, предоставленный библиотекой. Например, API Java 7 фактически использует быстродействующую сортировку с двойным шарниром.

Люди, которые по какой-либо причине действительно программируют свой собственный алгоритм сортировки, склонны придерживаться простого варианта с двумя вариантами, поскольку меньший потенциал для ошибок превосходит 20% лучшую производительность в большинстве случаев. Помните: безусловно, самое важное улучшение производительности - это когда код переходит от «не работает» к «работающему».

ответил Michael Borgwardt 5 Maypm13 2013, 23:05:48
30

Асимптотически это не имеет значения. Например, бинарный поиск делает приблизительно сопоставление log 2 n, а тройной поиск составляет приблизительно log 3 n сравнений. Если вы знаете свои логарифмы, вы знаете, что log a x = log b x /log b a, поэтому двоичный поиск составляет всего около 1 /log 3 2 ≈ В 1,5 раза больше сравнений, чем тройной поиск. Это также причина, по которой никто никогда не указывает базу логарифма в больших Ох обозначение: это всегда постоянный фактор от логарифма в данной базе, независимо от того, что является базой. Таким образом, разделение проблемы на большее количество подмножеств не улучшает сложность времени и практически недостаточно, чтобы перевесить более сложную логику. Фактически, эта сложность может негативно сказаться на практической производительности, увеличивая давление в кеше или делая микро-оптимизацию менее неосуществимой.

С другой стороны, некоторые древовидные структуры данных используют высокий коэффициент ветвления (намного больше 3, часто 32 и более), хотя обычно по другим причинам. Это улучшает использование иерархии памяти: структуры данных, хранящиеся в ОЗУ, лучше используют кеш, структуры данных, хранящиеся на диске, требуют меньше чтения HDD-> ОЗУ.

ответил 5 Maypm13 2013, 22:40:56
4

Существуют алгоритмы поиска /сортировки, которые подразделяются не на два, а на N.

Простым примером является поиск по хэш-кодированию, который принимает время O (1).

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

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

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

Когда компьютер берет одно число и преобразует его в индекс в массив, он «учится» до логарифма базы 2 числа элементов в массиве и делает это в постоянное время. Например, если есть таблица переходов из 1024 записей, все более или менее одинаково вероятны, то перепрыгивая через эту таблицу, «узнает» 10 бит. Это основной трюк за кодированием хэша. Пример сортировки - это способ сортировки колоды карт. Есть 52 бункера, по одному на каждую карточку. Бросьте каждую карточку в свой ящик, а затем выкопайте их все. Не требуется разделение.

ответил Mike Dunlavey 5 Maypm13 2013, 23:58:49
1

Поскольку это вопрос об общем делении и победе, а не просто сортировка, я удивлен, что никто не поднял Мастер-теорема

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

алгоритм Карацубы для умножения использует трехстороннее разделение и завоевание для достижения рабочего времени O (3 n ^ log_2 3), которая превосходит O (n ^ 2) для обычного алгоритма умножения (n - число цифр в числах).

ответил Charles E. Grant 4 AM000000100000002131 2014, 10:42:21
-4

Из-за его двоичной природы компьютер очень эффективен при делении вещей на 2 и не столько на 3. Вы получаете деление в 3, сначала делясь на 2, а затем снова разделяйте одну из частей на 2. Поэтому, если вам нужно разделить на 2, чтобы получить 3-мя дивизиями, вы можете также разделить на 2.

ответил Pieter B 4 AM000000100000001931 2014, 10:42:19

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132