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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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