如果给定一个包含 n 个数字的数组，并且 m 是数组中最大的数字，我们如何为基数排序选择最有效的基数？
How can we choose the most efficient base for radix sort if we are given an array of n numbers and m is the largest number in the array?
如果给定一个n个数的数组，m是数组中最大的数，我们想用基数排序对这个数组进行排序，那么这个基数排序如何选择基数来实现时间和内存效率？数组的大小或者数组的最大数如何帮助我们选择基数
这是特定于处理器的，与内部缓存以及缓存的实现方式有关。在 X86 处理器的情况下，可能有 3 或 4 级缓存，通常这些是 8 路关联。
一些处理器也对紧密循环中代码的位置很敏感。在我的系统上，我发现相同代码的 运行 时间差异高达 40%，其中唯一的区别是我用来将它们对齐到偶数或奇数 16 字节边界的函数之间的 nop。
对于 32 位或 64 位无符号整数使用基数排序，基数 256 似乎是最好的。我 运行 对 3600 万伪 运行dom 64 位无符号整数进行排序的基准测试，使用的位域大小为 {8,8,8,8,8,8,8,8}（基数 256） 8次传球。我尝试使用 {11,11,11,11,10,10}（以 2048 或 1024 为基数）进行 6 次传递，但花费了两倍的时间（~2 秒对~1 秒），这是一个与缓存实现方式相关的问题在我的处理器上。我也试了{16,16,16,16}（base 65536），4遍，差不多用了2.5秒
可以考虑m相对较小的值。如果 m 是 <= 65536，那么基数排序 256 (2^8) 可以在 2 遍中完成。如果对整数进行排序并且 m 足够小，那么基于计数而不是实际对数据进行排序的单次计数排序会更快。
如果给定一个n个数的数组，m是数组中最大的数，我们想用基数排序对这个数组进行排序，那么这个基数排序如何选择基数来实现时间和内存效率？数组的大小或者数组的最大数如何帮助我们选择基数
这是特定于处理器的，与内部缓存以及缓存的实现方式有关。在 X86 处理器的情况下，可能有 3 或 4 级缓存，通常这些是 8 路关联。
一些处理器也对紧密循环中代码的位置很敏感。在我的系统上，我发现相同代码的 运行 时间差异高达 40%，其中唯一的区别是我用来将它们对齐到偶数或奇数 16 字节边界的函数之间的 nop。
对于 32 位或 64 位无符号整数使用基数排序，基数 256 似乎是最好的。我 运行 对 3600 万伪 运行dom 64 位无符号整数进行排序的基准测试，使用的位域大小为 {8,8,8,8,8,8,8,8}（基数 256） 8次传球。我尝试使用 {11,11,11,11,10,10}（以 2048 或 1024 为基数）进行 6 次传递，但花费了两倍的时间（~2 秒对~1 秒），这是一个与缓存实现方式相关的问题在我的处理器上。我也试了{16,16,16,16}（base 65536），4遍，差不多用了2.5秒
可以考虑m相对较小的值。如果 m 是 <= 65536，那么基数排序 256 (2^8) 可以在 2 遍中完成。如果对整数进行排序并且 m 足够小，那么基于计数而不是实际对数据进行排序的单次计数排序会更快。