Наиболее эффективный способ сортировки массива и сохранения соответствующих исходных индексов.
Я хочу отсортировать массив целых чисел в C#, но также сохранить исходные индексы, соответствующие каждому элементу в массиве.
Моя первая мысль - преобразовать в объект Dictionary с ключом в качестве индекса и значением в качестве значения; а затем сортировать по значению с помощью linq. Я не думаю, что это работает очень хорошо. Какие еще решения возможны? Производительность является ключевым здесь.
Это кажется хорошим и простым решением; но это самый быстрый способ сделать это?
4 ответа
Если вы говорите о производительности во времени, вы можете скопировать массив во второй массив, отсортировать второй массив, а затем использовать два массива для отдельной функциональности. Это даст вам O(1) доступ к необходимым элементам.
Если вы говорите о производительности с точки зрения пространства, ваш подход с помощью словаря является лучшим, поскольку он будет содержать только 1 копию элементов, что приводит к O(n) пространство.
Как обычно, не оптимизируйте, пока не столкнетесь с проблемой производительности.
Для этого есть набор специальных встроенных функций .NET. Ищите перегрузки Array.Sort, которые принимают TKey[] аргумент. Существует несколько перегрузок, которые позволяют указать поддиапазон для сортировки или пользовательский 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Обратите внимание, что мы осторожны с возможными путаницами имен параметров. Мы передаем наши элементы как первый параметр (который называется "ключами"), а наш индекс (который больше похож на ключи) передается как второй параметр (называемый "элементы").
Использование довольно очевидно:
var rgs = new[] { "xyz", "a", "", "bb", "pdq" };
int[] idx = SortAndIndex(rgs); // rgs: { "", "a", "bb", "pdz", "xyz" }
// idx: { 2, 1, 3, 4, 0 }
Это касается случая ОП, когда вы действительно хотите, чтобы исходные данные были отсортированы. Если это то, что вам нужно, вы можете перестать читать здесь.
Но связанная с этим проблема заключается в том, что, если вам нужны такие же признаки сортировки, но вы не хотите изменять исходный массив? Как мы можем получить индексы сортировки без изменения порядка оригинальных предметов?
Лучший способ, который я нашел, - это использовать описанную выше процедуру для сортировки данных и получения индекса, но затем использовать этот индекс сортировки, чтобы восстановить отсортированные элементы в их первоначальном порядке.
Вероятно, есть несколько способов сделать это, но поскольку в этом вопросе упоминается эффективность, я могу показать некоторый код, который гарантированно выполнит минимальное количество обменов оригинальных элементов, используя только один 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 одновременно виден из другого места, промежуточные состояния будут видны.
В то время как для старой школы и нетипизированного Array.Sort(ключи массива, элементы массива) он лучше, чем LINQ для отслеживания индекса.
Начало реализации Array:
- C# Github исходный код для массива
- CPP Части реализации платформы
- Мэтт Уоррен - если вы действительно хотите понять Array
Array.Sort vs 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 |
Вы можете создать массив KeyValuePairs, а затем отсортировать по значению:
Array.Sort(array, (left, right) => left.Value.CompareTo(right.Value))
Но Array.Sort(Array, Array) тоже выглядит хорошо.