Стоит ли использовать сортировку по счету или любую другую альтернативу для сортировки частот по сложности символов?
У меня будет массив символов (256 символов ascii) и массив их частот (некоторые символы встречаются ноль раз). Было бы предпочтительнее использовать сложную систему подсчета для сортировки, и что будет занимать больше строк кода (код будет написано в сборке, тасм).
1 ответ
Сортировка подсчета должна быть превосходной, если ваши входные данные длинны (строки или буферы значительно длиннее 256).
Будет ли предпочтительнее использовать сложную подсчетную сортировку для сортировки?
Это, конечно, просто реализовать и имеет сложность O(1). Если большие входные данные возможны или распространены, подсчет сортировки очень хорош.
Однако, если небольшие входные данные являются общими, сортировка подсчета все еще должна тратить время на очистку всего массива счетчиков и повторное сканирование, и эта стоимость не уменьшается для меньших входных данных.
В зависимости от ЦП (например, быстрый набор настроек для очистки массива счетчиков), сортировка с 256 символами может быть полезна для входных данных от 64. Вы упоминаете TASM, так что вы конкретно говорите о x86 и, вероятно, x86-16. Современный x86 имеет очень быстрый memset, используя либо SSE хранилища, либо rep stosd, (256 или 512 байт (для 16-битных счетчиков) достаточно велико, чтобы использовать rep stos это не ужасная идея; накладные расходы при запуске в основном амортизируются, поэтому они близки к той же скорости, что и векторный цикл.)
Ниже 64 элементов я не уверен, что qsort или mergesort будут лучше. Ниже примерно 16 элементов (и в качестве базового варианта для qsort / merge-sort) вы, вероятно, захотите InsertionSort для производительности.
На современных x86 с SSSE3 (для pshufb) вы можете использовать SSE2 pminub / pmaxub в качестве компараторов в сети сортировки с байтовой гранулярностью (и да, эти инструкции работают в 16-битном режиме). См. Использование регистров SIMD и инструкций для включения параллелизма на уровне инструкций в алгоритмах сортировки для 32-разрядных элементов, а также быстрых байтов в регистре?,
Или используйте SIMD для частичной сортировки, чтобы InsertionSort было меньше свопов. Может быть, просто загрузите, pminub / pmaxub и сохраните, без особой перестановки.
и какое решение займет больше строк кода
В asm строки исходного кода - наименее полезная мера. (Не каждая строка собирается в инструкцию; некоторые являются метками или директивами).
Счетчик команд иногда важен, но некоторые инструкции медленнее других, и это имеет значение, как вы их упорядочиваете, и зависит ли ввод одной от вывода другой.
Если вам важна не производительность, а размер кода, вам нужно посмотреть количество байтов машинного кода. Инструкции x86 имеют переменную длину.
Если вы заботитесь только о размере кода, а не о производительности, вы можете подумать о сортировке по пузырькам или по принципу "прыжок вниз". (Без предварительной проверки, просто всегда зацикливайте максимальное время). Смотрите забавно-медленную сортировку JumpDown в 19-байтовом машинном коде x86-32. Имея всего несколько байтов кода, он может поменяться без использования xchg -с мем (неявный lock префикс). Более "нормальная" реализация типа "пузырьковая сортировка" выглядит следующим образом (TASM для 8-битных целых чисел).
Но вы также можете реализовать сортировку вставкой только с несколькими байтами кода, и в целом она работает хорошо (по сравнению с другими O(n^2) алгоритмами, такими как пузырь или выделение)