Moving list entries from one list to another
Alex Martelli
aleax at aleax.it
Sat Jul 13 17:12:06 EDT 2002
JB wrote:
...
> bigger. I thought that when f is slow, then at least the
> merging should be as fast as possible.
Wrong attitude. If f is slow enough, all that matters is
minimizing the numbers of calls to f -- everything else
is secondary and might as well be optimized for clarity
and simplicity instead.
> I thought that as have many entries, O(n) should mean "as
> fast as possible".
As N goes to infinity, yes. For real cases, maybe, and maybe
not. If f(x) selects few enough x's, my first suggestion may
be generally preferable -- even though its WORST CASE
(that's what big-O notation is generally about...!) is O(N log N)
rather than O(N). How often is the worst case encountered,
and what are the multiplicative constants in play...?
Alex
More information about the Python-list
mailing list