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

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

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

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

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

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