Created
February 6, 2011 10:02
-
-
Save rik0/813271 to your computer and use it in GitHub Desktop.
Trace of lazy set implementation in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Copyright (C) 2011 by Enrico Franchi | |
# | |
# This file is released under the terms of the MIT license | |
# http://www.opensource.org/licenses/mit-license.php | |
import itertools as it | |
def silence_generator_already_executing(generator): | |
try: | |
for element in generator: | |
yield element | |
except ValueError, e: | |
pass | |
class lazy_set(object): | |
""" | |
Trace of implementation of lazy sets in Python. | |
""" | |
def __init__(self, input_=[]): | |
self.input_ = iter(input_) | |
self.seen = set() | |
def _iter(self): | |
for element in self.input_: | |
if element in self.seen: | |
continue | |
else: | |
yield element | |
self.seen.add(element) | |
def add(self, obj): | |
self.seen.add(obj) | |
def update(self, iterator): | |
self.input_ = it.chain(self.input_, | |
silence_generator_already_executing(iterator)) | |
def __iter__(self): | |
return it.chain(self.seen, self._iter()) | |
if __name__ == "__main__": | |
import doctest | |
doctest.testmod() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import unittest | |
import lazy_set | |
class LazySetTest(unittest.TestCase): | |
def setUp(self): | |
self.lazy_set = lazy_set.lazy_set(xrange(1, 4)) | |
self.starting_value = range(1, 4) | |
def testCreation(self): | |
self.assertEqual( | |
sorted(self.lazy_set), | |
self.starting_value | |
) | |
def testUpdate(self): | |
self.lazy_set.update(2* x for x in range(4, 10)) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
[1, 2, 3, 8, 10, 12, 14, 16, 18] | |
) | |
def testAdd(self): | |
self.lazy_set.add(5) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
[1, 2, 3, 5] | |
) | |
def testUniqueness(self): | |
self.lazy_set.update(xrange(5)) | |
self.lazy_set.update(xrange(3, 8)) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
range(8) | |
) | |
def testSelfUpdateWIter(self): | |
self.lazy_set.update(iter(self.lazy_set)) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
self.starting_value | |
) | |
def testSelfUpdateWOIter(self): | |
self.lazy_set.update(self.lazy_set) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
self.starting_value | |
) | |
def testSelfUpdateNotLats(self): | |
self.lazy_set.update(iter(self.lazy_set)) | |
self.lazy_set.update(xrange(5, 8)) | |
self.assertEqual( | |
sorted(self.lazy_set), | |
range(1, 4) + range(5, 8) | |
) | |
if __name__ == '__main__': | |
unittest.main() |
Please, do not consider my last post as "this kind of stuff is not relevant". It is good to consider readability, style and efficiency (in this order) when writing code. It is the only way to improve. In pair programming, it would be the navigator to consider these issues.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You asked if they were redundant (No longer needed or useful; superfluous;Able to be omitted without loss of meaning or function).
The answer to that question is no. They cannot be omitted without loss of meaning or function.
What I now understand you meant is: can that functionality provided using less lines of code? The answer is "yes". The code you provided is essentially equivalent on (cPython you save 3 vm operations).
However, this kind of stuff is rather unimportant: I wrote it this way for no reason that there is less code to change should we seriously change the definition. As I said, I'm not sure I'm not missing something. I do not even believe the code is perfectly correct; as a consequence micro optimizations are premature.
Moreover, in cases just less trivial than this (here a formal proof is feasible) it is not wise to change code (in particular for micro-optimizing) without a full set of unit tests which would catch freshly introduced bugs.
But the short story is: yes. You could have written that way.