Thanks for the responses! On Thu, Jan 14, 2010 at 12:23 AM, Daniel Stutzbach <dan...@stutzbachenterprises.com> wrote: > Your guess is correct. Someday I'd like to rewrite HeapDict in C for speed, > but I haven't been able to find the time (and no one has offered to pay me to > make the time ;) ).
Daniel, did you realize you can accomplish logarithmic-time priority change (albeit indirectly) with the built-in heapq module using this mark-as-invalid trick? Are there other algorithms requiring decrease- key besides A* and Dijkstra where this technique doesn't help? On Thu, Jan 14, 2010 at 2:41 AM, Mikael Lind <ele...@elemel.se> wrote: > If I recall correctly, avoiding the linear search did wonders for > algorithm complexity. It's still possible to perform the decrease-key operation without having to do a linear search; heapdict does it in logarithmic time. If my cursory benchmarks were accurate (which upon reconsideration I'm not actually sure they are), I think the only explanation for it being possibly slower is that it's running in pure Python. I just switched back to using heapq but now with the mark-as-invalid trick instead of the linear scan, and the performance I'm observing is very close to heapdict's. Which is curious, because now that both operations are running in logarithmic time, I'd expect the heapq implementation to be much faster since it's written in C. Maybe I have some confounding variables in how I'm running my tests. By the way, I just realized that the obvious reason the heapq module doesn't support priority change is that its functions are designed to operate on external lists rather than providing an encapsulating data structure like heapdict. With heapdict, logarithmic decrease_key is possible because it's also storing the positions of the elements in an underlying dictionary, so instead of a linear scan it does a constant- time lookup. My guess is that the simplicity of having heapq operate on external lists is preferable to supporting decrease-key directly, so it isn't likely to change any time soon, especially since you can accomplish the same thing with the mark-as-invalid technique. Raymond, do you think this technique is worth documenting in the heapq module? It'd be too bad if any future users incorrectly think that it won't meet their needs the way I did. -- http://mail.python.org/mailman/listinfo/python-list
