我应该使用计数排序还是任何其他替代方法来明智地对符号复杂度的频率进行排序

Should I use counting sort or any other alternative for sorting frequencies of symbols complexity wise

我将有一个符号数组(256 个 ascii 符号)和它们的频率数组(一些符号出现零次)。使用计数排序进行排序是否更复杂?代码行(代码将用汇编、tasm编写)。

如果您的输入很长(字符串或缓冲区明显长于 256),则计数排序应该非常好。


Would it be preferable complexity wise to use counting sort for sorting

实现起来当然很简单,而且复杂度为 O(1)。如果大输入是可能的或常见的,计数排序非常很好。

但是,如果小输入很常见,计数排序仍然需要花时间清除整个计数数组并再次扫描它,并且此成本不会随着较小的输入而降低。

根据 CPU,(例如,用于清除计数数组的快速内存集),使用 256 个符号进行计数排序可能适用于小至 64 个的输入。你提到了 TASM,所以你是在专门谈论关于 x86,可能还有 x86-16。现代 x86 具有非常快的 memset,使用 SSE 存储或 rep stosd。 (256 或 512 字节(对于 16 位计数器)足够大,因此使用 rep stos 并不是一个糟糕的主意;启动开销大部分被摊销,因此它接近与矢量循环相同的速度。)

低于64个元素,我不确定是qsort还是mergesort会做得更好。低于 16 个左右的元素(并且作为 qsort / merge-sort 的基本情况),您可能需要 InsertionSort 来提高性能。

在带有 SSSE3(对于 pshufb)的现代 x86 上,您可以在具有字节粒度的排序网络中使用 SSE2 pminub / pmaxub 作为比较器(是的,这些指令在 16 位模式下工作)。请参阅 使用 SIMD 寄存器和指令启用 排序算法中的指令级并行性 用于 32 位元素,以及 Fast in-register sort of bytes?.

或者使用 SIMD 进行部分排序,这样 InsertionSort 要做的交换就更少了。也许只是一些加载、pminub/pmaxub 和存储,没有太多或任何改组。

and what solution will take more code lines

在 asm 中,源代码行数是最没有用的衡量标准。 (不是每一行都汇编成一条指令;有些是标签或指令)。

指令数有时是相关的,但有些指令比其他指令慢,这很重要,你如何排序它们,一个输入是否取决于另一个的输出。

如果你不关心性能,而是关心代码大小,那么你需要看机器码的字节数。 x86 指令是可变长度的。

如果您关心代码大小而不关心性能,您可以考虑冒泡排序或下跳排序。 (没有提前检查,只是总是循环最大次数)。看到一个非常慢的 JumpDown sort in 19-bytes of x86-32 machine code. With only a few more bytes of code, it could swap without using xchg-with-mem (implicit lock prefix). A more "normal" bubble-sort implementation looks like this(8 位整数的 TASM)。

但您也可以只用几个字节的代码来实现 Insertion Sort,而且它通常表现良好(与其他 O(n^2) 算法(如冒泡或选择)相比)