3 ms·
Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
by rwmj 11y ago
Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears.
- masklinn 11y ago> Can someone explain why the Python version is lazy? I don't understand where the lazy generator appears. It isn't. It could be lazy if `bind` was defined as return itertools.chain.from_iterable(map(f, xs)) or for x in xs: yield from f(x) (`unit` could also be defined as `yield x` but that wouldn't make much of a difference) The provided program returns a `list` of all solutions though, not any sort of iterator, generator or otherwise. This is confirmed by the runtime being anything other than instantaneous, a lazy version would just print the repr of the lazy iterator (say `<generator object bind>`), not the actual result (unless the iterator defined an __repr__/__str__ but very very few do, and those that do have little to nothing to compute e.g. dict views) Original program: > time python3.4 test_list.py [(9567, 1085, 10652)] python3.4 test_list.py 6.43s user 0.02s system 99% cpu 6.480 total Converted to `yield from` and `yield`: > time python3.4 test_yield.py <generator object bind at 0x1066ba7e0> python3.4 test_yield.py 0.04s user 0.01s system 84% cpu 0.062 total nb: this comment assumes Python 3 is being used given the print function, Python 2 doesn't have `yield from` and you'd need `itertools.imap` as the builtin `map` is eager nb2: on my machine, reifying the lazy version has roughly the same runtime as the eager version in CPython (2.7.10 and 3.4.3), in PyPy (2.6.0 ~ CPython 2.7.9) the reified lazy version (using chain.from_iterable) runs in half the time (~3s) as CPython and the eager version runs in 1/6ths the time (~1s)
- wging 11y agoThanks for the thorough analysis--you answered several of the follow-up questions I might have had.
- mjd 11y agoWhat is the time to actually run the iterator to the end and extract and print the solutions?
- masklinn 11y agoAs indicated in the second note, in CPython (2.7 or 3.4) it's roughly the same as the eager version. In pypy the lazy version is about 3 times slower than the eager version. Version from your post: > time python2.7 test_eager.py [(9567, 1085, 10652)] python2.7 test_eager.py 6.41s user 0.02s system 99% cpu 6.451 total > time python3.4 test_eager.py [(9567, 1085, 10652)] python3.4 test_eager.py 6.28s user 0.03s system 99% cpu 6.372 total > time pypy test_eager.py [(9567, 1085, 10652)] pypy test_eager.py 0.95s user 0.06s system 98% cpu 1.022 total Using `yield from` (3.4-only) and wrapping the solutions() call in a `list()`: > time python3.4 test_yield.py [(9567, 1085, 10652)] python3.4 test_yield.py 6.28s user 0.02s system 99% cpu 6.313 total Using chain.from_iterable + imap (or map in 3.4) and wrapping the solutions() call in a `list()`: > time python2.7 test_imap.py [(9567, 1085, 10652)] python2.7 test_imap.py 6.52s user 0.02s system 99% cpu 6.558 total > time python3.4 test_imap.py [(9567, 1085, 10652)] python3.4 test_imap.py 6.26s user 0.02s system 99% cpu 6.292 total > time pypy test_imap.py [(9567, 1085, 10652)] pypy test_imap.py 2.87s user 0.06s system 99% cpu 2.943 total Versions used: Python 2.7.10, Python 3.4.3, PyPy 2.6.0 with GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.57); all from macports