14 Jan
2011
14 Jan
'11
5:58 a.m.
On Fri, Jan 14, 2011 at 11:06 AM, Ross Paterson
I've also had no success in speeding it up. It's disappointing that having the extra information (whether the key was there or not) doesn't help, but I think I agree.
I think the problem is that you get almost 2x allocation. O(log n) allocation to create the Path and O(log n) allocation to rebuild the tree. Perhaps one could use continuations to create the whole instead of reifying the stack as a Path? We might lose the ability to get the smaller/larger elements but at least we might be able to update the "hole" efficiently? Johan