Piet van Oostrum wrote:
Douglas Alan <darkwate...@gmail.com> (DA) wrote:
DA> On Jul 13, 3:57 pm, a...@pythoncraft.com (Aahz) wrote:
Still, unless your list is large (more than thousands of elements),
that's the way you should go. See the bisect module. Thing is, the
speed difference between C and Python means the constant for insertion
and deletion is very very small relative to bytecode speed. Keep in
mind that Python's object/binding model means that you're shuffling
pointers in the list rather than items.
DA> Thank you. My question wasn't intended to be Python specific, though.
DA> I am just curious for purely academic reasons about whether there is
DA> such an algorithm. All the sources I've skimmed only seem to the
DA> answer the question via omission. Which is kind of strange, since it
DA> seems to me like an obvious question to ask.
It may well be that there is no good simple solution, and people avoid
writing about non-existent algorithms. I certainly cannot imagine
trying to write an article that carefully covered ideas which don't
have well-studied data structures available, and calling them out
only to say, "we don't know how to do this well." If such an algorithm
were simple and obvious, I dare say you'd be taught about it around the
time you learn binary search.
Of course you can take any BST algorithm and replace pointers by indices
in the array and allocate new elements in the array. But then you need
array elements to contain the indices for the children explicitely.
And you loower your locality of reference (cache-friendliness).
Note the insert in Python, for example, is quite cache-friendly.
--Scott David Daniels
scott.dani...@acm.org
--
http://mail.python.org/mailman/listinfo/python-list
