ну а теперь посмотри как устроены списки в хаскеле)
так ну первый рекурсивный вызов у нас заюзает ~ 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)
саша
Pawel
Мерль
что значит "скорее всего"? оно либо будет либо не будет и асимптотической сложности это имеет прямое отношение
Неа
Учитывая что:
- у нас работает оптимизирующий компилятор
- сборщик мусора
- переупорядочивание инструкций
- кэширование данных
- кэширование инструкций
- бранч предиктор
- предиктор подкачки памяти
- куча магии
- всё это работает внутри ОС нереального времени
Я бы вообще не стал бы делать никаких сильных заявлений, особенно без экспериментов
Мерль
)
David
ого, (не хвостовая) рекурсия без потребления стека, это как?
Мерль
но не такую как в хакеле, без потребления стека
С чего ты взял?
Оптимизации хвостовой рекурсии в го нет, а это даже не хвостовая
Мерль
)
David
ну я думаю, тут речь шла о том что сам список на стек не копируется
David
но я все еще жду пояснений про аморт. сложность 🙂
Pawel
С чего ты взял?
Оптимизации хвостовой рекурсии в го нет, а это даже не хвостовая
оно минизерное на столько, что должно хватить на гипер гигансткие массивы. Там только указатель на функцию и индексы передаются в рек. функцию
Мерль
оно минизерное на столько, что должно хватить на гипер гигансткие массивы. Там только указатель на функцию и индексы передаются в рек. функцию
Это всё результаты бенчмарков иди измерений или твои догадки?
Замеры в студию
Мерль
И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать
Pawel
И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать
и сделал оговорку что есть исключения
Pawel
И да, кто-то, не помню кто, говорил недавно что никто нормальный не будет использовать рекурсию, что всегда лучше переписать
и даже сказал, что внутри стандартных функций она есть
Dorian
Весело у вас тут
Pawel
Это всё результаты бенчмарков иди измерений или твои догадки?
Замеры в студию
это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный
Dorian
Проснулся в чате хаскеля
Алексей
Мерль
Мерль
это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный
Давай, мне интересно посмотреть
Olzhas
рекурсия по памяти же неочень
David
это кстати можно. хаскильный квиксорт на значительно меньшем массиве упадёт с SO чем гошный
хаскельный библиотечный квиксорт ничем не хуже гошного и конечно же не жрет стек
Диёр
У хаскеля на хвостовой рекурсии ни с памятью проблем, ни с переполнением стека
Диёр
Так что о чём разговор вообще
David
где там хвостовая рекурсия?
Алексей
не думаю что проблемы говнокода лучше перекладывать на компилятор
Говнокод тут вообще не причём
Olzhas
да и циклы хоть и выглядят страшно, но простые
Aliester
простые для человека, который привык к ним
Aliester
рекурсия натуральнее если у тебя математическое мышление
David
что И?
Aliester
индукция, все дела
Алексей
да и циклы хоть и выглядят страшно, но простые
Не всегда. Не все рекурсивные алгоритмы преобразуются в красивые циклы
Aliester
плюс циклы не являются абстрагируемой единицей и строго процедурны
Aliester
короче говоря - не подлежат генерализации и не очень вписываются в современное ПО
Aliester
как там у вас, слышал дженерики завезли наконец-то
Алексей
Скорее за ФП, хотя он и так уже идёт
Olzhas
фп заебись
David
циклы не нужны
Lucky
как жить то без них?
Aliester
любой цикл можно представить в виде рекурсии и наоборот
Co(n)stantine👨🔬
Marperia
А причём тут ФП и golang? Там же кроме замыканий ничего нельзя.
Alexander
зачастую цикл вообще можно заменить специальными функциями для обработки структур данных. типа filter, map, reduce и тд
Pawel
Мерль
Vladimir
Шок: рекурсия ест процессор
Marperia
Ну то есть:
- рекурсия это плохо
- очень плохо
- она ест память
- процессор
- стек
Если только она не написана авторами го. Тогда она прекрасна
Сэр, вы ходите по охуенно тонкому льду.
Бывают рекурсии без возрастания стека.
Алексей
David
особенно плохо, когда она написана на хаскеле, на хаскеле она есть в nlogn раз больше памяти и процессоров
Мерль
да по фигу как написана стандартная сортировка. Это вообще не в тему здесь
Это именно в тему того, что рекурсию можно применять, если она удобна
А она бывает удобна, и не только в стд
Невероятно, но факт
Aliester
особенно плохо, когда она написана на хаскеле, на хаскеле она есть в nlogn раз больше памяти и процессоров
процессор распознает хаскель
Aliester
и специально работает медленнее
Marperia
Только это скорее lisp и haskell. Причёт тут go вообще? Или кто-то научился функционально на нём писать?
Vladimir
Сэр, вы ходите по охуенно тонкому льду.
Бывают рекурсии без возрастания стека.
Рекурсия написанная авторами го имеет -10 к возрастанию стека
Pawel
Это именно в тему того, что рекурсию можно применять, если она удобна
А она бывает удобна, и не только в стд
Невероятно, но факт
бывает, но крайне редко. Её всегда можно переписать через циклы, это в 99% случаев это будет лучше читаться и эффективней работать
Алексей
Алексей
Стек реализованный руками вообще никогда не будет лучше читаться
Pawel
Это именно в тему того, что рекурсию можно применять, если она удобна
А она бывает удобна, и не только в стд
Невероятно, но факт
ты так гоовришь как будто ты единственный тут читал SICP а я типа не читал, а просто так набрасываю
Aliester
99%
Cat
Cat
мне для школы