Из-за усилия O (n ^ 2) и вектора 5000 элементов, стоит попробовать
- Преобразование вашего списка в простой двойной массив,
- Используйте некоторую специализированную библиотеку сортировки для сортировки массива
- Получить индексы порядка сортировки из сортировки и
- Упорядочить элементы вашего списка в соответствии с индексами
Это выполнимо, поскольку оно добавляет только O (2n) к усилию, следовательно, оно может быть пренебрежимо малым и окупается, если накладные расходы меньше, чем выигрыш из-за гораздо более быстрого сравнения.
если я найду время, я опубликую пример здесь.
@ Редактировать: я проверил это для демонстрации (и мой собственный интерес). Следующий тест сравнивает List.Sort () с подходом копирования-сортировки-копирования назад. Последнее было сделано с помощью ILNumerics быстрой сортировки. Обе версии запускались одна за другой по всей длине (означает: , а не с чередованием).
Отказ от ответственности: Это только для того, чтобы получить приблизительный обзор, если метод будет платить. На моем компьютере (Core i5, 2,4 ГГц, 3MB L3 Data Cache) он работает. Но точку безубыточности определить сложно. Кроме того, как всегда с такими быстрыми и грязными показателями производительности - целая куча влияний не учитывается. Наверное, самое важное: проблемы с кешем из-за нескольких копий, которые в реальной производственной среде могут не понадобиться.
код:
namespace ConsoleApplication1 {
unsafe class Program : ILNumerics.ILMath {
static void Main(string[] args) {
int numItems = 0, repet = 20000;
Stopwatch sw01 = new Stopwatch();
// results are collected in a dictionary:
// key: list length
// value: tuple with times taken by ILNumerics and List.Sort()
var results = new Dictionary<int, Tuple<float,float>>();
// the comparer used for List.Sort() see below
ItemComparer comparer = new ItemComparer();
// run test for copy-sort-copy back via ILNumerics
for (numItems = 500; numItems < 50000; numItems = (int)(numItems * 1.3)) {
Console.Write("\r measuring: {0}", numItems);
long ms = 0;
List<Item> a = makeData(numItems);
for (int i = 0; i < repet; i++) {
sw01.Restart();
List<Item> b1 = fastSort(a);
sw01.Stop();
ms += sw01.ElapsedMilliseconds;
}
results.Add(numItems,new Tuple<float,float>((float)ms / repet, 0f));
}
// run test using the straightforward approach, List.Sort(IComparer)
for (numItems = 500; numItems < 50000; numItems = (int)(numItems * 1.3)) {
Console.Write("\r measuring: {0}", numItems);
List<Item> a = makeData(numItems);
long ms = 0;
for (int i = 0; i < repet; i++) {
List<Item> copyList = new List<Item>(a);
sw01.Restart();
copyList.Sort(comparer);
sw01.Stop();
ms += sw01.ElapsedMilliseconds;
}
results[numItems] = new Tuple<float, float>(results[numItems].Item1, (float)ms / repet);
}
// Print results
Console.Clear();
foreach (var v in results)
Console.WriteLine("Length: {0} | ILNumerics/CLR: {1} / {2} ms", v.Key, v.Value.Item1, v.Value.Item2);
Console.ReadKey();
}
public class Item {
public double Value;
//... some else data fields
}
public class ItemComparer : Comparer<Item> {
public override int Compare(Item x, Item y) {
return (x.Value > y.Value) ? 1
: (x.Value == y.Value) ? 0 : -1;
}
}
public static List<Item> makeData(int n) {
List<Item> ret = new List<Item>(n);
using (ILScope.Enter()) {
ILArray<double> A = rand(1,n);
double[] values = A.GetArrayForRead();
for (int i = 0; i < n; i++) {
ret.Add(new Item() { Value = values[i] });
}
}
return ret;
}
public static List<Item> fastSort(List<Item> unsorted) {
//double [] values = unsorted.ConvertAll<double>(item => item.Value).ToArray();
//// maybe more efficient? safes O(n) run
//double[] values = new double[unsorted.Count];
//for (int i = 0; i < values.Length; i++) {
// values[i] = unsorted[i].Value;
//}
using (ILScope.Enter()) {
// convert incoming
ILArray<double> doubles = zeros(unsorted.Count);
double[] doublesArr = doubles.GetArrayForWrite();
for (int i = 0; i < doubles.Length; i++) {
doublesArr[i] = unsorted[i].Value;
}
// do fast sort
ILArray<double> indices = empty();
doubles = sort(doubles, Indices: indices);
// convert outgoing
List<Item> ret = new List<Item>(unsorted.Count);
foreach (double i in indices) ret.Add(unsorted[(int)i]);
return ret;
}
}
}
}
Это дало следующий вывод:
Length: 500 | ILNumerics / List.Sort: 0,00395 / 0,0001 ms
Length: 650 | ILNumerics / List.Sort: 0,0003 / 0,0001 ms
Length: 845 | ILNumerics / List.Sort: 0,00035 / 0,0003 ms
Length: 1098 | ILNumerics / List.Sort: 0,0003 / 0,00015 ms
Length: 1427 | ILNumerics / List.Sort: 0,0005 / 0,00055 ms
Length: 1855 | ILNumerics / List.Sort: 0,00195 / 0,00055 ms
Length: 2000 | ILNumerics / List.Sort: 0,00535 / 0,0006 ms
Length: 2600 | ILNumerics / List.Sort: 0,0037 / 0,00295 ms
Length: 3380 | ILNumerics / List.Sort: 0,00515 / 0,0364 ms
Length: 4394 | ILNumerics / List.Sort: 0,0051 / 1,0015 ms
Length: 4500 | ILNumerics / List.Sort: 0,1136 / 1,0057 ms
Length: 5850 | ILNumerics / List.Sort: 0,2871 / 1,0047 ms
Length: 7605 | ILNumerics / List.Sort: 0,5015 / 2,0049 ms
Length: 9886 | ILNumerics / List.Sort: 1,1164 / 2,0793 ms
Length: 12851 | ILNumerics / List.Sort: 1,4236 / 3,6335 ms
Length: 16706 | ILNumerics / List.Sort: 1,6202 / 4,9506 ms
Length: 21717 | ILNumerics / List.Sort: 2,3417 / 6,1871 ms
Length: 28232 | ILNumerics / List.Sort: 3,4038 / 8,7888 ms
Length: 36701 | ILNumerics / List.Sort: 4,4406 / 12,1311 ms
Length: 47711 | ILNumerics / List.Sort: 5,7884 / 16,1002 ms
Здесь, по-видимому, безубыточность составляет около 4000 элементов. Большие массивы всегда быстрее сортируются методом копирование-сортировка-копирование примерно в 3 раза. Я полагаю, что для меньших массивов он может платить - а может и нет. Числа, собранные здесь, ненадежны. Я предполагаю, что для небольших списков время сортировки маскируется некоторыми другими проблемами, такими как управление памятью (GC) и так далее. Может быть, кто-то здесь получил больше идей, как это объяснить.
Также странным является скачок во времени выполнения для List.Sort при длине 4000 элементов. Не знаю, переключится ли List.Sort здесь на другую (хуже) реализацию?
Что касается вопроса, то, похоже, стоит скопировать элементы, отсортировать их в виде простого массива и при необходимости скопировать их обратно. В зависимости от вашего оборудования, безубыточность может сместиться вверх или вниз. Так же, как всегда: профиль вашей реализации!