У меня будет массив символов (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, и сохранение, без особых перетасовок.
и какое решение займет больше строк кода
В ассемблере количество строк исходного кода является наименее полезной мерой. (Не каждая строка собирается в инструкцию; некоторые из них являются метками или директивами).
Количество инструкций иногда имеет значение, но некоторые инструкции медленнее других, и важно, как вы их упорядочиваете и зависит ли ввод одной от вывода другой.
Если вам важна не производительность, а размер кода, вам нужно посмотреть на количество байтов машинного кода. Инструкции x86 имеют переменную длину.
Если вас волнует только размер кода, а не производительность, вы можете использовать сортировку пузырьком или сортировку с переходом вниз. (Без ранней проверки просто всегда зацикливайте максимальное количество раз). См. весело-медленную сортировку JumpDown в 19-байтах машинного кода x86-32< /а>. Имея всего несколько дополнительных байтов кода, он мог обмениваться без использования xchg-with-mem (неявный префикс lock). Более «нормальная» реализация пузырьковой сортировки выглядит как это (TASM для 8-битных целых чисел).
Но вы также можете реализовать сортировку вставками, написав всего несколько байтов кода, и обычно она выполняет хорошо (по сравнению с другими алгоритмами O (n ^ 2), такими как пузырь или выбор)
person
Peter Cordes
schedule
20.01.2018
