为什么我的C#quicksort实现明显慢于List <T> .Sort

Question

我在C#中实现了一个quicksort版本,并执行了一些快速基准来与C#进行比较List<T>.Sort.我发现我的实现比库版本慢得多.我想知道为什么.这是一些粗略的基准数字.对于输入,我使用了一个随机(均匀)生成的整数列表,其中包含很少的重复元素.请注意,所有基准时间均为多次运行的平均值.

100,000 elements
My code         0.096 seconds
List<T>.Sort    0.011 seconds

1,000,000 elements
My code         1.10 seconds
List<T>.Sort    0.14 seconds

我的代码如下.以下是我尝试过的优化列表及其结果:

• 在线 - 我试图在线Swap和 我的ChoosePivotIndex功能内嵌,我看到了大约10%的改进.
• 枢轴选择 - 我知道我正在使用天真的枢轴选择方法.我也试过使用三个随机元素的中位数.这并没有带来太大的改善.我猜这是因为我用于基准测试的输入数据是均匀随机的.
• 并行性 - 我尝试并行进行递归分区调用.这似乎实际上增加了执行时间.
• 特殊外壳小输入 - 我已经尝试切换到小输入的插入排序(如List<T>.Sort声称做).这产生了大约20%的改善.

通过这些优化的组合,我已经能够将我的代码降低到

100,000 elements -   0.062 seconds
1,000,000 elements - 0.740 seconds 

这仍然比库Sort慢得多.在我的代码中有没有明显的解释性能差距,或者是从更小的调整中剩下的70-80%的差距？请注意,下面的代码是我未经优化的基础版本

public class Quicksorter<T> where T : IComparable<T>
{
    protected Random random;
    public Quicksorter()
    {
        random = new Random();
    }

    public void Sort(IList<T> items)
    {
        Partition(items, 0, items.Count-1);
    }

    private void Partition(IList<T> items, int startIndex, int endIndex)
    {
        if (startIndex >= endIndex)
            return;

        int pivotIndex = ChoosePivotIndex(items, startIndex, endIndex);
        T pivot = items[pivotIndex];

        // swap pivot and first element
        Swap(items, startIndex, pivotIndex);

        int partitionIndex = startIndex + 1;
        for (int frontierIndex = partitionIndex; frontierIndex <= endIndex; frontierIndex++)
        {
            if (items[frontierIndex].CompareTo(pivot) < 0)
            {
                Swap(items, frontierIndex, partitionIndex);
                partitionIndex++;
            }
        }
        // put pivot back
        items[startIndex] = items[partitionIndex-1];
        items[partitionIndex - 1] = pivot;

        // recursively sort left half
        Partition(items, startIndex, partitionIndex - 2);
        // recursively sort right half
        Partition(items, partitionIndex, endIndex);
    }

    protected virtual int ChoosePivotIndex(IList<T> items, int startIndex, int endIndex)
    {
        return random.Next(startIndex, endIndex);
    }

    private void Swap(IList<T> items, int aIndex, int bIndex)
    {
        T temp = items[aIndex];
        items[aIndex] = items[bIndex];
        items[bIndex] = temp;
    }
}

Answer 1

因为.NET Framework具有整数,字符串和其他内置类型的特殊情况排序方法.它们不会产生调用代表进行比较等的成本.如果您使用内置类型比较排序,那么库排序通常要快得多.