Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Соглашусь, очень похоже. Но есть принципиальные отличия, меняющие картину. Пресловутая досортировка здесь сводится к минимуму. Она производится для массивчиков из 2-х, 3-х и 4-х чисел, где она тривиальна и мало затратна.
Во вторую итерацию попадают подмассивы с разностью n max — n min близкой к n, то-есть уже во второй итерации слипаний, а значит и операций сравнения будет немного. То-есть даже на плохих данных сложность не должна превосходить n log n.
Одна простая, но очень важная мысль: «В массиве из n чисел всегда не более чем n различных значений».
Во вторую итерацию попадают подмассивы с разностью n max — n min близкой к n, то-есть уже во второй итерации слипаний, а значит и операций сравнения будет немного. То-есть даже на плохих данных сложность не должна превосходить n log n.
Одна простая, но очень важная мысль: «В массиве из n чисел всегда не более чем n различных значений».
То-есть даже на плохих данных сложность не должна превосходить n log n.
Это вряд ли. Если исходный массив содержит числа 1!, 2!, ..., n! (в произвольном порядке), или какой-нибудь более случайный набор, у которого log(log(n_k)) равномерно распределены на достаточно длинном отрезке, то на каждом шаге все числа, кроме одного, попадут в одну ячейку. И сложность будет n^2. Факториалы являются целыми положительными числами (хотя и произвольной длины), так что это условие не нарушено.
Да, верно. Математический склад ума все-таки отличается от обывательского. Никогда бы не пришло в голову сортировать факториалы. У факториалов и прочих сильно растущих функций есть один недостаток — сложно выписать достаточно много значений. Разрядность ограничена.
Кроме того, можно применить «ход конем». Если имеются предположения о функции, порождающей отсортированный массив, можно применить нелинейное распределение значений по местам. Перемешанные факториалы, экспоненты и подобные сильно меняющиеся значения довольно специфичны.
Кроме того, можно применить «ход конем». Если имеются предположения о функции, порождающей отсортированный массив, можно применить нелинейное распределение значений по местам. Перемешанные факториалы, экспоненты и подобные сильно меняющиеся значения довольно специфичны.
В принципе, даже не обязательно генерировать ряды с помощью быстрорастущих функций.
Достаточно только неудачного минимума/максимума, чтобы сделать дельту не соответствующей среднему значению. Тогда подлый экстремум окажется на одном полюсе распределения, все остальные элементы — на противоположном.
Достаточно только неудачного минимума/максимума, чтобы сделать дельту не соответствующей среднему значению. Тогда подлый экстремум окажется на одном полюсе распределения, все остальные элементы — на противоположном.
Анимация
Но тогда эти «остальные элементы» будут распределены уже более-менее равномерно, и при рекурсивном вызове алгоритм отсортирует их за линейное время. В случае факториалов распределение «один против всех» будет при каждом вызове.
Обдумываю тоже эту тему. Надо каким-то образом выявить сильную нелинейность. Пока осмысливается критерий того что что-то не так — вызов второй итерации, для которой количество значений несущественно меньше, чем начальное n. Раз так, то вместо того чтобы дальше сортировать с квадратичной сложностью, нужно либо интерполировать поточнее, либо использовать какой-то другой алгоритм сортировки.
>>> Преимущества:
>>> Скорость, легкость понимания и программирования.
А также: православный способ сортировки. )))
>>> Скорость, легкость понимания и программирования.
А также: православный способ сортировки. )))
Родилось решение по сортировке факториалов и быстрого роста.
Вычисление индекса надо производить над логарифмами сортируемых значений.
delta=(log(n max)-log(n-min))/n+1
indx=(log(n i)-log(n min))/delta+1
Подходящее основание логарифма от 1,1 до 2.
Логарифмирование не отменяет следующих итераций, которые уже можно делать над самими значениями, но исключает квадратичную сложность.
Вычисление индекса надо производить над логарифмами сортируемых значений.
delta=(log(n max)-log(n-min))/n+1
indx=(log(n i)-log(n min))/delta+1
Подходящее основание логарифма от 1,1 до 2.
Логарифмирование не отменяет следующих итераций, которые уже можно делать над самими значениями, но исключает квадратичную сложность.
Надо будет поиграться с этими логарифмами (было бы время)… А если обычное линейное распределение, не пробовали? Эти формулы тоже подойдут?
В принципе, при линейном распределении тоже более-менее.
Вот такой вот массив двузначных чисел:
С помощью логарифмической дельты распределила следующим образом:
С помощью обычной дельты раскидала так:
То есть большие элементы логарифмическая дельта распределяет качественнее.
А вот так логарифмы расфасовали набор из 10-ти чисел от 0 до 9.
Без логарифмов бы каждое число попало бы в отдельную корзину.
Вот такой вот массив двузначных чисел:
С помощью логарифмической дельты распределила следующим образом:
С помощью обычной дельты раскидала так:
То есть большие элементы логарифмическая дельта распределяет качественнее.
А вот так логарифмы расфасовали набор из 10-ти чисел от 0 до 9.
Без логарифмов бы каждое число попало бы в отдельную корзину.
UPD. Чтобы у меня VBA не ругалось на логарифмы чисел <= 0 я поставил значение таких функций 0 (что неверно, разумеется)
Массив из 10 чисел от 1 до 10 логарифмическая дельта так бы распределила:
Массив из 10 чисел от 1 до 10 логарифмическая дельта так бы распределила:
Главная фишка в том, что наборы чисел, которые в отсортированном виде ложатся на прямую delta*i+n min, i=0..n сортировать вообще не нужно. Достаточно сгенерировать заново этот набор.
Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.
Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
1) Если данные линейны или близки к линейным, оперируем со значениями.
2) Если нелинейны, причем сильно — логарифмируем. Натуральные логарифмы вполне годятся.
Вообще в нелинейном случае стоит задача сжать динамический диапазон значений. Может быть, арктангенс подойдет даже лучше.
Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.
Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
1) Если данные линейны или близки к линейным, оперируем со значениями.
2) Если нелинейны, причем сильно — логарифмируем. Натуральные логарифмы вполне годятся.
Вообще в нелинейном случае стоит задача сжать динамический диапазон значений. Может быть, арктангенс подойдет даже лучше.
Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
>>>Главная фишка в том, что наборы чисел, которые в отсортированном виде ложатся на прямую delta*i+n min, i=0..n сортировать вообще не нужно. Достаточно сгенерировать заново этот набор. Это правило распространяется в принципе на любую функцию. Если известна функция, порождающая отсортированный набор, достаточно ее вычислить для n необходимых значений и получить отсортированный набор.
Сильно оторвано от практики. Идеально вписывающихся в функцию наборов значений почти не встречаются.
Кроме того Вы попадаете в порочный круг. Чтобы придти к выводу, что элементы нет надобности сортировать — их нужно отсортировать, чтобы увидеть вписываются ли они в какую-нибудь выхолощенную формулу.
>>> Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
Если заранее есть точные сведения (ну или с высокой долей вероятности), то такая логика — ещё куда ни шло.
Но если набор пока не отсортирован, то понять степень нелинейности весьма затруднительно, если вообще возможно. Всё от чего можно оттолкнуться (после предварительного однократного прогона по структуре и не впадая в какие-то дополнительные расходы по памяти) — минимум, максимум и среднее арифметическое/геометрическое. Но этого, скорее всего, не хватит. Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.
>>> Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
В этом направлении можно сгенерировать несколько интересных идей.
Например, можно распределить небольшую часть массива (а ещё лучше — несколько, чтобы свести к минимуму влияние вырожденных ситуаций) обоими способами и сравнить по каким-то критериям насколько качественным вышло распределение по карманам в обоих случаях.
В целом, в гибридных (и вообще) сортировках я не припомню подхода, чтобы для решения по какому пути двигаться — нужно предугадать уровень энтропии в результате (хотя сортировки в основном придумывают программисты знающие толк в математике). Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
Сильно оторвано от практики. Идеально вписывающихся в функцию наборов значений почти не встречаются.
Кроме того Вы попадаете в порочный круг. Чтобы придти к выводу, что элементы нет надобности сортировать — их нужно отсортировать, чтобы увидеть вписываются ли они в какую-нибудь выхолощенную формулу.
>>> Перед тем как начинать собственно сортировку, необходимо понять, а какого вида у нас набор?
Если заранее есть точные сведения (ну или с высокой долей вероятности), то такая логика — ещё куда ни шло.
Но если набор пока не отсортирован, то понять степень нелинейности весьма затруднительно, если вообще возможно. Всё от чего можно оттолкнуться (после предварительного однократного прогона по структуре и не впадая в какие-то дополнительные расходы по памяти) — минимум, максимум и среднее арифметическое/геометрическое. Но этого, скорее всего, не хватит. Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.
>>> Безумная идея пришла в голову. Вместо того, чтобы решать, брать логарифмы или нет, надо запустить параллельно обе версии. Версия отработавшая быстрее останавливает другую.
В этом направлении можно сгенерировать несколько интересных идей.
Например, можно распределить небольшую часть массива (а ещё лучше — несколько, чтобы свести к минимуму влияние вырожденных ситуаций) обоими способами и сравнить по каким-то критериям насколько качественным вышло распределение по карманам в обоих случаях.
В целом, в гибридных (и вообще) сортировках я не припомню подхода, чтобы для решения по какому пути двигаться — нужно предугадать уровень энтропии в результате (хотя сортировки в основном придумывают программисты знающие толк в математике). Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
В целом, в гибридных (и вообще) сортировках я не припомню подхода, чтобы для решения по какому пути двигаться — нужно предугадать уровень энтропии в результате
В каком-то смысле это происходит, когда quicksort, решив, что случай неблагоприятный, переключается на heapsort. Там реакция идёт не на размер массива, а на уже обнаруженные статистические свойства порядка элементов.
Я только шапочно ознакомился с интроспективной сортировкой (не дошли пока руки разобраться в ней подробно), но насколько помню, что действительно «в каком-то смысле». Переключение происходит в результате достижения заранее оговоренной глубины рекурсии. Грубо говоря, переключаемся через изначально планируемое количество итераций, а не по результатам анализа характера распределения текущего набора данных. Повторюсь, в алгоритм я по сути не вникал, так что, может, я и не прав.
Правильно. Но то, что глубина рекурсии превысила планируемое число итераций — это и есть следствие того, что распределение (точнее, порядок) оказался неблагоприятным. А дальше авторы предположили, что раз уж случилось такое невероятное событие, то логично считать, что враги подсунули алгоритму набор-киллер, и теперь надо от него застраховаться (хотя, возможно, весь ущерб уже нанесён, а дальше было бы всё хорошо).
>> Поведение нелинейности может напоминать вообще какую-нибудь хитрую недосинусоидную псевдоэкспоненту, которая станет очевидна только в конце процесса.
Проще. Отсортированный рост является неубывающим. А если договориться о неразличимости одинаковых чисел, то и строго возрастающим. И чаще всего его вид будет кусочно линейно-нелинейным.
Этот алгоритм сортировки сам в некоторой степени являет собой кусочно-линейную аппроксимацию. С разрывами на стыках кусков. Естественно, что в линейной версии он спотыкается на экспоненте, которую как ни дифференцируй — она остается экспонентой. Но не страшно, для нее у нас припасен логарифм. Вопрос, похоже, становится чисто организационным. Когда выгоднее логарифмировать, в первом проходе, во втором или вообще запускать обе версии параллельно.
Что касается расходов по памяти — их можно сильно уменьшить. Массив количества индексов никуда не денется, конечно. Но вместо копирования самих чисел мы сохраняем указатели на них. Особенно выгодно получается, если работаем с действительными числами полной точности. (Само число — 10 байт, ссылка на него — 2 или 4 байта). Итого — памяти нужно не более 4n. В байтах: 10*n+ 2*3 n.
>>Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
Вот. Именно. Еще одна фундаментальная мысль. Если имеется дополнительная информация об обрабатываемых неким алгоритмом данных, то она позволяет снизить сложность алгоритма. Как пример — таблицы Брадиса. Можно считать синусы с помощью рядов, а можно выбрать значение из таблицы.
Проще. Отсортированный рост является неубывающим. А если договориться о неразличимости одинаковых чисел, то и строго возрастающим. И чаще всего его вид будет кусочно линейно-нелинейным.
Этот алгоритм сортировки сам в некоторой степени являет собой кусочно-линейную аппроксимацию. С разрывами на стыках кусков. Естественно, что в линейной версии он спотыкается на экспоненте, которую как ни дифференцируй — она остается экспонентой. Но не страшно, для нее у нас припасен логарифм. Вопрос, похоже, становится чисто организационным. Когда выгоднее логарифмировать, в первом проходе, во втором или вообще запускать обе версии параллельно.
Что касается расходов по памяти — их можно сильно уменьшить. Массив количества индексов никуда не денется, конечно. Но вместо копирования самих чисел мы сохраняем указатели на них. Особенно выгодно получается, если работаем с действительными числами полной точности. (Само число — 10 байт, ссылка на него — 2 или 4 байта). Итого — памяти нужно не более 4n. В байтах: 10*n+ 2*3 n.
>>Переключение между методами происходит только в зависимости от размера массива, а набор данных всегда воспринимается как «чёрный ящик», о котором практически ничего не известно.
Вот. Именно. Еще одна фундаментальная мысль. Если имеется дополнительная информация об обрабатываемых неким алгоритмом данных, то она позволяет снизить сложность алгоритма. Как пример — таблицы Брадиса. Можно считать синусы с помощью рядов, а можно выбрать значение из таблицы.
Хорошо, что Вы сказали про аппроксимацию. Я припомнил, что есть же метод с однокоренным названием.
en.wikipedia.org/wiki/Proxmap_sort
Ещё не разбирался с ним, но по-моему что-то родственное тому что мы здесь обсуждаем.
en.wikipedia.org/wiki/Proxmap_sort
Ещё не разбирался с ним, но по-моему что-то родственное тому что мы здесь обсуждаем.
Все сортировки без сравнений похожи. Суть — распределить n чисел по m классам. Только мало кто догадывается, что классов должно быть не менее n.
Кстати, свежая догадка. Если классов взять больше n, вплоть до nmax-nmin, то тогда слипаний станет существенно меньше, а при m= nmax-nmin их не будет вовсе. Разумеется, последнее справедливо для целых чисел. То-есть в массиве Indxs(i) будут только нули и единицы, вследствие чего сборка будет происходить за линейное время без дополнительных действий. Пугает расход памяти, но это решаемая проблема.
Конечно, реализован будет промежуточный вариант. Возможно, m=n*3 будет достаточно для существенного сокращения обычно большого количества пар и троек.
Кстати, свежая догадка. Если классов взять больше n, вплоть до nmax-nmin, то тогда слипаний станет существенно меньше, а при m= nmax-nmin их не будет вовсе. Разумеется, последнее справедливо для целых чисел. То-есть в массиве Indxs(i) будут только нули и единицы, вследствие чего сборка будет происходить за линейное время без дополнительных действий. Пугает расход памяти, но это решаемая проблема.
Конечно, реализован будет промежуточный вариант. Возможно, m=n*3 будет достаточно для существенного сокращения обычно большого количества пар и троек.
Помимо размера сортируемых подмассивов, категории которыми оперируют при переключении с одного метода на другой — «случайно перемешано» / «почти остортировано» / «реверсно отсортировано». Методов оценок линейности распределения данных ни Седжвик, ни Хоар, ни Дейкстра, ни Кнут, ни прочие мастодонты, не придумали (то есть мне об этом ничего не известно).
Некоторые алгоритмы заточены под определённого вида наборы данных, но при условии, что это известно до начала сортировки, а не вычисляется по ходу действия.
Некоторые алгоритмы заточены под определённого вида наборы данных, но при условии, что это известно до начала сортировки, а не вычисляется по ходу действия.
Ах да, ещё надо решить что с нулями делать )))
UPD. Ничего не делать, сортировка изначально рассчитана на натуральные числа. Или можно увеличить все элементы на число, достаточное чтобы все оказались положительными, отсортировать и затем уменьшить на это число.
UPD. Ничего не делать, сортировка изначально рассчитана на натуральные числа. Или можно увеличить все элементы на число, достаточное чтобы все оказались положительными, отсортировать и затем уменьшить на это число.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Соломонова Сортировка