基数排序算法可能对不同顺序的数据有不同的运行-时间？

Question

我正在尝试实现基数排序算法。我正在使用 linked 列表来存储要排序的元素，然后我将每个元素扔到它的桶中。这个桶只是一个指针，它将 link 属于它的桶的元素列表。

我正在测试区间 [0, 1000000] 中的 10.000.000 和 100.000.000 个整数。此数字可以是新月形、渐变形和随机顺序。

100.000.000 个数字的运行时间大约为 20 秒。但是对于具有随机顺序的相同数量的元素运行-时间约为 110 秒。

据我了解，此算法对任何质量具有相同的复杂性要排序的数据。

有人知道为什么会这样吗？

这是我的代码：

    void radix(Number** numbers)
    {
        unsigned int i, k, e = 1;
        Number* bucket[10];
        Number* tail[10];
        Number* index;

        for(k = 0; k < 7; k++, e *= 10)
        {
            for(i = 0; i < 10; i++) bucket[i] = tail[i] = NULL;

            index = *numbers;
            while(index != NULL)
            {
                i = (index->value / e) % 10;

                if(tail[i] == NULL)
                    bucket[i] = index;
                else
                    tail[i]->next = index;

                tail[i] = index;
                index = index->next; 
            }

            for(i = 0; i < 10; i++)
            {
                if(tail[i] != NULL)
                {
                    *numbers = bucket[i];
                    index = tail[i];
                    for(i++; i < 10; i++)
                    {
                        if(tail[i] != NULL)
                        {
                            index->next = bucket[i];
                            index = tail[i];
                        }
                    }
                }
            }

            index->next = NULL;
        }
    }

其中 Number 是：

typedef struct number
{
    unsigned int value;
    struct number* next;
} Number;

Answer 1

答案可能与内存访问和引用位置有关。

Ascending/descending order 有一个规则模式，它可能具有更大的时间局部性，与其说是关于 buckets，不如说是关于链表节点用于数字的方式（特别是如果它们不连续）。

例如，如果我们输入：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

我们从 bucket 0 循环到 bucket 9，然后回到 bucket 0。当我们回到 bucket 0 时，我们正在访问最近访问过的 number 节点（仅 9 次迭代前) 可能会被缓存到更快、更小的内存中。

如果我们使用随机排序，谁知道我们什么时候会回到桶 0？因此，在我们返回到用于任何给定存储桶头部数字的内存之前，我们很有可能将数据从 DRAM 移动到缓存。结果可以转化为更多这样的前 number 节点被从缓存中逐出，当我们回到这样的桶时，更多的缓存未命中。

对于不规则的排序，分支预测错误也可能会消耗一些时间。分析应该有助于缩小原因。

如果您确实存在内存瓶颈，可以尝试的一种方法是将您的存储桶变成，比如说，您可以将数字深度复制到其中的展开列表。这将使您不再访问以前插入的数字的内存，这些数字可能已经插入了很多次迭代（由于随机排序，一个潜在的大变量）。这样我们就开始恢复一些时间局部性（如果数字是连续分配的，可能还有空间局部性），否则我们将失去这种链表表示形式。然后它变成了重用桶的连续内存（只有 10 个），而不是桶中的元素，其间有可变的步幅。我们还通过展开表示在桶内获得空间局部性。

But if is the same data, just with different order, this can affect a lot ? 20 to 110 seconds is too much for the same data.

内存效率可以产生数量级的差异。 http://lwn.net/Articles/250967/

我不是这方面的专家（更多的是 "profile it and try to optimize based on guidelines" 类型），但根据我过去从内存优化中获得的结果，我通常会在效果方面将它们放在一起通过算法优化。例外情况是复杂性差异很大（例如：线性对数与二次方），但即使线性对数算法也可以非常可行地击败具有非常大输入的线性算法，如果前者对缓存更友好的话。

基数排序算法可能对不同顺序的数据有不同的运行-时间？

The radix sort algorithm may have different run-time for datas with different order?

c

sorting

algorithm

radix-sort