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