В хаскеле с оптимизацией хвоста не всё так просто из-за лени.

Тут я уже вмешаюсь Pawel, приведите результаты бенчмарка, иначе чем вы лучше тех, кого вы ругаете за отсутствие примеров?

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

Господа, топящие за рекурсию. Приведите код быстрой сортировки с рекурсией, или вы пустые болтуны

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

этот код не эффективен. гошня, да и любая итеративная реализация быстрой сортировки работает быстрее и с меньшими затратами по памяти.

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

То есть бенчмарков нету Ну, всё ясно

То есть бенчмарков нету Ну, всё ясно

https://play.rust-lang.org/?gist=75342b7290702231c4a42ad920d35d2b&version=stable&mode=debug&edition=2015

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

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

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

не знаю на счёт аморт. сложности, но этот код не читается проще аналогичного гошного

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

Вам, как человеку якобы пишущему высокопроизводительные приложения, следовало знать, что О большое вообще говоря не определяет скорость алгоритма, а определяет увеличение сложности при росте каких-то параметров Ничто не мешает алгоритму O(n^3) быть быстрее алгоритма O(n^2), всё зависит от кучи условий

при таких сравннеиях алгоритмов на разных языкакх нет вообще ни каких оснований считать что О на хаскиле будет меньше чем О на Го

при таких сравннеиях алгоритмов на разных языкакх нет вообще ни каких оснований считать что О на хаскиле будет меньше чем О на Го

И что?

Я бы вообще не стал бы делать никаких предположений о виде роста сложности, учитывая что у нас идёт оптимизация на каждом слое: от трансляции до исполнения на функциональных блоках И это ещё без учета кэшей и предективной выгрузки из памяти

Давай ты напишешь такой же алгоритм на го, не in place и убедишься на сколько там все проще

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

Так нас интересует сложность реализации или производительность кода? Вы уж определитесь

не производительность бинарника, а гарантии по аморт. сложности

не производительность бинарника, а гарантии по аморт. сложности

не производительность бинарника, а гарантии по аморт. сложности

Нет никаких гарантий

Есть гарантии - O (n * log n) и O(1) по памяти. "Простой" алгормитм на хаскеле их не даёт, и по фигу что О может быть разным

"Простой" алгоритм на хаскеле не является квиксортом, это каждому первокурснику очевидно

Есть гарантии - O (n * log n) и O(1) по памяти. "Простой" алгормитм на хаскеле их не даёт, и по фигу что О может быть разным

"Простой" алгоритм на хаскеле не является квиксортом, это каждому первокурснику очевидно

честно говорят алгоритмы с нуля это какая то узкая совсем ниша

?

Да? Так вас всё таки интересует потребление памяти, а не скорость работа или простота реализации? А у вас есть результаты замеров?

я правильно понимаю что тут обсуждается тот факт, что рекурсивный qsort на иммутабельном списке менее предпочтителен чем inplace? 🙂

я правильно понимаю что тут обсуждается тот факт, что рекурсивный qsort на иммутабельном списке менее предпочтителен чем inplace? 🙂

у алгоритма быстрой сортировки есть свойства, которым "простой" алгоритм на хаскеле не удовлетворяет

и на этом основании делается выовод что хаскель - отстой? )))

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

Например?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оно хз какое

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

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

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

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

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

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

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