Tree

Рекурсия переполняет стек, создаваемый автоматически в статической памяти. Потому она заменяется на цикл и стек, создаваемый вручную в памяти динамической.

Это какое должно быть дерево чтобы стек переполнить?

А ты думаешь он бесконечный что ли?

На каких ЯП вы это делаете?

На тех, на которых приложение.

как вы обходитесь без TCO?

Очевидно не на всех задачах деревья очень большие. Ну и если допустим дерево хранится в бд, а не загружается полностью в память, то ТСО тут вообще ни при чем, а вопрос в том, как хранить дерево в БД.

В контексте деревьев, если не быдлокодить, можно в первом приближении считать что да. Даже если дерево двоичное (самый плохой для рекурсии случай), то на 1 трлн элементов надо всего лишь 40 этажей (ну ладно пусть оно несбалансированное совсем и этажей будет 100). Переполнить стек 100 рекурсивными вызовами это надо очень постараться. У себя проверил - рекурсия падает после 8мбайт занятого стека (на дефолтном gcc в debian11 32bit).

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

А, ну да. Я почему-то думал про дерево которое внутри своего софта используешь.

когда тебе деревья идут в качестве данных… неожиданно… надо проверять глубину рекурсии. если глубина >10^4(например), просто надо ругнуться и прекратить их обработку, ибо понятно, что это злые люди постучались.

правильный код никаким данными не взломаешь.

правильные посоны ВСЕГДА проверяют глубину рекурсии, и не только на деревьях, иначе оно может плохо кончится.

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

если глубина >10^4(например)

Вспомнилось: 640 килобайт хватит всем.

Очень плохое решение, если это хардкодить, и не менее плохое, если выносить в конфиг.

На каких ЯП вы это делаете?

На любых. Сложно представить слоль-либо серьёзный ЯП без реализации деревьев и библиотек для работы с ними.

TCO

У меня Гугл это в первых результатах показывает: https://en.wikipedia.org/wiki/Total_cost_of_ownership.

Пишете все обходы итеративно?

Зависит от дерева. Для некоторых деревьев, например AVL гарантируется логарифмическая глубина, так что скорее вся память кончится, чем стек переполнится.

Очень плохое решение, если это хардкодить, и не менее плохое, если выносить в конфиг.

никакой не конфиг. этот лимит на реальных данных достичь невозможно.

приведите пример когда такое может случится. это вложенность. таких вложенностей не бывает. уже 100 - малореально. это 2^100 для сбалансированного дерева

никакой не конфиг. этот лимит на реальных данных достичь невозможно.

Зато вполне возможно, что на целевой платформе или конфигурации приложения стек окажется существенно меньше, и эта проверка будет бесполезной.

что на целевой платформе

я что 10^4 гвоздями прибил? берите 1000 например. если у вас на целевой платформе мало памяти вас вообще ничто не спасет. итерация имеет смысл при рекурсиях на списках, а на деревьях она выгрыша не дает.

а деревья, вырожденные в список - это явно ошибка представления. их надо или балансировать или хешировать ключи.

У вас не проводят тестирование перед принятием на эксплуатацию?

я что 10^4 гвоздями прибил?

Прибили. Независимо от конкретного числа. Подумайте, почему.

если глубина >10^4(например), просто надо ругнуться

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

можете поставить макс глубину в 100. для сбалансированного бинарного дерева это 10^30. если этого мало - возьмите 200. тогда будет 10^60. если дерево что может содержать 10^60 элементов, и у вас переполнение по глубине - значит у вас где-то неправильный код.

с рекурсивными типами работают на функциональных ЯП. У них там для этого своя кухня, сильно оптимизирующая весь процесс (анализа, разработки и исполнения).

но у вас же не про это вопрос ? :-)

никакой не конфиг. этот лимит на реальных данных достичь невозможно.

Например, прочитать AST. Больше 10^4 операций — не очень большая программа.

На каких ЯП вы это делаете?

На Racket. Стек может занимать всю доступную память. И TCO есть.

Например, прочитать AST. Больше 10^4 операций — не очень большая программа.

глубина рекурсии на дереве, в том числе AST - это вложенность! это все равно, что написать код, где if вложены 10^4 раз.

  if(..) {
    if(..) {
      if(..) {
      ... //повторить 10 тыщ раз
      }
    }
  }

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

глубина рекурсии на дереве, в том числе AST - это вложенность! это все равно, что написать код, где if вложены 10^4 раз.

stmt1; stmt2; stmt3; stmt4

==

      seq 
stmt1          seq 
         stmt2          seq 
                 stmt3      stmt4

как вы обходитесь без TCO? Пишете все обходы итеративно?

Используем имеющуюся обобщенную реализацию обхода деревьев (например, функции из clojure.walk). Как она там внутре работает — вопрос больше академический, чем практический.

Как говорил классик, можешь не писать — не пиши.

stmt1; stmt2; stmt3; stmt4

это список, а не дерево. abstract syntax tree никакое не бинарное дерево, а структура с нодой вида, порождающей список.

struct NodeBase {
  NodeBase *_next; //следующий
}

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

struct NodeChilds: public NodeBase {
  NodeBase *_childs; //первый локальный
}

и вложенность AST будет примерно равна синтаксической вложенности вашего текста…

в вашем случае вложенности нет вообще, это последовательный список операторов.

обычно вложенность не превышает и 10.

чтобы породить сильно вложенное AST надо написать примерно так

struct A{
  struct {
    struct {
    ....
    } b
  } c;
}

а структура с нодой вида, порождающей список

Так список является деревом к вложенностью, равной длине списка.

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

У gcc в AST составное выражение имеет только одного ребёнка — первое выражение в цепочке, а то также имеет одного ребёнка и т.д.

http://icps.u-strasbg.fr/~pop/images/compound-stmt.png

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

составное выражение это просто список выражений. а вот например оператор

if (Condition) Statement;

это нода примерно вида:

struct if_operator : public NodeBase {
  Expr* _condition;
  Statement* _statements;
}

ты не видишь что там сами statements в списке? горизонтальные стрелки там на что?

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

рекурсией будет обрабатываться вложенный составной оператор. тогда будет нода с чайлдами и у нее свои дети в виде списка.

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

На языке с ТСО обход единообразен. А так у тебя два взаимнорекурсивных обхода. Но согласен, так можно выкрутиться.

Нормальное решение имхо, просто само число зависит от задачи. Sane data limit всегда нужен

На языке с ТСО обход единообразен.

чтобы получить твое tco(tail call optimization), надо еще код правильно написать. в с++ любой обьект с нетривиальным деструктором на стеке, в данном блоке или охватывающем, снесет эту оптимизацию, поскольку будет скрытый код вызова деструкторов. аналогично будет если будет defer в языках, где он есть.

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

от функциональщиков вред один!

чтобы получить твое tco(tail call optimization), надо еще код правильно написать.

В нормальном языке (со сборщиком мусора) работает всегда. Хоть в лиспе, хоть в хаскеле.

от функциональщиков вред один!

Если они пытаются писать на С++ как привыкли, то да.

это 2^100 для сбалансированного дерева

Ключевое слово — «сбалансированного». ;)

а деревья, вырожденные в список - это явно ошибка представления. их надо или балансировать или хешировать ключи.

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

Ключевое слово — «сбалансированного». ;)

ключевое слово - адекватность представления структуре данных.

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

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

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

Если для вас деревья всегда сбалансированы, это говорит лишь о малом опыте построения сложных алгоритмов.

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

какими «алгоритмами» вы там овладели, чтобы нести лютую пургу?

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

«для хранения вложенных структурированных данных»

Неужели так трудно представить ситуацию, когда эти самые данные не ложатся на список, а представляются далеко не сбалансированным деревом?

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

какими «алгоритмами» вы там овладели, чтобы нести лютую пургу?

Нет, ну если тебе 20 лет и все деревья либо красно-чёрные, либо имеют глубину не больше 10^4, то я несу «лютую пургу», конечно :D

Неужели так трудно представить ситуацию, когда эти самые данные не ложатся на список, а представляются далеко не сбалансированным деревом?

учитесь читать. балансируются деревья для «бинарного поиска».

деревья, отражающие структуру, не балансируются, ибо отражают структуру!!! AST не балансируется, ибо это нарушит структуру программы.

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

ну представьте структуры вложенности 10^4, и покажите предметную область, где такое возникает. флаг в руки.

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

Это же не я как раз мешаю :)

ну представьте структуры вложенности 10^4, и покажите предметную область, где такое возникает. флаг в руки.

Ну, например, вы хотите моделировать поведение какой-то сложной системы с помощью ациклического случайного Марковского поля. Древовидную структуру вы получаете из большой выборки с помощью метода Chow-Liu. Никаких гарантий на глубину этого дерева, разумеется, нет.

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

Никаких гарантий на глубину этого дерева, разумеется, нет.

а гарантии на бесконечный размер стека у вас есть???

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

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

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

вы как будете обходить свое дерево?

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

Ну, я-то умею обходить дерево и без рекурсии.

Это вы, видимо, не умеете и закатываете истерику про

таких вложенностей не бывает. уже 100 - малореально. это 2^100 для сбалансированного дерева

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

Обработать ациклическое Марковское поле из 10^7 переменных — плёвая задача на любом современном десктопе.

Обработать ациклическое Марковское поле из 10^7 переменных — плёвая задача на любом современном десктопе.

каким-то там рекурсивным алгоритмом? вы же сами говорили что «будут проблемы»

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

ваши утверждения несовместны. сначала вы говорите что будут проблемы, потом говорите, что плевое дело.

значит какое-то из утверждений или ложно или нечетко сформулировано. вы не привели никакой конкретики вообще.

каким-то там рекурсивным алгоритмом? вы же сами говорили что «будут проблемы»

Проблемы будут у тех, у кого деревьев глубже 10^4 не бывает.

значит какое-то из утверждений или ложно или нечетко сформулировано. вы не привели никакой конкретики вообще.

Я описал вполне конкретную ситуацию, когда возникают деревья глубже 10^4. Естественно, для их обработки я не буду использовать рекурсию и проблем у меня не будет, покуда оперативки хватит.

Проблемы будут у тех, у кого деревьев глубже 10^4 не бывает.

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

какой глубины деревья

Аааа в Африке деревья вот такой глубины!
Аааа в Африке реки вот такой вышины!

P.S. И зеленый попугай.

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

Несколько миллионов вершин, в стек не влазили.

ЗЫ вообще, плохая практика на «этим способом трудно или нельзя делать X» отвечать «X делать нИнужно!»

Несколько миллионов вершин, в стек не влазили.

вы верно понимаете вопрос? бинарное сбалансированное дерево в «несколько миллионов вершин», это дерево глубиной всего-то 20

я про глубину, а вы про число вершин

Дерево не было ни бинарным, ни сбалансированным.

Дерево не было ни бинарным, ни сбалансированным.

максимальная глубина от его какая? очевидно что «число вершин», это не ответ. если у вас число вершин есть глубина, то это список.

бинарное как и любое дерево тоже легко выродить в список. но это скорей говорит либо о неверном с ним обращении, либо о каких-то особенных, экстремальных данных некого класса, который стоит оговорить.

я вот не понимаю, когда ваше чоу-лю дерево вырождается в список. это же какое-то нестандартное поведение данных.