Что быстрее - сортировка или умножение небольшого массива элементов?

Question

Читая Cactus Kev's Poker Hand Evaluator , я заметил следующие утверждения:

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

Мне трудно поверить в это.

Кактус Кев представляет каждую карту как 4-байтовое целое число и оценивает руки, вызывая eval_5cards( int c1, int c2, int c3, int c4, int c5 ).Мы могли бы представлять карты как один байт, а покерную комбинацию - как 5-байтовый массив.Сортировка этого 5-байтового массива для получения уникальной руки должна быть довольно быстрой.Это быстрее, чем его подход?

Что если мы сохраним его представление (карты как 4-байтовые целые числа)?Может ли сортировка массива из 5 целых чисел быть быстрее, чем их умножение?Если нет, то какую низкоуровневую оптимизацию можно выполнить, чтобы ускорить сортировку небольшого числа элементов?

Спасибо!

Хорошие ответы всем;Я работаю над сравнением производительности сортировки и умножения, чтобы получить некоторую статистику производительности.

Answer 1

Конечно, это сильно зависит от процессора вашего компьютера, но обычный процессор Intel (например, Core 2 Duo) может умножить два 32-битных числа в течение 3 тактов процессора.Чтобы алгоритм сортировки побил это, алгоритм должен быть быстрее, чем 3 * 4 = 12 циклов ЦП, что является очень жестким ограничением.Ни один из стандартных алгоритмов сортировки не может сделать это менее чем за 12 циклов наверняка.Только сравнение двух чисел займет один цикл ЦП, условная ветвь результата также займет один цикл ЦП, и что бы вы ни делали, по крайней мере, один цикл ЦП (замена двух карт фактически займет не менее 4-х циклов ЦП).Таким образом, умножение выигрышей.

Конечно, это не учитывает задержку для извлечения значения карты из кэша 1-го или 2-го уровня или, возможно, даже из памяти;однако эта задержка относится к любому случаю, умножению и сортировке.

Answer 2

Без тестирования я сочувствую его аргументации. Вы можете сделать это в 4 умножениях, по сравнению с сортировкой, которая составляет n log n. В частности, для оптимальной сортировочной сети требуется 9 сравнений. Затем оценщик должен хотя бы посмотреть на каждый элемент отсортированного массива, что составляет еще 5 операций.

Answer 3

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

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

Теперь, если вас интересует теоретический вопрос, есть также решение, использующее сложение, а не умножение. Может быть только 4 карты с любым одним значением, так что вы также можете назначить значения 1,5,25, ..., 5 ^ 12 и добавить их. Это все еще вписывается в 32-битную арифметику. Существуют также другие решения на основе сложения с другими математическими свойствами. Но это действительно не имеет значения, потому что микрокодированная арифметика намного быстрее, чем все остальное, что делает компьютер.

Answer 4

5 элементов могут быть отсортированы с использованием оптимизированного дерева решений, что намного быстрее, чем с помощью универсального алгоритма сортировки.

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

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

Answer 5

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

Это пример непозиционной системы счисления.

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

Что если мы сохраним его представление (карты как 4-байтовые целые числа)?Может ли сортировка массива из 5 целых чисел быть быстрее, чем их умножение?

ОЗУ является внешним ресурсом и, как правило, медленнее, чем ЦП.Сортировка 5 целых всегда должна идти в оперативную память из-за операций подкачки.Добавьте сюда издержки самой функции сортировки, и умножение перестанет выглядеть так плохо.

Я думаю, что на современных процессорах целочисленное умножение почти всегда будет быстрее, чем сортировка, поскольку несколько умножений могут выполняться одновременно на разныхАЛУ, хотя есть только одна шина, соединяющая ЦП с ОЗУ.

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

5 целых чисел можно довольно быстро отсортировать, используя пузырьковая сортировка : qsort будет использовать больше памяти (для рекурсии), тогда как хорошо оптимизированная пузырьковая сортировка будет работать полностью из d-кеша.

Answer 6

Стоит упомянуть одну вещь: даже если инструкция умножения вашего процессора очень медленная (или вообще отсутствует), вы можете использовать таблицу поиска, чтобы ускорить процесс.

Answer 7

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

Answer 8

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

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

Answer 9

Пример готового Техасского Холдема с 7- и 5-карточным оценщиком можно найти здесь с документацией и более подробным объяснением здесь . Все отзывы приветствуются по адресу электронной почты, найденному в нем.

Вам не нужно сортировать, и, как правило, (~ 97% времени) уходит всего лишь с 6 добавлениями и парой сдвигов в битах при оценке 7-карточных комбинаций. Алгоритм использует сгенерированную справочную таблицу, которая занимает около 9 МБ ОЗУ и создается почти мгновенно. Дешевые. Все это делается внутри 32-битной системы, и «встроенный» оценщик из 7 карт хорош для оценки примерно 50 м случайно генерируемых раздач в секунду на моем ноутбуке.

Да, и умножение происходит быстрее, чем сортировка.

Answer 10

Умножение быстрее.

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