concise code (beginner)
rhamph at gmail.com
Fri Sep 7 18:46:00 CEST 2007
On Sep 6, 1:56 pm, Karthik Gurusamy <kar1... at gmail.com> wrote:
> That said, it may be a good future language enhancement to define a
> reasonable consistent behavior for an iterator over a changing
> collection. This occurs quite common when we walk a collection and
> usually delete the current item.
> For a sequence, what the expected behavior is quite obvious (just
> remove this element and go over to the next). For other collections
> like dictionary/set, again if the operation is delete, the expected
> behavior is obvious. If we are doing insertion, for sequence a well-
> defined behavior can be formulated (based on insert before or after
> current position -- if after we will see it in the walk, if before we
> won't see it) . For dict/set I see this isn't simple (as based on hash
> key we may insert ahead or later of the current 'cursor'/position.
Removing from a list while you iterate will had quadratic performance
though. O(n) to find the element you wish to remove and move over
everything after it, multiplied by your original O(n) of iterating,
gives O(n**2). That, combined with the fact that adding enough
accounting to invalidate or update your iterator would be a cost on
all the correct users too, is why it's not done.
The best approach in almost all cases in python is to create a new
container as you iterate over the old one. After you finish, you
replace the old one with the new one. This lets you keep an overall
O(n) performance, as well as avoiding the tricky semantics.
Adam Olsen, aka Rhamphoryncus
More information about the Python-list