Здравствуйте, romkol, Вы писали:
R>Например есть класс:
R>class myGen R>{ R> public int flt_no; R> public string reis_no;
R> public myGen(int pFlt_no, string pReis_no) R> { R> this.flt_no = pFlt_no; R> this.reis_no = pReis_no; R> } R>}
R>и есть лист: R>List<myGen> list = new List<myGen>();
R>Как реализовать две сортировки по int полю и по string?
1. Можно реализовать интерфейс IComparable классом myGen
2. Можно написать свой Comparer для myGen
Здравствуйте, Lloyd, Вы писали: L>Насколько я помню, вызов делегата не существенно дороже вызова виртуального метода.
Все познается в сравнении Поскольку данная тема (оптимизация алгоритмов при использовании generics) мне близка, то дам более развернутый ответ.
Я провел некоторые тесты для сравнения скорости работы Array.Sort (реализующего qsort) при разных способах вызова, а также ряда самописных реализаций.
Вот результаты:
Array.Sort with ComparerClass: 4640
Array.Sort with ComparerStruct: 4984
Array.Sort with delegate: 6687
QSort with ComparerClass: 3359
QSort with ComparerStruct: 3125
SmartQSort with LessComparerClass: 3015
SmartQSort with LessComparerStruct: 1719
Поясню о чем речь. Производится сортировка массива из 10 миллионов случайных чисел (массив всегда один и тот же для всех участников испытания). Алгоритм сортировки -- классический qsort с детерминированным выбором разделителя (выбирается всегда средний элемент).
Первый две строки соответствуют реализации, когда компаратор -- это класс или структура соответственно. Третья строка -- использование делегата. Виден проигрыш в производительности (он действительно не такой большой).
Но небольшой он лишь при использовании тупой реализации Array.Sort. Существует известный трюк, позволяющий избавиться от виртуальности вызова при использовании интерфейсов. А именно, пишем:
Как видно, теперь у нас два параметра-типа -- тип элемента массива и тип компаратора. Дело в том, что если в качестве компаратора передавать структуру, реализующую интерфейс, то начиная кажется со второй беты боксинга происходить не будет. Соответственно, мы получим обычный, неполиморфный вызов. Это и видно на представленной таблице -- ускорение 3125 против 4640.
Но и это еще не все. IComparer удобен конечно, но совершенно отвратителен с точки зрения производительности. Лучших результатов можно добиться с использованием двузначного предиката IsLess. Он проще вычисляется и открывает возможности JIT-у заинлайнить код компаратора (это лишь мои подозрения, впрочем).
Итак, смотрим последнюю строку -- 1719. Это почти в 2.7 раз быстрее, чем было изначально при использовании компаратора-класса с полиморфным вызовом!
При этом мы еще даже не пробовали улучшать сам алгоритм, который сейчас сделан непотимально -- на малых подотрезках нужно переходить на квадратичную сортировку.
Исходник теста:
using System;
using System.Collections.Generic;
class Test
{
interface ILessComparer<T>
{
bool IsLess(T lhs, T rhs);
}
static void QSort<T, Comparer>(T[] arr, int lo, int hi, Comparer cmp)
where Comparer : IComparer<T>
{
int i = lo;
int j = hi;
T sep = arr[(lo + hi) >> 1];
while (i <= j)
{
while (cmp.Compare(arr[i], sep) < 0)
i++;
while (cmp.Compare(sep, arr[j]) < 0)
j--;
if (i <= j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (lo < j)
QSort(arr, lo, j, cmp);
if (i < hi)
QSort(arr, i, hi, cmp);
}
static void QSort<T, Comparer>(T[] arr, Comparer cmp)
where Comparer : IComparer<T>
{
QSort(arr, 0, arr.Length - 1, cmp);
}
static void SmartQSort<T, Comparer>(T[] arr, int lo, int hi, Comparer cmp)
where Comparer : ILessComparer<T>
{
int i = lo;
int j = hi;
T sep = arr[(lo + hi) >> 1];
while (i <= j)
{
while (cmp.IsLess(arr[i], sep))
i++;
while (cmp.IsLess(sep, arr[j]))
j--;
if (i <= j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (lo < j)
SmartQSort(arr, lo, j, cmp);
if (i < hi)
SmartQSort(arr, i, hi, cmp);
}
static void SmartQSort<T, Comparer>(T[] arr, Comparer cmp)
where Comparer : ILessComparer<T>
{
SmartQSort(arr, 0, arr.Length - 1, cmp);
}
class ComparerClass : IComparer<int>
{
public int Compare(int a, int b)
{
return a < b ? -1 : (a > b ? +1 : 0);
}
}
struct ComparerStruct : IComparer<int>
{
public int Compare(int a, int b)
{
return a < b ? -1 : (a > b ? +1 : 0);
}
}
class LessComparerClass : ILessComparer<int>
{
public bool IsLess(int a, int b)
{
return a < b;
}
}
struct LessComparerStruct : ILessComparer<int>
{
public bool IsLess(int a, int b)
{
return a < b;
}
}
const int N = 10000000;
static int[] arr = new int[N];
delegate void Tester(int[] arr);
static void InvokeTest(Tester tester, string comment)
{
Random random = new Random();
for (int i = 0; i < arr.Length; i++)
arr[i] = random.Next();
int timer0 = Environment.TickCount;
tester(arr);
int timer1 = Environment.TickCount;
Console.WriteLine("{0}: {1}", comment, timer1 - timer0);
for (int i = 0; i < arr.Length - 1; i++)
if (arr[i] > arr[i+1])
throw new Exception("Oops..");
}
static void Main()
{
InvokeTest(
delegate (int[] arr)
{
Array.Sort(arr, new ComparerClass());
},
"Array.Sort with ComparerClass");
InvokeTest(
delegate (int[] arr)
{
Array.Sort(arr, new ComparerStruct());
},
"Array.Sort with ComparerStruct");
InvokeTest(
delegate (int[] arr)
{
Array.Sort(
arr,
delegate (int lhs, int rhs)
{
return lhs < rhs ? -1 : (lhs > rhs ? +1 : 0);
});
},
"Array.Sort with delegate");
InvokeTest(
delegate (int[] arr)
{
QSort(arr, new ComparerClass());
},
"QSort with ComparerClass");
InvokeTest(
delegate (int[] arr)
{
QSort(arr, new ComparerStruct());
},
"QSort with ComparerStruct");
InvokeTest(
delegate (int[] arr)
{
SmartQSort(arr, new LessComparerClass());
},
"SmartQSort with LessComparerClass");
InvokeTest(
delegate (int[] arr)
{
SmartQSort(arr, new LessComparerStruct());
},
"SmartQSort with LessComparerStruct");
}
}
Здравствуйте, Mab, Вы писали:
Mab>Но и это еще не все. IComparer удобен конечно, но совершенно отвратителен с точки зрения производительности. Лучших результатов можно добиться с использованием двузначного предиката IsLess. Он проще вычисляется и открывает возможности JIT-у заинлайнить код компаратора (это лишь мои подозрения, впрочем).
Добавлю еще про инлайнинг. Наличие или отсутствие его можно понять, добавив для метода атрибут MethodImpl(MethodImplOptions.NoInlining). Если это сделать, то становится ясно, что единственный из методов в приведенном примере, который инлайнится -- это лишь последний вариант теста. Что помешало заинлайнить вариант с трехзначным компаратором -- остается только догадываться. Возможно слишком большое ветвление.
Здравствуйте, Lloyd, Вы писали:
Mab>>Хороший способ, только сделует иметь в виду, что он медленнее, чем передача компаратора. L>Насколько я помню, вызов делегата не существенно дороже вызова виртуального метода.
В текущей реализации будет делегат будет вызываться через виртуальный метод. т.е. если есть желание избавиться от лишней косвенности, то лучше использовать компаратор
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Скажу пару слов в защиту делегатов... Не так уж они сильно медленее при условии использования нормального алгоритма сортировки. Просто то что использовано во фрэймворке не очень оптимальный вариант.
Добавил в твой тест еще один варинт SmartQSort использующий делегат. Результат получился следующим:
Array.Sort with ComparerClass: 4422
Array.Sort with ComparerStruct: 4891
Array.Sort with delegate: 6344
QSort with ComparerClass: 2922
QSort with ComparerStruct: 2578
SmartQSort with LessComparerClass: 2672
SmartQSort with LessComparerStruct: 1500
SmartQSort with IsLess<T> delegate: 3000
Код:
delegate bool IsLess<T>(T x, T y);
static void SmartQSort<T>(T[] arr, IsLess<T> isLess)
{
SmartQSort(arr, 0, arr.Length - 1, isLess);
}
static void SmartQSort<T>(T[] arr, int lo, int hi, IsLess<T> isLess)
{
int i = lo;
int j = hi;
T sep = arr[(lo + hi) >> 1];
while (i <= j)
{
while (isLess(arr[i], sep))
i++;
while (isLess(sep, arr[j]))
j--;
if (i <= j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (lo < j)
SmartQSort(arr, lo, j, isLess);
if (i < hi)
SmartQSort(arr, i, hi, isLess);
}
Конечно это заметно медленее чем заинлайленный вариант с компоратором на базе структуры, но все же он выглядит очень достойно на фоне обычного компоратора. К тому же удобство использования делегатов превешивает.
Ну, и надо понимать, что такие огромные объемы обрабатываются редко и уж так вылизывать все не стоит. Для большинства применений встроенной сортировки с делегатом за глаза хватит.
Плюс нужно понимать, что столь большие отрывы достигаются в следствии того, что сортируются целые числа. Они и сравниваются и перемещаются куда быстрее. На массиве объектов по идее разрыв должен стать меньше. Так что предостеригаю всех от поспешного переписывания кода на рукопашный. Делайте это только если сортировка действительно узкое место в программе.
... << RSDN@Home 1.2.0 alpha rev. 618>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Чтобы подвести данный тест к логическому завершению, приведу еще результаты сравнения с C++ (managed и native, версии 7.1 и 8.0 RC). Так можно понять, заодно, насколько вообще осмысленно говорить о том, чтобы использовать C# 2.0 для написаня критического по скорости кода, который до сих пор писался на C++.
Участники испытания:
Все те же, что и в пролшый раз, но со следующими добавлениями:
1) предложенный Владом вариант с делегатом и двузначным сравнением
2) почти дословно переведенный на C++ вариант SmartQSort
3) std::sort из STL (вне конкурса, т.к. реализует иной, более быстрый алгоритм)
4) SpecializedQSort на C# -- получен ручной подстановкой типа int и заменой вызова компаратора на прямое сравнение
Решаемая задача:
Детерминированный QSort без попыток оптимизации (нет tail recursion elimination, нет перехода на квадратичную сортировку на малых отрезках). Тестируются два варианта: сортировка 10 000 000 целых и сортировка 100 000 000 целых. В первом случае тест повторяется 10 раз и берется среднее. Исходные данные для всех испытуемых одинаковы -- детерминированные псевдослучайные числа, полученные с помощью линейного конгруэнтного метода (взят кусок реализции из VC CRT).
Выделены некоторые интересные, на мой ввзгляд, строки.
Кое-какие выводы:
1) Лучшая generic-реализация алгоритма на C# уступает лучшей native-реализации на C++ по скорости 15%.
2) При переходе от VC 7.1 к VC 8.0 RC наблюдается некоторый регресс в производительности (интересно было бы узнать, как дела в VC 8.0 Release).
3) Специализированная реализация алгоритма на C# уступает native-реализации на C++ по скорости 10%. Заметим, что при этом первая явлется полностью safe (например, включены array bounds checks).
4) Managed-реализация std::sort устуает native-релизации std::sort под VC7.1 примерно два раза. Странно, но факт. Возможно, порождается слишком лохматый IL-код, а возможно и недоработка JIT. Так или иначе, в FW 2.0 эти проблемы решены (хотя, см. п.2).
5) Использование в таком алгоритме делегата замедляет код примерно в 1.5-2 раза (чем оптимальнее реализация без делегата, тем выше коэффициент).
6) std::sort вместо SmartQSort выигрывает незначительно и лишь при очень больших размерах массива.
Здравствуйте, Аноним, Вы писали: А>Такие оптимизации в реальных проектах просто не нужны.
Думаю, стоило бы добавить ИМХО.
В тех проектах, где я участвую, скорость имеет значение. И заказчик готов платить, если вместо часа обсчет графа будет произведен за полчаса. А значит такой проект вполне реальный
Здравствуйте, <Аноним>, Вы писали:
А>Не занимайтесь ерундой. Это не будет акрутально ни в этой версии .NET FW, но в следующей. Такие оптимизации в реальных проектах просто не нужны.
Да? А я вот в редакторе кода для сортировки стилей вообще КаунтингСорт использовал, да еще специализированную версию (чтобы уж наверняка небыло никаких левых рассчетов).
И это не было причудой. Просто сортировка применяется в месте которое может быть вызвано очень много раз.
... << RSDN@Home 1.2.0 alpha rev. 618>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Поскольку данная тема (оптимизация алгоритмов при использовании generics) мне близка, то дам более развернутый ответ.
