c# - 数组按整数大小重新缩放整数

Question

我有一个整数数组，如果我按大小对它们进行排序，我想更改它们的位置值，目前我正在这样做:

var result = { 5,4,6,12,1,0 };

var order = new int[result.Length];

for (int i = 0; i < order.Length; i++)
{
    order[i] = i;
}
Array.Sort(result,order);

for (int i = 0; i < result.Length; i++)
{
    result[i] = i;
}

Array.Sort(order, result);
//output: result = { 3,2,4,5,1,0 }

但我不仅觉得这非常低效，而且根据 Visual Studio 的分析，这些类型占用了我大约 80% 的 CPU 时间。 我怎样才能让它更快？

Answer 1

对于初学者来说，根据输入大小选择正确的算法总是会带来好处。我不确定 Array.Sort 是否能做到这一点，很可能不会。

例如:如果处理 3-4 个元素，使用您自己的插入排序/硬编码 if 语句实现会更快。

其次，如果处理许多元素(~10000)，如果并行化 QuickSort，您可以轻松地将 Array.Sort 的性能提高 50%。不过，请参阅 ParallelExtensions，不要怀疑您一次要处理那么多元素。

问题最终归结为排序。使用 LINQ/OrderBy 的任何解决方案都不太可能击败整数数组上的 native Array.Sort，.NET 框架几乎没有巧妙的优化，可以将速度降低 2 倍。

为了将算法提高 2 倍，您只需要排序一次。

以下假设键的范围为 0..1000:

int[] _indexArray = new int[1001];

public void AbitBetterImplementation(int[] array)
{
   int[] copy = array.ToArray();

   for(var i = 0; i < array.Length; i++){
        var elem = array[i];
        _indexArray[elem] = i;
    }

   Array.Sort(copy);

   for(var i = 0; i < copy.Length; i++){
     var oldIndex = _indexArray[copy[i]];
     array[oldIndex] = i;
   }

}

快速基准测试:

Basic implementation Time Elapsed 183,2125 ms
A bit better implementation Time Elapsed 99,4912 ms