tguev 28 июл 2013 в 20:00

Сортировка в .NET

16 мин

72K

.NET * C# *

+62

Комментарии 37

bachin 28 июл 2013 в 21:18

Пожалуйста, уточните — в некоторых местах у вас «наивный алгоритм», а в других «нативный алгоритм»
Это опечатка или американизмы?

VenomBlood 28 июл 2013 в 21:33

Я полагаю это разные термины. Нативный имеется ввиду «родной», такое часто применяется когда идет речь о прямом использовании функционала нижележащей среды. Т.е. реализованная непосредственно в CLR ([MethodImpl(MethodImplOptions.InternalCall)]) функциональность для BLC может называться нативной.
Наивная реализация — это фактически синоним слова «топорная реализация», т.е. без учета каких-либо тонкостей, которые ценой небольших модификаций базового описания алгоритма дадут какой-либо выигрыш.

tangro 28 июл 2013 в 21:59

А я на стороне Java и тимсорта. Понятно, что ими движет: вот было у нас 100 файликов в папке, отсортированных по имени, юзер бросил еще два и снова попросил посортировать. 100 из 102 файлов уже расположены верно относительно друг друга, надо лишь поставить 2 новых на правильные места, тимсорт это сделает лучше дотнетовской сортировки. Таких примеров много: новые фотки на фотоаппарате, новые поступления данных в базу, консолидация данных из нескольких идентичных источников. Дотнет же предполагает, что мир больше хаотичен и случаен, мне в это меньше верится.

vics001 28 июл 2013 в 22:30

Немного странные примеры, так как в этом случае алгоритм бинарной вставки все равно быстрее TimSort.
Из моего опыта часто встречаются кластеры схожих данных, к примеру вы достаете данные из N страниц памяти или читаете из N мест, как правило данные в каждой странице близки по значения (одинаково удаленны от центра сортировки), а следовательно получается много схожих подпоследовательностей, так скажем подгрупп со схожими свойствами относительно других элементов. И тут TimSort быстрее? (затрудняюсь ответить)

tangro 29 июл 2013 в 09:11

Было бы интересно посмотреть на бенчмарки при реализации алгоритмов на одном языке. А то «на глазок» сравнивать — как-то не научно.

Athari 28 июл 2013 в 22:50

Было бы интересно узнать ещё и про реализацию сортировки в LINQ. Написать цепочку из OrderBy и ThenBy приятнее, чем реализовать метод для сравнения вручную: меньше кода, лучше читается, меньше шансов ошибиться в логике и т.п. Соответственно, интересно, насколько LINQ проигрывает по скорости сортировке массива.

Nagg 29 июл 2013 в 06:27

В OrderBy используется устойчивый алгоритм в отличие от Array.Sort. А вообще если речь идет о LINQ to EF\NH\SQL то там вообще запрос в бд :-)

GrigoryPerepechko 30 июл 2013 в 09:23

Посмотрите рефлектором EnumerableSorter<T>. Там чистый QuickSort, вроде бы ни во что не переходящий.

Roman_Pekhov 29 июл 2013 в 00:39

В примерах кода SorterGenericArray и SorterObjectArray закрывающих фигурных скобок больше, чем открывающих. И бросается в глаза do без while.

Стану читать дальше, если сделаете везде одинаковые отступы. В одном и том же куске кода встречается 1, 2 и 4 пробела. Крыша едет, глаза слезятся.

Roman_Pekhov 30 июл 2013 в 12:22

Стало читабельнее, спасибо. Ещё бы так же исправить раскардаш отступов в «Нативный QuickSort».

chersanya 29 июл 2013 в 02:08

Сильно деградирует по скорости до O(n²) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, выбирая опорный элемент случайно, а не фиксированным образом;

Не обязательно случайно, можно сделать быструю сортировку детерминировано за O(n log n).

А с TimSort сравнения не делали? Насколько я знаю, в питоне он используется достаточно давно, и менять не собираются.

Mrrl 29 июл 2013 в 02:38

Не обязательно случайно, можно сделать быструю сортировку детерминировано за O(n log n).

Не можете сказать идею такой сортировки или дать ссылку? Или это делается через какой-нибудь поиск медианы за O(N)? Тогда константа должна быть просто ужасной.

mexanism 29 июл 2013 в 04:24

На графике секунды? .NET 4.5 Миллионный массив чего-нибудь за 10 минут сортируется?

Mrrl 29 июл 2013 в 04:35

Наверное, это миллисекунды.

tguev 29 июл 2013 в 05:48

Это миллисекунды.

asm0dey 29 июл 2013 в 07:36

Да запросто — главное в критерий сравнения добавить аналог Thread.sleep().

nicolausYes 29 июл 2013 в 07:31

К слову, замечу, что в C++, в реализации std::sort от microsoft используется тот же подход – использование insertion sort, heapsort, quick sort в зависимости от условий.

std::sort в VS2010

template<class _RanIt,
	class _Diff,
	class _Pr> inline
	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
	{	// order [_First, _Last), using _Pred
	_Diff _Count;
	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
		{	// divide and conquer by quicksort
		_STD pair<_RanIt, _RanIt> _Mid =
			_Unguarded_partition(_First, _Last, _Pred);
		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions

		if (_Mid.first - _First < _Last - _Mid.second)
			{	// loop on second half
			_Sort(_First, _Mid.first, _Ideal, _Pred);
			_First = _Mid.second;
			}
		else
			{	// loop on first half
			_Sort(_Mid.second, _Last, _Ideal, _Pred);
			_Last = _Mid.first;
			}
		}

	if (_ISORT_MAX < _Count)
		{	// heap sort if too many divisions
		_STD make_heap(_First, _Last, _Pred);
		_STD sort_heap(_First, _Last, _Pred);
		}
	else if (1 < _Count)
		_Insertion_sort(_First, _Last, _Pred);	// small
	}

Интересно, что при малых выборках и использовании Insertion sort, вы получите устойчивую сортировку, а на больших данных – уже нет.

К слову, проводил недавно эксперименты с разными сортировками, писал руками и замерял время сортировки на разных объемах данных (ссылка на github). Что интересно, до 1 000 000 значений алгоритмы с STL работают быстрее, при бОльших объемах – начинают проигрывать.

Полученные результаты на Google Docs
Еще раз ссылка на Github – исходники, графики, описания

Полученные результаты картинкой

Попсовый график сравнения лучших алгоритмов на больших объемах данных

Mrrl 31 июл 2013 в 15:51

Странно, что у вас MergeSort работает так медленно.
Я погонял эти тесты, подставив недефолтную функцию сравнения ( bool cmp(int x,int y){ return (x^13)<(y^13); } ) — получились такие результаты:

64 bit, Intel i7

5000000:
MergeSort = 492.8ms
MergeSortInPlace = 670.9ms
MergeSortBottomUp = 536.2ms
QuickSort = 615.5ms
std::sort = 666.4ms
std::stable_sort = 628.6ms

10000000:
MergeSort = 1025.2ms
MergeSortInPlace = 1425.2ms
MergeSortBottomUp = 1117.6ms
QuickSort = 1269.2ms
std::sort = 1397.8ms
std::stable_sort = 1323.8ms

50000000:
MergeSort = 5318ms
MergeSortInPlace = 8034.67ms
MergeSortBottomUp = 6154ms
QuickSort = 7048ms
std::sort = 7671.33ms
std::stable_sort = 7189.33ms

100000000:
MergeSort = 11444ms
MergeSortInPlace = 17040ms
MergeSortBottomUp = 13166ms
QuickSort = 14647ms
std::sort = 15944ms
std::stable_sort = 14953ms

200000000:
MergeSort = 23447ms
MergeSortInPlace = 35907ms
MergeSortBottomUp = 27430ms
QuickSort = 30298ms
std::sort = 33544ms
std::stable_sort = 31094ms

MergeSortInPlace — экспериментальная сортировка с дополнительной памятью O(1) и гарантированным временем O(N*log(N)). Работает чуть хуже, чем мой прошлый опыт (проигрывает quicksort'у 10-20%), зато код намного более простой…

nicolausYes 31 июл 2013 в 18:35

Скорее всего из-за того, что память медленная, там на гитхабе указаны характеристики машины — RAM 8Gb, 1033. На домашней машине, где память быстрее, MergeSort работает тоже довольно таки значительно быстрее, но не скажу на сколько точно. Может на процентов 5-10.

Mrrl 31 июл 2013 в 18:43

Я немного доработал код, теперь он (по моим тестам) на уровне остальных MergeSort (хотя память по-прежнему O(1)).

www.dropbox.com/s/cag6ao6xsyccnr8/MergeInPlaceSort.h

nicolausYes 1 авг 2013 в 11:33

Оу, спасибо, я посмотрю.

GrigoryPerepechko 30 июл 2013 в 09:25

Всегда расстраивался что в .NET FW не зашили несколько реализаций сортировок которые можно было бы выбирать при сортировке. Зачастую разработчик представляет природу своих данных и смог бы подобрать оптимальный алгоритм.

Athari 30 июл 2013 в 09:34

Никто не запрещает реализовать (или скопипастить) подходящий алгоритм сортировки, если вам так критичны 10% производительности в операции, которая занимает 5% времени работы программы. :)

GrigoryPerepechko 30 июл 2013 в 09:42

Да что вы говорите? А я всё ждал такого бесценного совета.

Суть не в том что я не могу это сделать. Суть в том что в каждом проекте видишь эти ваши «копипасты», и тошнить начинает от этих через зад прилепленных реализаций.
Моя идея была в том что MS написав такой гигансткий фреймворк где уже есть некоторые алгоритмы сортировки, могли бы управление алгоритмом вытащить наружу для тех кто понимает какой алгоритм в текущей задаче ему даст эти 10%.

А что касается 5% времени работы программы — если вы занимаетесь формочками и CRUD'ом — это ваши личные проблемы. Я уверен что очень многие разработчики тут пишут приложения в которых есть обработка больших объемов данных и их пользователям пригодились бы те самые 10% производителности.

Athari 30 июл 2013 в 10:04

Мне ещё не доводилось видеть на коленке реализованных алгоритмов сортировки. :) Вот сколько EnumerableExtensions и иже с ними повидал, чего только там не встречал, а сортировок — не было.

Вы можете назвать задачу, которой вы занимаетесь, для которой критична сортировка огромных массивов? Массивы должны быть частично отсортированными, и сортировка должна производиться в управляемом коде.

могли бы управление алгоритмом вытащить наружу для тех кто понимает какой алгоритм в текущей задаче ему даст эти 10%

Э… чо? Сделать настройку, которая меняет реализацию Array.Sort во всём приложении что ли?

Я уверен что очень многие разработчики тут пишут приложения в которых есть обработка больших объемов данных и их пользователям пригодились бы те самые 10% производителности.

Большие объёмы данных — это научнота, датамайнинг и иже. Посмотрим правде в глаза: большинство пользователей фреймворка этим не интересуется. Даже если это вам надо, это не повод запихивать в фреймворк вещи, которые нужны 2% людей.

Вообще, пихать всё в фреймворк — не самая хорошая идея. И так эта дура 50 метров весит, а после установки — полтора-два гига (посмотрите на досуге размер C:\Windows\Assembly и C:\Windows\Microsoft.NET).

Mrrl 30 июл 2013 в 20:36

Не совсем понятно, что вы предлагаете разработчику в ситуации, когда ему полезны «10% производительности» и у него есть алгоритм той самой сортировки, который даёт эти самые 10%, но библиотечным не является? Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке? Или наступить на горло собственной песне, взять библиотечную реализацию и сказать пользователям «покупайте железо помощнее»?

Athari 31 июл 2013 в 19:35

Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке?

Пишем extension method. Вместо array.Sort() имеем array.SuperSort(). Да даже если банальный статический метод в двух местах будет вызываться вместо Sort — что же, от этого тошнить должно?

Mrrl 1 авг 2013 в 00:41

Пишем extension method. Вместо array.Sort() имеем array.SuperSort().

Пожалуй, я так и сделаю. Спасибо за идею! Жаль только, что универсальная сортировка у меня узким местом пока не является :(

Mrrl 30 июл 2013 в 15:03

5% времени работы программы могут быть критичными, если они составляют время между моментом, когда пользователь нажал кнопку и моментом, когда он увидел результат — чтобы еще что-то сделать, запустить долгий процесс и пойти пить кофе. 15 секунд он потерпит, а если это будет 20 секунд — отвлечется на какой-нибудь фейсбук, а потом будет говорить, что программа строила preview полчаса…

Mrrl 30 июл 2013 в 14:59

Может быть, дело в том, что когда эффективности Quicksort не хватает, то оптимальный алгоритм будет слишком специфичным? И шансов, что он окажется среди ещё десятка универсальных алгоритмов, которые могли бы предложить разработчики, будет не так уж много? Ведь кроме предполагаемого порядка элементов оптимальный алгоритм будет учитывать ещё и их вероятное распределение, кластеризацию, особенности функции сравнения. Например «сначала пустим поразрядную сортировку по этому полю, потом quicksort по этому сравнению на полученные фрагменты, а потом сольём их по этой быстро вычисляемой функции сравнения». Какие шансы, что такое удастся найти хоть в какой-нибудь библиотеке?
А меня в .NET больше расстраивает, что у них нет функции сортировки фрагмента массива по заданной функции сравнения. Для всего массива есть, а для фрагмента нет. Приходится в этом месте (если фрагмент небольшой) писать какой-нибудь пузырёк. Открыли бы они хотя бы создание компаратора по лямбда-выражению — не пришлось бы тратить время. Но нет, 10 строчек, а класс internal…

tguev 30 июл 2013 в 16:43

Есть ведь метод который сортирует элементы в диапазоне элементов массива, используя заданный компоратор
public static void Sort(T[] array, int index, int length, IComparer comparer).
Или вы имели ввиду метод принимающий Comparison?

Mrrl 30 июл 2013 в 16:48

Да, Comparison (обычно это лямбда-выражение, использующее текущее окружение). Сами они делают из него компаратор. Но нам этого класса не дают.

tguev 30 июл 2013 в 16:50

Да знаю. Сам пользуюсь часто перегрузкой с делегатом) Согласен, что было бы удобнее если бы такой метод был бы, так как с компоратором не очень удобно.

Mrrl 30 июл 2013 в 16:57

Может быть, просто украсть у них этот класс и пользоваться:

        internal sealed class FunctorComparer<T> : IComparer<T> { 
            Comparison<T> comparison;
 
            public FunctorComparer(Comparison<T> comparison) {
                this.comparison = comparison;
            }
 
            public int Compare(T x, T y) {
                return comparison(x, y); 
            } 
        }

tguev 30 июл 2013 в 16:59

Можно!!!)))) Но лучше бы они добавили реализацию, при которой нам не понадобиться красть)))))

PsyHaSTe 9 дек 2015 в 11:51

Можно написать свою реализацию генерации компаратора, иногда довольно удобно. Лично я для себя остановился на таком:

[TestMethod]
public void TestComparerFull4()
{
    Tuple<string, int> a = new Tuple<string, int>("1", 2), b = new Tuple<string, int>("2", 4);
    Tuple<string, int> x = new Tuple<string, int>("2", 2), y = new Tuple<string, int>("2", 4);
    var comparer = CustomComparer<Tuple<string, int>>.New(t => t.Item1).Add(t => t.Item2).CreateDelegate();
    var comparerNeg = CustomComparer<Tuple<string, int>>.NewNeg(t => t.Item1).Add(t => -t.Item2).CreateDelegate();

    Assert.AreEqual(-1, comparer(a, b));
    Assert.AreEqual(1, comparer(b, a));

    Assert.AreEqual(1, comparerNeg(x, y));
    Assert.AreEqual(-1, comparerNeg(y, x));
}

Сами делегаты строятся на экспрешенах. В итоге получается достаточно удобно.
Сама реализация на гитхабе: тыц и тыц. Планирую потом перенести в другое отдельное решение, может кому пригодится. Но вообще довольно юзабельным должно быть. Ну и конечно каждый под себя может переделать как ему больше нравится.

PsyHaSTe 26 фев 2016 в 13:21

Кстати, лучше все же смотреть на referencesource, ибо декомпилятор не показывает комментарии и директивы условной компиляции, которые зачастую весьма интересны (и магическое число 32 тоже объясняется):

internal void Sort(int left, int length)
{
#if FEATURE_CORECLR
// Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade 
// to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka 
// IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.

    IntrospectiveSort(left, length);
#else
    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
    {
        IntrospectiveSort(left, length);
    }
    else
    {
        DepthLimitedQuickSort(left, length + left - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
    }
#endif
}

Зарегистрируйтесь на Хабре, чтобы оставить комментарий