timing puzzle

[Robin Becker]

Chris Mellon wrote:
........
> 
> remove() does a linear search to find the item to remove, so it's O(n)
> + the actual deletion. Append() is amortized O(1) (overcommit). If you
> delete by index instead:
> for idx, node in active_nodes:
>   if cond:
>     del active_nodes[idx]
> 
> 

that's what I was missing; my indexed deletes avoid the linear search. I 
was looking only at the data movements

> You should see performance comparable to your second option. If you
> can trade memory for performance, discarding the old active_nodes
> might be even faster:
> active_nodes = [node for node in active_nodes if node not in
> deleted_nodes], where deleted_nodes is a set.
> 
> 
> Normal micro-optimization techniques apply here too, like looking up
> the remove() method ahead of time and so on.
>.....

yes indeed and they'll start to count if I can eliminate the main 
problem areas.
-- 
Robin Becker