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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Это пример системы с непозиционным номером.

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

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

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

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

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

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

Ответ 9

Как указывали другие, сортировка сама по себе не быстрее, чем умножение на 5 значений. Однако это игнорирует остальную часть его решения. После преуменьшения 5-элементного сортировки он продолжает выполнять двоичный поиск по массиву из 4888 значений - по меньшей мере 12 сравнений, больше, чем требуется когда-либо!

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

Ему также не нужно было использовать простые числа. Если бы он просто закодировал значение каждой карты в 4 бита, ему понадобилось бы 20 бит для представления руки, давая диапазон от 0 до 2 ^ 20 = 1048576, примерно 1/100-й диапазон, полученный с использованием простых чисел, и достаточно маленький (хотя все еще страдают проблемы согласованности кеша) для создания таблицы поиска.

Конечно, еще более интересный вариант - взять 7 карт, например, в таких играх, как Texas Holdem, и найти лучшую 5-карточную комбинацию, которая может быть сделана из них.

Ответ 10

Умножение выполняется быстрее.

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

Ответ 11

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

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

О, и умножение выполняется быстрее, чем сортировка.