Comments 45
Браво. Читал с удовольствием.
но меня задолбало это это набирать
Ну есть же замена в редакторе, это быстро.
И вот тут кажется мы можем нащупать какую-то пользу из нашего эксперимента. Мы получили действую модель оптимизации алгоритма под исходные данные. Если мы что-то знаем про частотность перестановок в исходных данных, мы можем подогнать под них алгоритм сортировки и получить гарантированно самую быструю сортировку. Быстрее теоретических чисел сортировки.
Ну вот, а когда я пишу что сортировка зависит от контекста данных (да и не только сортировка, но и кодирование, сжатие и т.д.), то меня закидывают ссаными тряпками, мол не трогай святое пользуйся универсальными методами и вообще, если метод не универсальный и не стабильный то он фуфуфу.
Но эти же люди продолжают пользоваться архиваторами видимо забывая как именно устроены ключи степени сжатия в самой программе и почему контекст важен.
и при этом люди забывают, что контекст важен. это единица информации, которая идёт с архивом вместе с данными - насколько оптимально был упакован архив.универсальные алгоритмы всегда проигрывают специфичным именно потому, что у них нет либо они игнорируют эту информацию.
поскольку даже мне, только поверхностно изучавшей теорию информации 10 лет назад в университете, понятно, что более продвинутые алгоритмы сначала анализируют входную информацию, чтобы подобрать более подходящий метод сжатия. если бы это было не так - мы бы до сих пор пользовались бы каким-нибудь rle, в худшем случае - по теореме Шеннона (zip в основной модификации)
а потому современные упаковщики, сначала смотрят тип данных для упаковки, а потом выбирают стратегию упаковки именно исходя из полученного анализа
а потому современные упаковщики, сначала смотрят тип данных для упаковки, а потом выбирают стратегию упаковки именно исходя из полученного анализа
Нет же. Они гонят все в gzip или те что более продвинутые в zstd. И не парятся.
не совсем так. тут вопрос скорее бизнес модели. но крупные компании типа амазона или гугла заморачиваются по поводу контекстного сжатия.
кстати PNG по сути как раз сжимает данные в зависимости от контекста, а вот насколько хорошо, то уже зависит от реализации, поэтому я обычно за paint.net и photoshop еще файлы дожимаю с помощью Pingo. У меня на сетевом диске есть библиотека PNG файлов для рисования всякого, размер около 4 Гб, я прогнал как-то ее через Pingo и уменьшил размер до 3.2Гб.
Подобрать более подходящий алгоритм под паттерн данных на стадии проектирования можно. И так делают иногда. Хотя как правило все равно просто берут gzip или zstd.
Это все равно безмерно далеко от анализа текущего потока и подбора чего-то под него. Один раз спроектировали, написали и оно крутится годами.
PS: Правильная настройка словаря для zstd дает больше чем практически все остальное (работающее со сравнимой скоростью) на почти любом паттерне данных.
настройка словаря - это и есть контекстная настройка, каким методом вы решили задачу не так важно. я вам писал ответ на ваши "берут gzip и не парятся", а вы тут же пишете что "настраивают словарь", то есть заморочились таки.
В подавляющем большинстве случаев берут гзип и не парятся. Оно того не стоит. В остальных случаях стоит подумать о чем-то вроде настройки словаря zstd.
И это все равно не "сначала смотрят тип данных для упаковки, а потом выбирают стратегию упаковки именно исходя из полученного анализа".
То что кто-то не слишком умный это понятно, но мы же не такие, а значит выбор стратегии имеет место быть. Ну и разговор идёт об обычных архиваторах, а не о бизнес-моделях, а там zip/7z/rar где Deflate совсем не единственный метод, скорее уж вы попадёте на LZMA.
Лично я для себя пользуюсь zpaq (m5) и 7zip(bzip2 или ppmd) и за 50 лет ни разу не пользовался ни gzip ни zstd.
ну я что-то не припомню чтобы популярные архиваторы занимались анализом данных (ниже напишу). я говорю о том что степень сжатия, которая обозначена в настройках архиватора это не какой-то очень умный алгоритм, а просто выбор набора алгоритмов меняющих соотношение сильная_степень_сжатия/скорость.
касательно контекста, есть например архиватор zpaq, у него используется контекстная модель. тут да - достигается повышение степени сжатия за счет анализа данных, но сжимает он долго. основный архиваторы крутятся вокруг словарных методов и в большинстве своем на первое место ставятся или скорость или количество используемой памяти.
Пример тупой сортировки (не стоит её повторять):
#include
#define N 10
int main()
{
int vec[N] = {1, 7, 3, -7, -1, 7, 9, -2, 5, 8};
for (auto i = 0; i < N - 1; ++i)
if ((vec[i] > vec[i + 1])) {
std::swap(vec[i], vec[i + 1]); i = -1;
}
for (auto i = 0; i < N; ++i) std::cout << vec[i] << "\t";
return EXIT_SUCCESS;
}
Согласен, это победитель)
По сложности он идентичен самому первую варианту в статье. Так что они тут делят первое место по тупости :)
По идее у Bogosort тупость всё же чуть выше (если не смотреть на память). Дело в сохранении информации — ваш алгоритм гарантированно проверяет каждый вариант максимум один раз, и с каждым шагом он всё ближе к получению "правильного" массива; в то же время Bogosort не ограничен от "топтания на месте" ничем. Так что O(n*n!) у вас соответствует максимальному времени сортировки, а у Bogosort — среднему… впрочем, его преимущество в том, что памяти почти не нужно.
Ох, насколько же приятно выглядит мобильная википедия на десктопе!
https://ru.wikipedia.org/wiki/Лас-Вегас_(алгоритм) из этой серии)
Блин, как начал читать статью, тут же подумал об этом алгоритме, но оказалось, что его уже придумали (
Я больше SlowSort предпочитаю
никакого рандома
экспоненциальная сложность
Моя номинация на самую тупую сортировку:
Java
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
final int[] arr = {1, 7, 3, -7, -1, 7, 9, -2, 5, 8};
final int[] sorted = naiveSort(arr);
System.out.println(Arrays.toString(arr));
System.out.println(testSorted(arr));
System.out.println(Arrays.toString(sorted));
System.out.println(testSorted(sorted));
}
private static int[] naiveSort(int[] arr) {
final int[] sorted = new int[arr.length];
final boolean[] checked = new boolean[arr.length];
Arrays.fill(checked, false);
for (int i = 0; i < arr.length; i++) {
sorted[i] = findMin(arr, checked);
}
return sorted;
}
private static int findMin(int[] arr, boolean[] checked) {
int min = Integer.MAX_VALUE;
int minInd = 0;
for (int i = 0; i < arr.length; i++) {
if (!checked[i] && arr[i] <= min) {
min = arr[i];
minInd = i;
}
}
checked[minInd] = true;
return min;
}
private static String testSorted(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return "Array is not sorted";
}
}
return "Array is sorted";
}
}
Хотя это скорее не тупая, а "наивная". Т.е. если бы я ничего не знал о программировании (ну, кроме синтаксиса), я бы написал именно так. Даже то что можно просто поменять местами два элемента - это какая-то иезуитская хитрость :) Я бы наверно сам не допёр, по крайней мере, не сразу.
это ж по сути сортировка выбором, только складывают не в отдельный массив, а в начало/конец сортируемого, сдвигая неотсортированное.
Но это самый естественный способ сортировать, по-моему все кто еще не знает алгоритмы сортировки делают что-то наподобие этого.
Это сортировка выбором (selection sort). Добавить немного улучшений в часть findMin и сразу получите heapsort.
У меня самый простой вариант:
public void sort(List<Integer> list) {
while (!isSorted(list)) {
Collections.shuffle(list);
}
}
private boolean isSorted(List<Integer> list) {
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i) > list.get(i + 1))
return false;
}
return true;
}ага, выше уже давали ссылку на https://ru.m.wikipedia.org/wiki/Bogosort
У вас он еще и некорректный, потому что если числа повторяются, список никогда не отсортируется :)
Отличный вариант! Но персонально останусь верен O(n) StalinSort https://github.com/gustavo-depaula/stalin-sort
Конечно, это юмористическая статья, но подобная сортировка оптимизированная под размер массива (4-9 элементов) существует в прод-коде. Если не изменяет память, разработчики гугла применили такое в одной из библиотек и увеличили скорость сортировки внутри sql-запросов до 30 %.
Реализация libcxx обрабатывала несколько конкретных случаев особым образом. Коллекции длиной 5 или меньше сортировались при помощи специальных самописных сортировок на основе сравнений.
https://habr.com/ru/articles/662181/
который я где-то пролюбил
fixed. Вот среднее число сравнений если каждый раз выбирать индексы жадно (максимизируя min(len(lss), len(gtr)). Было бы хорошо если бы обновили график.
ссылка на код
[1.0, 2.6666666666666665, 4.666666666666667, 6.933333333333334, 9.577777777777778, 12.39047619047619, 15.406795634920634]более тупое
Тут автор весьма принижает свои размышления, ведь на самом деле речь не о поиске сортирующей перестановки без дополнительно памяти, а вполне себе серьезный математический вопрос:
какое наименьше (в среднем) число вопросов (сравнений двух элементов) нужно задать что бы отгадать загаданную перестановку
Подержите моё пиво
Автор чем-то пьян. Пьян идеей ?
О, когда весной изучал работу нового поколения псевдоразумных нейросетей архитектуры трансформера (GPT3 / GPT 4 и их многочисленные аналоги), в частности остановился на том, как они сортируют списки или занимаются простым счетом если задать им такую задачу в чистом виде или как часть более общей.
В частности что они без проблем справляются с короткими списками, но начинают ошибаться и сильно тупить (даже если указывать им на ошибки и пытаться помочь/подсказать) если список становится длиннее (в зависимости от конкретной реализации и "размера" сети = количества ее "параметров"/весов, это происходит где-то в диапазоне от 7-10 элементов и до нескольких десятков)
И пришел к выводу, что нейросети в процессе "тренировки" самостоятельно сформировали внутри себя очень специфические алгоритмы. Которые скорее всего представляют что-то очень похожее на описанное вами! Конкретно для случая сортировки.
Вот тут про это немного писал в комментариях:
https://habr.com/ru/companies/ods/articles/716918/comments/#comment_25509482
https://habr.com/articles/729966/#comment_25509056 (тут 1й пример, где прошу нейросеть на базе GPT-4 отсортировать буквы по алфавиту)
Что-то похожее(хотя и немного другое) происходит и с математическими операциями, когда подобная нейросеть пытается выполнять математические операции — там размерность чисел не ограничена, но результат получается "примерный".
Из-за того, что такие нейросети класса "большая текстовая модель", в частности Трансформер имеют очень жесткие исходные(архитектурные) ограничения: они не рекуррентные (т.е. прямые циклы или даже их иналоги в их внутренних алгоритмах просто невозможны, но зато возможны множественные и очень сложные ветвления и проверки условий!), у них нет "рабочей памяти" для хранения переменных(память и слежение за контекстом разговора чат-ботов на основе таких сетей реализуется внешними алгоритмами, подающими часть истории разговора на вход нейросети заново при каждом следующем сообщении/запросе).
То при достаточном уровне тренировки и размере сети (количестве параметров представляющих собой аналог объема кода) в ней рождаются вот такие вот "тупые" алгоритмы. В частности для сортировки и подсчета элементов. Не по принципу "тупости", а "жить захочешь, еще не так раскорячишься" (с).
Вот представьте, что вы программируете, но у вас в распоряжении есть только один очень дурацкий язык программирования, в котором ВООБЩЕ отсутствуют циклы и нет доступа к оперативной памяти для хранения переменных(зато констант прямо в код нафигачить можно почти неограниченно) и даже встроенных базовых математический операций(сложение, умножение и т.д.) в языке нет. Но зато if… then… else и их аналоги (Case, Select и т.д.) можно фигачить в код тоже почти в неограниченных количествах.
И вам вот с таким "инструментарием" нужно отсортировать массив, или сосчитать количество элементов в некотором множестве или выполнять математические операции и т.д.
И вот тогда, подобные "тупые" алгоритмы, окажутся далеко неплохим вариантом, а вероятно одним из лучшим (из возможных в конкртеных ограниченных условиях). А вот это:
А факториал растет очень быстро, значит наши функции будут становиться все длиннее, отнимая не только вычисления, но и память — ее нам тоже потребуется O(n!). Не для хранения данных (мы же их даже никуда не сохраняем), а для самого алгоритма.
Становится не багой (простыни говнокода из бесконечной лапши IF-ов, вместо считанных байт для хранения нескольких переменных и обработки в цикле и вызова функций рекурсией), а киллер-фичей в условиях когда этих самых байт ОЗУ тупо нет в принципе (точнее не можем в него ничего писать во время исполнения "кода"), зато мегабайты кода — вообще не проблема.
Самая крутая сортировка — квантовая. Имея квантовый источник случайного шума, можно за O(n) получить случайную перестановку массива. Потом, опять же за O(n), можно, как верно заметил автор, проверить, а не отсортирован ли массив. Если нет, то надо, всего-лишь уничтожить вселенную. В результате (если принять многомировую интерпретацию квантовой физики) останется хотя бы одна вселенная, в которой массив отсортирован за O(n). Вот, мы и изобрели линейный алгоритм сортировки!
Обычно люди удивляются и не верят, когда им говоришь, что для целых чисел (int32 например) вычислительная сложность сортировки - это O(1). Но так и есть. По памяти она, правда, хромает, но зато честный научный O(1).
Всмысле? Да будь там числа хоть 0,1 — все равно надо все числа обойти. O(n) получается.
Не получается. O(1) означает, что существует такое константное k, что алгоритм заканчивается за k шагов для всех размеров входа. Целых чисел фиксированное количество (2^32 штук например), а значит, такое k существует.
Если кажется ну совсем сюром, тогда вот другой (на этот раз вполне себе практический, даже по памяти приемлемый): алгоритм сортировки «за O(n)», если диапазон чисел не очень велик и все числа в массиве уникальны (на самом-то деле он тоже O(1), ну да назовем это «похожим на O(n)»). Например, если у нас есть не более 1000 уникальных элементов в диапазоне 0..999, можно их отсортировать за ~2000 шагов: берем зануленную битовую карту на 1000 битов (это всего-то 125 байтов), дальше идем по входному массиву и взводим в 1 бит, соответствующий очередному числу. В конце проходим по битовой карте и выплевываем в качестве результата позиции тех битов, где 1 (тут огромный простор для оптимизаций: можно проскакивать те 8-байтовые группы, где все нули например). Похожий алгоритм широко используется в СУБД.
Нет же. 32 битных чисел — конечное число. Массивов из них — бесконечное. Не существует такого k. Допустим оно есть, а я вам дам массив из k+1 числа. И даже не любой массив, а очень ограниченный — все числа там нули и только одно число больше нуля. За k шагов вы даже это ненулевое число не всегда найдете, а найти его надо, ведь оно может быть любым. А оно может быть на любой из k+1 позиции.
Да, если у вас чисел строго ограниченное количество, то можно, конечно, и сову O(1) натянуть на глобус ассимптотики. Но это солипсизм какой-то получается. Такто, у вас всегда ограниченное количество данных, ибо компьютеры конечны. Поэтому счтают скорость роста от размера входных данных, хоть бы этот размер и ограничен, что не строго соответствует математическому определению.
Пишем самую тупую на свете сортировку