3 ms·
At a gut shot, only concern for this would be highly dynamic trees that are not either appending or prepending elements to children. I'd be curious to see benc
by taeric 10y ago
At a gut shot, only concern for this would be highly dynamic trees that are not either appending or prepending elements to children. I'd be curious to see benchmarks checking that.
With this, I'm always bemused that there are not more discussions on algorithms for doing tree traversal that don't use a queue or a stack. I think you have everything you need here to accomplish that.
- c-smile 10y agoIt was discussed quite a loot actually. ArrayList (sciter's children list) vs LinkedList (Edge children list) : http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist http://stackoverflow.com/questions/322715/when-to-use-linked...
- taeric 10y agoI meant specifically in modeling the Dom. Apologies if that wasn't clear. The specific questions would be how often are the trees of a site dynamic and how often they insert instead of prepend or append. Edit: And, of course, I'm still interested in why more people don't use stackfree algorithms for DFS.
- c-smile 10y agoWell, almost all HTML/CSS layout algorithms are O(N) complex so number of immediate children of an element is naturally limited by, say, 500-1000 sub-nodes. Otherwise the whole thing will not move. Note that GMail uses pagination with 500-800 elements on the page. So we are speaking about vectors of pointers that contain 1000 elements. memmove() performance (used for quite rare operation of insertion of elements in the middle) on modern CPU is comparable with the need to access left/right elements in DL-lists for insertion. Consider cache misses, etc.
- taeric 10y agoThis all makes sense, but I have become ridiculously empirical in my old age. Actual data wins many arguments in ways that surprise reasoning.
- jdmichal 10y agoEven prepending... One would have to touch every sibling to update the index. So prepends are now a linear operation on the count of siblings. Prepend a few hundred items to a node, and I'm sure one would see the pain in profiling. Now, whether that's a realistic use case is another question. But at the same time, you know someone on the Internet is doing it that way...
- taeric 10y agoI was assuming you'd use a standard deque that could hide the complexity of prepending. I didn't consider that the ordinal actually matters from the parent, though. So great point! :) And yes, this was essentially my question. What are the realistic numbers in either scenario.
- jdmichal 10y agoRight. If you don't cache the ordinal, than "next sibling" and "previous sibling" operations have to scan the array. But it's a relatively easy performance enhancement to have a validity flag for the ordinals, and only rewrite them when a read requires them. That way, write-heavy workloads won't be punished.