Hacker News new | comments | ask | show | jobs | submit login

> 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))

    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)

Thanks for the thorough analysis--you answered several of the follow-up questions I might have had.

What is the time to actually run the iterator to the end and extract and print the solutions?

As 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

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact