"рекурсивный qsort на иммутабельном списке" - это школотронство, предназначенное для обучения, а не реального применения.

давайте к аморт. сложности вернемся

Например?

например O(n) требование по памяти

я пока не понял какое отношение она имеет к qsort и мне очень интересно ))

например O(n) требование по памяти

Удовлетворяет ж

Удовлетворяет ж

нет, там расход памяти O(n²)

нет, там расход памяти O(n²)

может быть больше либо меньше, но не суть

да, меня интересует скорость и гарантии по потреблению памяти. Вы не согласны с тем, что "прстой" квиксорт на хакеле сложнее чем O (n * log n) / O(1) ?

А зачем вам асимптотическая сложность, если в реальности будет по-другому? Ведь, внезапно, в реальности у реализации на хаскеле потребление памяти скорее всего не растёт как n*ln(n)

нет, там расход памяти O(n²)

С чего?

нет, там расход памяти O(n²)

Смотри ещё раз)))

А зачем вам асимптотическая сложность, если в реальности будет по-другому? Ведь, внезапно, в реальности у реализации на хаскеле потребление памяти скорее всего не растёт как n*ln(n)

но оно же и не постоянное, не так ли?

Смотри ещё раз)))

ладно, да, O(n * log n)

А зачем вам асимптотическая сложность, если в реальности будет по-другому? Ведь, внезапно, в реальности у реализации на хаскеле потребление памяти скорее всего не растёт как n*ln(n)

что значит "скорее всего"? оно либо будет либо не будет и асимптотической сложности это имеет прямое отношение

ладно, да, O(n * log n)

Ещё раз смотри

Ещё раз смотри

??? каждое "ещё раз смотри" добавляет логарифм?

А зачем вам асимптотическая сложность, если в реальности будет по-другому? Ведь, внезапно, в реальности у реализации на хаскеле потребление памяти скорее всего не растёт как n*ln(n)

я там выше приводил код с in place сортировкой на хаскиле. Вы егопроигнорили, а зря - лучшие учёные умы на хакеле бьются многие годы над тем, что любой джун на голанге напишет

??? каждое "ещё раз смотри" добавляет логарифм?

убавляет)

но оно же и не постоянное, не так ли?

Оно хз какое

Оно хз какое

это всё придирки к словам. Оно не постоянное

Ещё раз смотри

Что там ещё раз смотреть? Приходит список длинны n, мы поделим его на части log n раз. При этом после каждого деления у нас добавляется log₂k списков (где k - глубина текущей рекурсии), сумма длинн которых всегда равна n.

@bertolu4i поясните про аморт. сложность пожалуйста

@bertolu4i поясните про аморт. сложность пожалуйста

в гугл и випедию плиз

Что там ещё раз смотреть? Приходит список длинны n, мы поделим его на части log n раз. При этом после каждого деления у нас добавляется log₂k списков (где k - глубина текущей рекурсии), сумма длинн которых всегда равна n.

ну а теперь посмотри как устроены списки в хаскеле)

это всё придирки к словам. Оно не постоянное

Неа Вы не сможете спрогнозировать потребление памяти для языка со сборщиком мусора, ленивостью и сильно оптимизирующийся компилятором

в гугл и випедию плиз

я то в курсе что это такое, поясните какое отношение она имеет к qsort?

я там выше приводил код с in place сортировкой на хаскиле. Вы егопроигнорили, а зря - лучшие учёные умы на хакеле бьются многие годы над тем, что любой джун на голанге напишет

Пожалуйста, напишите библиотечную функцию быстрой сортировки для go Чтобы было честно, пусть она работает каким в других языках с обобщёнными типами

Пожалуйста, напишите библиотечную функцию быстрой сортировки для go Чтобы было честно, пусть она работает каким в других языках с обобщёнными типами

А потом мы сравним бенчмарк, потребление памяти и простоту кода

ну а теперь посмотри как устроены списки в хаскеле)

так ну первый рекурсивный вызов у нас заюзает ~ n + (n - n / 2) памяти, вторая ~ n + (n - n / 2) + (n - n / 4), третья ~ n + (n - n / 2) + (n - n / 4) + (n - n / 8). Снова n * log n. UPD: на каждой глубине рекурсии будет заюзано на самом деле ~ n + n * k / 2, где k глубина рекурсии. В общем-то это ничего не меняет, расход по памяти остаётся O(n * log n)

Пожалуйста, напишите библиотечную функцию быстрой сортировки для go Чтобы было честно, пусть она работает каким в других языках с обобщёнными типами

уже написали - sort.Slice

что значит "скорее всего"? оно либо будет либо не будет и асимптотической сложности это имеет прямое отношение

Неа Учитывая что: - у нас работает оптимизирующий компилятор - сборщик мусора - переупорядочивание инструкций - кэширование данных - кэширование инструкций - бранч предиктор - предиктор подкачки памяти - куча магии - всё это работает внутри ОС нереального времени Я бы вообще не стал бы делать никаких сильных заявлений, особенно без экспериментов

уже написали - sort.Slice

Она написана через рекурсию

)

Она написана через рекурсию

но не такую как в хакеле, без потребления стека

Она написана через рекурсию

можно было бы и через циклы перепиать, мало что изменилось бы

ого, (не хвостовая) рекурсия без потребления стека, это как?

но не такую как в хакеле, без потребления стека

С чего ты взял? Оптимизации хвостовой рекурсии в го нет, а это даже не хвостовая

)

ну я думаю, тут речь шла о том что сам список на стек не копируется

но я все еще жду пояснений про аморт. сложность ?

С чего ты взял? Оптимизации хвостовой рекурсии в го нет, а это даже не хвостовая

оно минизерное на столько, что должно хватить на гипер гигансткие массивы. Там только указатель на функцию и индексы передаются в рек. функцию

оно минизерное на столько, что должно хватить на гипер гигансткие массивы. Там только указатель на функцию и индексы передаются в рек. функцию

Это всё результаты бенчмарков иди измерений или твои догадки? Замеры в студию

И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать

И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать

и сделал оговорку что есть исключения

И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать

и даже сказал, что внутри стандартных функций она есть

Весело у вас тут

Это всё результаты бенчмарков иди измерений или твои догадки? Замеры в студию

это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный

Проснулся в чате хаскеля

это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный

С чего это вдруг?

это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный

Давай, мне интересно посмотреть

и даже сказал, что внутри стандартных функций она есть

А где ты это говоришь?

рекурсия по памяти же неочень

рекурсия по памяти же неочень

Компилятор должен разрулить хвостовую рекурсию

это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный

хаскельный библиотечный квиксорт ничем не хуже гошного и конечно же не жрет стек

Компилятор должен разрулить хвостовую рекурсию

не все могут это сделать

рекурсия по памяти же неочень

Да вообще-то нормально по памяти

не все могут это сделать

Не проблема тех, кто может

не все могут это сделать

ага, я даже знаю один популярный язык без этой оптимизации ?

У хаскеля на хвостовой рекурсии ни с памятью проблем, ни с переполнением стека

Так что о чём разговор вообще

Так что о чём разговор вообще

так про квиксорт же

где там хвостовая рекурсия?

Не проблема тех, кто может

не думаю что проблемы говнокода лучше перекладывать на компилятор

не думаю что проблемы говнокода лучше перекладывать на компилятор

Говнокод тут вообще не причём

ERROR: S client not available

да и циклы хоть и выглядят страшно, но простые

простые для человека, который привык к ним

так про квиксорт же

И?

рекурсия натуральнее если у тебя математическое мышление

что И?

индукция, все дела

И?

в рекурсивном квиксорте нет хвостовой рекурсии

да и циклы хоть и выглядят страшно, но простые

Не всегда. Не все рекурсивные алгоритмы преобразуются в красивые циклы

плюс циклы не являются абстрагируемой единицей и строго процедурны

короче говоря - не подлежат генерализации и не очень вписываются в современное ПО

плюс циклы не являются абстрагируемой единицей и строго процедурны

о, ща за ооп срач пойдет

как там у вас, слышал дженерики завезли наконец-то

Скорее за ФП, хотя он и так уже идёт

фп заебись

как там у вас, слышал дженерики завезли наконец-то

Ой, нехорошее слово на д, ща забанят

фп заебись

Но в тру фп нету циклов

циклы не нужны

как жить то без них?

как жить то без них?

Рекурсивные функции.

любой цикл можно представить в виде рекурсии и наоборот

как жить то без них?

в жаве есть streams

А причём тут ФП и golang? Там же кроме замыканий ничего нельзя.

зачастую цикл вообще можно заменить специальными функциями для обработки структур данных. типа filter, map, reduce и тд

да по фигу как написана стандартная сортировка. Это вообще не в тему здесь

Ну то есть: - рекурсия это плохо - очень плохо - она ест память - процессор - стек Если только она не написана авторами го. Тогда она прекрасна

Шок: рекурсия ест процессор

Ну то есть: - рекурсия это плохо - очень плохо - она ест память - процессор - стек Если только она не написана авторами го. Тогда она прекрасна

Сэр, вы ходите по охуенно тонкому льду. Бывают рекурсии без возрастания стека.

Сэр, вы ходите по охуенно тонкому льду. Бывают рекурсии без возрастания стека.

Это уже выяснили.

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

да по фигу как написана стандартная сортировка. Это вообще не в тему здесь

Это именно в тему того, что рекурсию можно применять, если она удобна А она бывает удобна, и не только в стд Невероятно, но факт