p
Со стеком. Ну то есть эмуляция стека вызовов руками, зачем только — непонятно.
Потому что у рекурсии есть лимит
Size: a a a
2020 September 10
p
У тебя вообще все задачи про дереаья
NL
Потому что у рекурсии есть лимит
Рекурсия может быть хвостовая, это раз. И у стека в куче тоже есть лимит, это два.
B
В мейне еще обсуждали вопрос поднятия лимита стека, но это изврат
NL
Ого, нормальный такой список, спасибо!!! Столько написал.
Про ханойские я и забыл😅
Про ханойские я и забыл😅
https://nlinker.github.io/presentations/06_advanced-data-structures-2/
Там есть слайд Functional RB tree, insert
Там есть слайд Functional RB tree, insert
B
А если дерево адекватной глубины то стека нативного за глаза обычно
B
https://nlinker.github.io/presentations/06_advanced-data-structures-2/
Там есть слайд Functional RB tree, insert
Там есть слайд Functional RB tree, insert
Ну деревя я тоже хочу дать, но по позже, буду чет простое придумывать)
p
Рекурсия может быть хвостовая, это раз. И у стека в куче тоже есть лимит, это два.
Тебе трудно будет достичь лимита на куче, а лимита рекурсии вполне реально
EG
https://nlinker.github.io/presentations/06_advanced-data-structures-2/
Там есть слайд Functional RB tree, insert
Там есть слайд Functional RB tree, insert
Это неинтересное дерево
Интересное было бы дерево на идрисе с статической верификацией того, что оно действительно красно-чёрное
Интересное было бы дерево на идрисе с статической верификацией того, что оно действительно красно-чёрное
p
Это неинтересное дерево
Интересное было бы дерево на идрисе с статической верификацией того, что оно действительно красно-чёрное
Интересное было бы дерево на идрисе с статической верификацией того, что оно действительно красно-чёрное
О
p
Этим и займусь
p
Потом
NL
Тебе трудно будет достичь лимита на куче, а лимита рекурсии вполне реально
Не, ну просто можно на стеке хранить указатели. И лимит действительно можно увеличить так, что для практических нужд хватит более чем.
Если у тебя глубина AST превышает 1 миллиона (насколько я знаю, дефолтный стек равен 8Мб), значит тут явно что-то не так. И всегда можно контролировать глубину рекурсии через глобальную переменную и вызывать кастомную обработку переполнения рекурсии, если уж так надо.
Если у тебя глубина AST превышает 1 миллиона (насколько я знаю, дефолтный стек равен 8Мб), значит тут явно что-то не так. И всегда можно контролировать глубину рекурсии через глобальную переменную и вызывать кастомную обработку переполнения рекурсии, если уж так надо.
p
Не, ну просто можно на стеке хранить указатели. И лимит действительно можно увеличить так, что для практических нужд хватит более чем.
Если у тебя глубина AST превышает 1 миллиона (насколько я знаю, дефолтный стек равен 8Мб), значит тут явно что-то не так. И всегда можно контролировать глубину рекурсии через глобальную переменную и вызывать кастомную обработку переполнения рекурсии, если уж так надо.
Если у тебя глубина AST превышает 1 миллиона (насколько я знаю, дефолтный стек равен 8Мб), значит тут явно что-то не так. И всегда можно контролировать глубину рекурсии через глобальную переменную и вызывать кастомную обработку переполнения рекурсии, если уж так надо.
Не понял
p
Дерево храни как угодно
p
Обработка через стек
p
Что не так?
NL
Не понял
Ты делаешь рекурсивный вызов (не хвостовой), у тебя фрейм кладётся на стек. Можно просто фрейм уменьшить до минимума, храня просто указатель на объект в куче с текущими данными.
Сейчас подумал, да, мы в сущности говорим об одном и том же.
Сейчас подумал, да, мы в сущности говорим об одном и том же.
T1
Через цикл часто намного быстрее на современных компьютерах
NL
Через цикл часто намного быстрее на современных компьютерах
Это если ты обрабатываешь массив, то да. А если дерево — то что-то неочевидно, цикл будет постоянно спотыкаться об if-ы и сбрасывать кэш объектами, которые эмулируют фреймы.