3 ms·
Even 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 hun
by jdmichal 10y ago
Even 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.