multiset solution commenting questiong
Author Message
c1wangjj Offline

Reputation: 0
Post: #1
multiset solution commenting questiong
this is from multiset solution line 196

if self.count(e) > other.count(e):
# It is potentially dangerous to modify a collection while
# iterating over it. But it is safe in this case, because of
# the modifications we made to the SkipList iterator: when we
# remove element e, the iterator has already moved past that
# element and will not be affected.

it says because the iterator has already moved past the removed element, is that because line 371 is before line 372 in skiplist solution?:

item = self.current.item (this line is before the next line)
self.current = self.current.right
2013-05-07 00:20
Find all posts by this user Quote this message in a reply
fpitt Offline

Reputation: 13
Post: #2
RE: multiset solution commenting questiong
The important thing to understand here is the way in which the for loop works with the iterator, and how that interacts with the changes we are making to the list. When Python executes a for-loop, like "for e in self.skiplist:", an iterator object gets created. This object is managed directly by Python— it does not get stored in any variable that we can access directly. In essence, the for-loop
for e in self.skiplist:
    ...loop body (making use of local variable e)...
is equivalent to the following
i = iter(self.skiplist)  # calls special method self.skiplist.__iter__()
while True:
        e = next(i)  # calls special method i.__next__()
    except StopIteration:
        break  # terminate the while-loop
    ...loop body (making use of local variable e)...

Now, the iterator object that gets created is an instance of our class SkipIter: this object keeps a reference self.current to one node on the bottom level of the skip list, and each time its __next__ method is executed, this reference is moved forward to the next node.

The problem with this is that, within the body of the loop, we might delete the node that stores the item e. If the iterator's current attribute really did refer to the node at the bottom level storing item e, then this could be a problem because it would mean the iterator's current attribute might refer to an object that has already been "cleaned up" by Python's garbage collection mechanism!

However, we anticipated this and wrote our iterator class so that its current attribute always refers to the next node in the skip list (the one immediately following the item returned by method __next__). This means that it's OK to delete the node that contains e without affecting the iterator.

To be honest, this is not a very good design! Smile The reason is that it is very sensitive to understanding this subtle interplay of the different methods with each other— meaning anyone who tries to make a change to the code might run into some unpleasant surprises if they do not understand how it all works. It would be "messier" but better to rewrite method __iand__ in class MultiSet so that it does not depend on this property of the iterator.
2013-05-07 10:17
Visit this user's website Find all posts by this user Quote this message in a reply
Post Reply 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5

Forum Jump:

User(s) browsing this thread: 1 Guest(s)