对数组进行排序并保留相应原始索引的最有效方法

问题描述 投票：0回答：4

我想在 C# 中对整数数组进行排序，但同时保留与数组中每个元素相对应的原始索引。

我的第一个想法是转换为一个Dictionary对象，以key为索引，以value为值；然后使用 linq 按值排序。我认为这表现得不太好。还有哪些其他可能的解决方案？性能是这里的关键。

这似乎是一个很好且简单的解决方案；但这是最快的方法吗？

c# arrays sorting indices
4个回答
1
投票

如果您谈论时间性能，您可以将数组复制到第二个数组中，对第二个数组进行排序，然后使用两个数组实现单独的功能。这将使您能够

O(1)
访问所需的元素。

如果您谈论空间方面的性能，那么使用字典的方法是最好的，因为它只会保留元素的 1 个副本，从而产生 

O(n)
空间。

像往常一样，在真正遇到性能问题之前不要进行优化。

1
投票

虽然老式且无类型 Array.Sort（数组键，数组项）它比 LINQ 更好地跟踪索引。

进入数组实现：

  • C# Array 的 Github 源代码
  • CPP 平台实现部分
  • Matt Warren - 如果你真的想了解数组

Array.Sort 与 Linq

    [GlobalSetup]
    public virtual void Setup()
    {
        data = new T[N];
        indexes = new int[N];
        for (var cc = 0; cc < N; cc++)
        {
            data[cc] = GetRandom();
            indexes[cc] = cc;
        }
    }

    // Clone is nessesary as Array.Sort is done in place, ie the next call will be incorrectly given a pre-sorted list
    private T[] GetTestData() => (T[]) data.Clone();
    private int[] GetTestDataIndex() => (int[])indexes.Clone();

    [Benchmark]
    public virtual void Sort()
    {
        Array.Sort(GetTestData());
    }

    [Benchmark]
    public virtual void SortMaintainIndex()
    {
        Array.Sort(GetTestData(), GetTestDataIndex());
    }

    [Benchmark]
    public virtual void SortWithLinq()
    {
        int cc = 0;
        var withIndex = GetTestData()
                  .Select(x => (cc++, x))
                  .OrderBy(x => x.x)
                  .ToArray();
    }

就速度而言，没有可比性： 来源在这里https://gist.github.com/guylangston/cd9a0719d467f020eba46c6d0beb0584

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-3930K CPU 3.20GHz (Ivy Bridge), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=2.1.300
  [Host]     : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT


            Method |     N |        Mean |      Error |     StdDev |      Median |
------------------ |------ |------------:|-----------:|-----------:|------------:|
              Sort |  1000 |    35.85 us |  0.3234 us |  0.2700 us |    35.76 us |
 SortMaintainIndex |  1000 |    60.82 us |  0.2280 us |  0.1780 us |    60.76 us |
      SortWithLinq |  1000 |   172.26 us |  3.3984 us |  3.7773 us |   170.75 us |
              Sort | 10000 |   611.82 us | 13.8881 us | 18.0584 us |   602.77 us |
 SortMaintainIndex | 10000 |   889.25 us | 18.6503 us | 28.4810 us |   874.06 us |
      SortWithLinq | 10000 | 2,484.35 us | 57.8378 us | 54.1015 us | 2,476.72 us |
1
投票

在 .NET 中有一组特定的内置函数可以执行此操作。查找带有 TKey[] 参数的 

Array.Sort
重载。有多个重载可让您指定要排序的子范围或自定义 
IComparer<TKey>
。秘诀在于将原始数组作为 
keys
参数传递，并为 
0, 1, 2,... n-1
参数传递恒等数组 (
items
)。以下功能将为您完成所有工作：

/// sort array 'rg', returning the original index positions
static int[] SortAndIndex<T>(T[] rg)
{
    int i, c = rg.Length;
    var keys = new int[c];
    if (c > 1)
    {
        for (i = 0; i < c; i++)
            keys[i] = i;

        System.Array.Sort(rg, keys /*, ... */);
    }
    return keys;
}

再次，通过 

Array.Sort
，请注意我们要小心可能令人困惑的参数名称。我们将 items 作为第一个参数（称为“keys”）传递，并将 index-to-be （感觉更像键）作为第二个参数（称为“items”）传递。

用法非常不言自明：

var rgs = new[] { "xyz", "a", "", "bb", "pdq" };

int[] idx = SortAndIndex(rgs);  // rgs: { "",  "a", "bb", "pdz", "xyz" }
                                // idx: {  2,   1,    3,    4,     0   }

这涵盖了 OP 的情况，即您实际上希望原始数据最终进行排序。如果这就是您需要的，您可以在这里停止阅读。

但一个相关的问题是，如果您想要相同的排序索引，但您不想修改原始数组怎么办？我们如何在不更改原始项目顺序的情况下获得排序索引？

我发现做到这一点的最佳方法实际上是使用上面的过程对数据进行排序并获取索引，然后使用该排序索引将排序后的项目恢复到原始顺序。

可能有几种方法可以做到这一点，但由于这个问题提到了效率，我可以展示一些保证执行最少数量的原始项目交换的代码，同时仅使用单个 

T
存储元素，以便将项目恢复到原来的、未排序的顺序：

static unsafe void RevertSortIndex<T>(T[] rg, int[] keys)
{
    int i, k, c;
    int* rev = stackalloc int[c = rg.Length];
    for (i = 0; i < c; i++)
        rev[k = keys[i]] = k != i ? i : -1;

    do
        if ((i = rev[--c]) != c && i >= 0)
        {
            T t = rg[k = c];
            do
            {
                rg[k] = rg[i];
                rev[k] = -1;
            }
            while ((i = rev[k = i]) != c);

            rg[k] = t;
            rev[k] = -1;
        }
    while (c > 0);
}

为了仅使用单个 

T
元素进行交换，并且仅将每个元素移动到其最终位置一次，您必须按照由数据确定的非常特定的顺序进行交换。通过临时反向索引 (
rev
) 可以简化计算过程，该索引很容易从 
keys
创建。这里显示为 stackalloc，但如果您不想走这条路，您可以轻松地将其替换为托管 
int[]
分配。

无需过多讨论，任何排序索引都包含一个或多个从一个项目链接到另一个项目的循环（或循环“链”），并且遵循这些循环中的每一个都会为您提供可以恢复这些元素的最佳顺序回到原来的位置，同时只保留一个临时的

T
。这就是内部 
do...while
循环的作用。

外部

while...
循环需要扫描额外的循环，因为排序索引作为一个整体可能有多个独立的链，并且它们都需要被访问。重要的是，为了获得正确的结果，每个链必须只处理一次，不能再重复。因此，为了查明是否已处理任何给定的交换，其在 
rev
临时反向索引中的条目设置为 
-1
。这表明 
T
中相应的 
rg
元素已经被移动（作为前一个链的一部分）。

这是完整的使用示例：

var rgs = new[] { "xyz", "a", "", "bb", "pdq" };

int[] idx = SortAndIndex(rgs);

// rgs: { "",  "a", "bb", "pdz", "xyz" }
// idx: {  2,   1,    3,    4,     0   }

RevertSortIndex(rgs, idx);

// rgs: { "xyz", "a", "", "bb", "pdq"  }
// idx: {   2,   1,    3,    4,     0  }    (unchanged)

最后要注意的是，

SortAndIndex
与 
RevertSortIndex
的组合可能会导致 
rgs
最终未修改的外观，但这不应依赖于并发目的。如果 
rgs
同时从其他地方可见，则中间状态将可见。

0
投票

您可以创建一个 KeyValuePairs 数组，然后按值排序：

Array.Sort(array, (left, right) => left.Value.CompareTo(right.Value))

但是 Array.Sort(Array, Array) 看起来也不错。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.