How to become an author
Search
Write a publication
Pull to refresh

Comments 37

Пожалуйста, уточните — в некоторых местах у вас «наивный алгоритм», а в других «нативный алгоритм»
Это опечатка или американизмы?
Total votes 4: ↑2 and ↓20
Я полагаю это разные термины. Нативный имеется ввиду «родной», такое часто применяется когда идет речь о прямом использовании функционала нижележащей среды. Т.е. реализованная непосредственно в CLR ([MethodImpl(MethodImplOptions.InternalCall)]) функциональность для BLC может называться нативной.
Наивная реализация — это фактически синоним слова «топорная реализация», т.е. без учета каких-либо тонкостей, которые ценой небольших модификаций базового описания алгоритма дадут какой-либо выигрыш.
Total votes 4: ↑4 and ↓0+4
А я на стороне Java и тимсорта. Понятно, что ими движет: вот было у нас 100 файликов в папке, отсортированных по имени, юзер бросил еще два и снова попросил посортировать. 100 из 102 файлов уже расположены верно относительно друг друга, надо лишь поставить 2 новых на правильные места, тимсорт это сделает лучше дотнетовской сортировки. Таких примеров много: новые фотки на фотоаппарате, новые поступления данных в базу, консолидация данных из нескольких идентичных источников. Дотнет же предполагает, что мир больше хаотичен и случаен, мне в это меньше верится.
Total votes 2: ↑1 and ↓10
Немного странные примеры, так как в этом случае алгоритм бинарной вставки все равно быстрее TimSort.
Из моего опыта часто встречаются кластеры схожих данных, к примеру вы достаете данные из N страниц памяти или читаете из N мест, как правило данные в каждой странице близки по значения (одинаково удаленны от центра сортировки), а следовательно получается много схожих подпоследовательностей, так скажем подгрупп со схожими свойствами относительно других элементов. И тут TimSort быстрее? (затрудняюсь ответить)
Total votes 1: ↑1 and ↓0+1
Было бы интересно посмотреть на бенчмарки при реализации алгоритмов на одном языке. А то «на глазок» сравнивать — как-то не научно.
This comment wasn’t rated yet0
Было бы интересно узнать ещё и про реализацию сортировки в LINQ. Написать цепочку из OrderBy и ThenBy приятнее, чем реализовать метод для сравнения вручную: меньше кода, лучше читается, меньше шансов ошибиться в логике и т.п. Соответственно, интересно, насколько LINQ проигрывает по скорости сортировке массива.
Total votes 6: ↑6 and ↓0+6
В OrderBy используется устойчивый алгоритм в отличие от Array.Sort. А вообще если речь идет о LINQ to EF\NH\SQL то там вообще запрос в бд :-)
Total votes 1: ↑1 and ↓0+1
Посмотрите рефлектором EnumerableSorter<T>. Там чистый QuickSort, вроде бы ни во что не переходящий.
This comment wasn’t rated yet0
В примерах кода SorterGenericArray и SorterObjectArray закрывающих фигурных скобок больше, чем открывающих. И бросается в глаза do без while.

Стану читать дальше, если сделаете везде одинаковые отступы. В одном и том же куске кода встречается 1, 2 и 4 пробела. Крыша едет, глаза слезятся.
Total votes 3: ↑0 and ↓3-3
Стало читабельнее, спасибо. Ещё бы так же исправить раскардаш отступов в «Нативный QuickSort».
This comment wasn’t rated yet0
Сильно деградирует по скорости до O(n2) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, выбирая опорный элемент случайно, а не фиксированным образом;

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

А с TimSort сравнения не делали? Насколько я знаю, в питоне он используется достаточно давно, и менять не собираются.
Total votes 2: ↑0 and ↓2-2
Не обязательно случайно, можно сделать быструю сортировку детерминировано за O(n log n).

Не можете сказать идею такой сортировки или дать ссылку? Или это делается через какой-нибудь поиск медианы за O(N)? Тогда константа должна быть просто ужасной.
Total votes 3: ↑2 and ↓1+1
На графике секунды? .NET 4.5 Миллионный массив чего-нибудь за 10 минут сортируется?
This comment wasn’t rated yet0
Наверное, это миллисекунды.
This comment wasn’t rated yet0
Это миллисекунды.
This comment wasn’t rated yet0
К слову, замечу, что в 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 – исходники, графики, описания

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

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


Total votes 5: ↑5 and ↓0+5
Странно, что у вас 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%), зато код намного более простой…
This comment wasn’t rated yet0
Скорее всего из-за того, что память медленная, там на гитхабе указаны характеристики машины — RAM 8Gb, 1033. На домашней машине, где память быстрее, MergeSort работает тоже довольно таки значительно быстрее, но не скажу на сколько точно. Может на процентов 5-10.
This comment wasn’t rated yet0
Всегда расстраивался что в .NET FW не зашили несколько реализаций сортировок которые можно было бы выбирать при сортировке. Зачастую разработчик представляет природу своих данных и смог бы подобрать оптимальный алгоритм.
This comment wasn’t rated yet0
Никто не запрещает реализовать (или скопипастить) подходящий алгоритм сортировки, если вам так критичны 10% производительности в операции, которая занимает 5% времени работы программы. :)
This comment wasn’t rated yet0
Да что вы говорите? А я всё ждал такого бесценного совета.

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

А что касается 5% времени работы программы — если вы занимаетесь формочками и CRUD'ом — это ваши личные проблемы. Я уверен что очень многие разработчики тут пишут приложения в которых есть обработка больших объемов данных и их пользователям пригодились бы те самые 10% производителности.
Total votes 3: ↑2 and ↓1+1
Мне ещё не доводилось видеть на коленке реализованных алгоритмов сортировки. :) Вот сколько EnumerableExtensions и иже с ними повидал, чего только там не встречал, а сортировок — не было.

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

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

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

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

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

Вообще, пихать всё в фреймворк — не самая хорошая идея. И так эта дура 50 метров весит, а после установки — полтора-два гига (посмотрите на досуге размер C:\Windows\Assembly и C:\Windows\Microsoft.NET).
This comment wasn’t rated yet0
Не совсем понятно, что вы предлагаете разработчику в ситуации, когда ему полезны «10% производительности» и у него есть алгоритм той самой сортировки, который даёт эти самые 10%, но библиотечным не является? Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке? Или наступить на горло собственной песне, взять библиотечную реализацию и сказать пользователям «покупайте железо помощнее»?
This comment wasn’t rated yet0
Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке?

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

Пожалуй, я так и сделаю. Спасибо за идею! Жаль только, что универсальная сортировка у меня узким местом пока не является :(
This comment wasn’t rated yet0
5% времени работы программы могут быть критичными, если они составляют время между моментом, когда пользователь нажал кнопку и моментом, когда он увидел результат — чтобы еще что-то сделать, запустить долгий процесс и пойти пить кофе. 15 секунд он потерпит, а если это будет 20 секунд — отвлечется на какой-нибудь фейсбук, а потом будет говорить, что программа строила preview полчаса…
This comment wasn’t rated yet0
Может быть, дело в том, что когда эффективности Quicksort не хватает, то оптимальный алгоритм будет слишком специфичным? И шансов, что он окажется среди ещё десятка универсальных алгоритмов, которые могли бы предложить разработчики, будет не так уж много? Ведь кроме предполагаемого порядка элементов оптимальный алгоритм будет учитывать ещё и их вероятное распределение, кластеризацию, особенности функции сравнения. Например «сначала пустим поразрядную сортировку по этому полю, потом quicksort по этому сравнению на полученные фрагменты, а потом сольём их по этой быстро вычисляемой функции сравнения». Какие шансы, что такое удастся найти хоть в какой-нибудь библиотеке?
А меня в .NET больше расстраивает, что у них нет функции сортировки фрагмента массива по заданной функции сравнения. Для всего массива есть, а для фрагмента нет. Приходится в этом месте (если фрагмент небольшой) писать какой-нибудь пузырёк. Открыли бы они хотя бы создание компаратора по лямбда-выражению — не пришлось бы тратить время. Но нет, 10 строчек, а класс internal…
This comment wasn’t rated yet0
Есть ведь метод который сортирует элементы в диапазоне элементов массива, используя заданный компоратор
public static void Sort(T[] array, int index, int length, IComparer comparer).
Или вы имели ввиду метод принимающий Comparison?
This comment wasn’t rated yet0
Да, Comparison (обычно это лямбда-выражение, использующее текущее окружение). Сами они делают из него компаратор. Но нам этого класса не дают.
This comment wasn’t rated yet0
Да знаю. Сам пользуюсь часто перегрузкой с делегатом) Согласен, что было бы удобнее если бы такой метод был бы, так как с компоратором не очень удобно.
This comment wasn’t rated yet0
Может быть, просто украсть у них этот класс и пользоваться:

        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); 
            } 
        }

Total votes 1: ↑1 and ↓0+1
Можно!!!)))) Но лучше бы они добавили реализацию, при которой нам не понадобиться красть)))))
This comment wasn’t rated yet0
Можно написать свою реализацию генерации компаратора, иногда довольно удобно. Лично я для себя остановился на таком:

[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));
}

Сами делегаты строятся на экспрешенах. В итоге получается достаточно удобно.
Сама реализация на гитхабе: тыц и тыц. Планирую потом перенести в другое отдельное решение, может кому пригодится. Но вообще довольно юзабельным должно быть. Ну и конечно каждый под себя может переделать как ему больше нравится.
This comment wasn’t rated yet0
Кстати, лучше все же смотреть на 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
}
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr