Douglas Alan <darkwate...@gmail.com> writes: > I can't see that a binary search tree would typically have > particularly good cache-friendliness, so I can't see why a flat-array > representation, such as is done for a binary heap, would have > particularly worse cache-reference.
That is a good point. Maybe we should be paying more attention to cache-oblivious algorithms. http://en.wikipedia.org/wiki/Cache-oblivious_algorithm H. Prokop's masters' thesis cited in the wiki article explains the subject very well. A fair amount of work has been done on it since then, but not as much as one might expect. -- http://mail.python.org/mailman/listinfo/python-list
