Just having some fun
Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check.
So as far as I understand, it's pretty rare, so can be ignored.realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check. We'd be creating new items (without children obviously) for all other cases. So, I think the performance impact should be limited.
DeepSOIC wrote:Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?
n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.realthunder wrote:visit each children recursively (that's factorial n! maybe?)
DeepSOIC wrote:n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.realthunder wrote:visit each children recursively (that's factorial n! maybe?)
Haha, that's just O(n^2), which is a heaven of a difference compared to the factorial .realthunder wrote:Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2.