数组按整数的大小重新缩放整数

本文关键字：整数 缩放 新缩放 数组 | 更新日期: 2023-09-27 18:29:43

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

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时间。我怎样才能让它更快？

数组按整数的大小重新缩放整数

首先，根据输入大小选择正确的算法总是会带来好处。我不确定Array.Sort是否会这样做，很可能不会。

例如：如果处理3-4个元素，则使用自己的insertion sort / hardcoded if statements实现会更快。

其次，如果处理许多元素（约10000），如果并行化QuickSort，则可以轻松地将Array.Sort的性能提高50%。不过，请参阅ParallelExtensions，不要以为您同时处理了那么多元素。

问题最终归结为分类。任何使用LINQ/OrderBy的解决方案都不太可能在整数数组上击败本机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

这个怎么样：

var order = Enumerable.Range( 0, results.Length ).OrderBy( i => results[i] ).ToArray();

这应该会给你一个数组，这样就可以在不修改结果数组的情况下按顺序打印results数组：

foreach( var index in order ) 
{
    Console.WriteLine( results[index] );
}

编辑：正如所指出的那样，以上内容并不能提供期望的结果。然而，它确实提供了结果的"逆"，因此很容易获得并正确映射：

var order = Enumerable.Range( 0, results.Length ).OrderBy( i => results[i] ).ToArray();
var indices = new int[results.Length];
for( int i = 0; i < results.Length; ++i )
{
    indices[order[i]] = i;
}
// The indices array now holds the index that each item in the results array 
// would end up at if sorted

您可以计算每个项目存在多少个较低的值：

int[] r = result.Select(n => result.Count(x => x < n)).ToArray();

或：

int[] r = new int[result.Length];
for (var i = 0; i < result.Length; i++) {
  int n = result[i];
  for (var j = 0; j < result.Length; j++) {
    if (result[j] < n) r[i]++;
  }
}

这实际上是效率更高还是更低取决于有多少数据。这是一个O（n*n）解决方案，所以如果数组很长，效率就没有那么高。

这是一个用LINQ编写的简单解决方案：

var input = new int[] { 5, 4, 6, 12, 1, 0 };
var result = from n in input
             let order = input.OrderBy(k => k).ToList()
             select order.IndexOf(n);

请注意，实际上，重复项将具有相同的结果索引。我不知道它是否符合您的需求（但我怀疑在输入序列中不可能重复）。

This只对数组进行一次排序+它在集合中循环（仅）3次。如果藏品很大，这一点很重要。如果多个值具有相同的值，则它知道原始位置。

var items = new[] { 5, 4, 6, 12, 1, 0 };
var combinations = items.Select((value, originalindex) => new { value, originalindex });
var sortedCombination = combinations.OrderBy(c => c.value);
var sortedCombinationWithIndex =
    sortedCombination.Select((combination, sortedIndex) => new {combination, sortedIndex});
var result = new int[items.Length]; 
foreach (var item in sortedCombinationWithIndex)
{
    result[item.combination.originalindex] = item.sortedIndex;
}

在可以简单调用的方法中重写：

public int[] SortIndexes<T>(T[] source) where T : IComparable<T>
{
    var combinations = source.Select((value, originalindex) => new { value, originalindex });
    var sortedCombination = combinations.OrderBy(c => c.value);
    var sortedCombinationWithIndex =
        sortedCombination.Select((combination, sortedIndex) => new { combination, sortedIndex });
    var result = new int[source.Length];
    foreach (var item in sortedCombinationWithIndex)
    {
        result[item.combination.originalindex] = item.sortedIndex;
    }
    return result;
}
相关文章：