Notebook

I. Introductions¶

II. Functions vs Generators (vs Generator Expressions vs Iterables)¶

Functions¶

A typical function definition looks like the below. In this case, we return two values as a tuple. We use this function by calling it with (). In Python, functions are generalised as "callables" and support the __call__ protocol. Many different things are callables (classes, C-functions, generators, &c.)

In [7]:

def function(x):
    return x+1, x+2

assert function(10) == (11,12)

# example usage
answer = function(10)
print 'function(100) -> {}'.format(answer)

function(100) -> (11, 12)

Generators¶

A typical generator definition looks like the below. We swap out the `return` statement with a `yield statement` and provide two values. We use this generator by instantiating it with () then iterating over it. In Python, generators are generalised as "iterables" and support the __iter__/__next__ protocols. Many different things are iterable (lists, tuples, dictionaries, generators, &c.)

In [9]:

def generator(x):
    yield x+1
    yield x+2

assert list(generator(10)) == [11, 12]

# example usage
for x in generator(10):
    print 'generator(10) -> {}'.format(x)

generator(10) -> 11
generator(10) -> 12

Generator Expressions¶

We may note that a generator defined with `yield`-syntax appears to support both the __call__ and __iter__/__next__ protocols. In this case, we __call__ the generator to create an instance, then we iterate over the instance. A generator expression is one way we can construct a single instance inline.

In [12]:

generator_expression = (x+1 for x in [1,2,4,8,16])

assert list(generator_expression) == [2,3,5,9,17]

In [11]:

generator_expression = (x+1 for x in [1,2,4,8,16])

# example usage
for x in generator_expression:
    print 'generator_expression -> {}'.format(x)

generator_expression -> 2
generator_expression -> 3
generator_expression -> 5
generator_expression -> 9
generator_expression -> 17

A generator defined with `yield`-syntax is not strictly the same as, but can be considered equivalent with a generator expression that is constructed dynamically behind a lambda.

In [13]:

generator_expression = lambda: (x+1 for x in [1,2,4,8,16])

assert list(generator_expression()) == [2,3,5,9,17]

# example usage
for x in generator_expression():
    print 'generator_expression() -> {}'.format(x)

generator_expression() -> 2
generator_expression() -> 3
generator_expression() -> 5
generator_expression() -> 9
generator_expression() -> 17

Iterables¶

Callables are the Python generalisation of functions. In Python a callable is just some object that supports the __call__ protocol. __call__ corresponds to () or apply()

In [17]:

class Callable(object):
    def __call__(self, x):
        return x + 1, x + 2

assert Callable()(10) == (11, 12)

# exampe usage
answer = Callable()(10)
print 'Callable(10) -> {}'.format(answer)

Callable(10) -> (11, 12)

What if __call__ is a staticmethod?

In [20]:

class Callable(object):
    @staticmethod
    def __call__(x):
        return x + 1, x + 2

assert Callable()(10) == (11, 12)

In [22]:

from collections import Callable

def function():
    pass

assert callable(function) # deprecated in Python 3
assert isinstance(function, Callable)

Iterables are the Python generalisation of lists, tuples, &c. In Python an iterable is just some object that supports the __iter__ protocol and returns an object which supports the __next__ protocol. __iter__ corresponds to iter() and __next__ corresponds to next() Note that in Python 2, the __next__ protocol is provided by next. This was fixed in Python 3 (which we should all be using.)

In [21]:

some_list = [1, 1, 2, 3, 5]

for x in some_list:
    print 'some_list -> {}'.format(x)

some_list -> 1
some_list -> 1
some_list -> 2
some_list -> 3
some_list -> 5

In [29]:

class Iterable(object):
    def __init__(self, x):
        self.x = x
        self.state = 0
    def __iter__(self):
        return self # this object is both an iterator and an iterable
    def __next__(self):
        if self.state == 2:
            raise StopIteration
        rv = self.x + self.state
        self.state += 1
        return rv
    next = __next__ # Python 3 calls it `__next__`; Python 2 calls it `next`
    
assert list(Iterable(10)) == [10, 11]

# example usage
for x in Iterable(10):
    print 'Iterable(10) -> {}'.format(x)

Iterable(10) -> 10
Iterable(10) -> 11

Note that, in the above, we have an instance member called `self.state` that tracks the state. An iterator is anything that can be iterated over. An iterable is merely some object that tracks the state of the iteration.

In [33]:

from collections import Iterator, Iterable

some_list = [1, 1, 2, 3, 5]
assert isinstance(some_list, Iterable) and not isinstance(some_list, Iterator)

some_iter = iter(some_list)
assert isinstance(some_iter, Iterable) and isinstance(some_iter, Iterator)

A generator is merely a much lower-level expression of the above. Instead of explicitly tracking the state with some instance member, the state is tracked by a frame object which tracks the last line of code executed.

III. Coroutines¶

The generator below can `yield` values. This is in correspondence to how a function can `return` values.

In [34]:

def generator(x):
    yield x+1
    yield x+2

assert list(generator(10)) == [11, 12]

We can also send values into a generator at any point during the iteration. This is what makes a generator a coroutine. In fact, generators support a rich protocol including: .next: get the next value .throw: raise an exception .send: send a value in .close: terminate iteration

next & .next¶

In [41]:

def generator(x):
    yield x+1
    yield x+2

assert list(generator(10)) == [11, 12]
    
# support for next(), .next()
g = generator(10)
print 'next(g) -> {}'.format(next(g)) # these two lines are 
print 'next(g) -> {}'.format(g.next())

# next too many times, and we get a StopIteration
try:
    next(g)
except StopIteration as e:
    print 'next(g) -> {!r}'.format(e)

next(g) -> 11
next(g) -> 12
next(g) -> StopIteration()

.throw¶

In [53]:

from sys import exc_info
from traceback import print_tb

def generator(x):
    yield x+1
    yield x+2

g = generator(10)
print 'next(g) -> {}'.format(next(g))
# print 'next(g) -> {}'.format(next(g))

# support for .throw
try:
    g.throw(ValueError('raised value error'))
except ValueError as e:
    print 'g.throw(ValueError) -> {!r}'.format(e)
    _, _, traceback = exc_info()
    print_tb(traceback)

next(g) -> 11
g.throw(ValueError) -> ValueError('raised value error',)

  File "<ipython-input-53-d97f9e02cf2e>", line 14, in <module>
    g.throw(ValueError('raised value error'))
  File "<ipython-input-53-d97f9e02cf2e>", line 5, in generator
    yield x+1

.close¶

In [57]:

def generator(x):
    yield x+1
    yield x+2

g = generator(10)
print 'next(g) -> {}'.format(next(g))

g.close()

try:
    next(g)
except StopIteration as e:
    print 'g.close()'
    print 'next(g) -> {!r}'.format(e)

next(g) -> 11
g.close()
next(g) -> StopIteration()

.send¶

next(g) is the same as g.next() These are the same as g.send(None) or g.send() g.send() sends a value back into the generator at the point of `yield`

In [59]:

def generator(x):
    y = None
    y = yield x+1, y
    y = yield x+2, y

g = generator(10)
print 'next(g) -> {}'.format(         g.next()       )
print 'g.send("abc") -> {}'.format(    g.send("abc")  )

next(g) -> (11, None)
g.send("abc") -> (12, 'abc')

pumping & priming¶

One annoyance of generators is that we retrieve a value sent into the generator on the left hand side of a `yield`. This means that we must `yield` a value before we can accept a value back in. As a result, we have the following problem.

In [61]:

def generator(x):
    yield x + 1
    
g = generator(10)
g.send(10)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-61-d3574267c9bf> in <module>()
      3 
      4 g = generator(10)
----> 5 g.send(10)

TypeError: can't send non-None value to a just-started generator

IV. Itertools¶

Itertools is an extremely useful collection of utilities in the standard library. It contains very efficient generalisations, helpers, and algorithms that allow us to work very effectively with generators. The contents of itertools are themselves not generators; they are written in C and are mostly standard Python C-functions and C-objects.

generalisation¶

In [3]:

# an example of a generalisation: slicing
from itertools import islice

# standard lists can be sliced
some_list = [1, 1, 2, 3, 5, 8]
print some_list[1:5]

# abstract iterables can be isliced
def fibonacci(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b

print list(islice(fibonacci(),1,5))

# other examples: izip, imap, ifilter (Python2)

[1, 2, 3, 5]
[1, 2, 3, 5]

helper¶

In [4]:

# an example of a helper: chain
from itertools import chain, islice

# standard lists can be appended
some_list = [1, 1, 2, 3, 5, 8]
some_list = [0] + some_list
print some_list

# abstract iterables can be chained
def fibonacci(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b
    
f = fibonacci()
f = chain([0], f)

print list(islice(f,0,7))

# other examples: tee, repeat, cycle

[0, 1, 1, 2, 3, 5, 8]
[0, 1, 1, 2, 3, 5, 8]

algorithm¶

In [7]:

# an example of an algorithm: takewhile
from itertools import takewhile

# take elements as long as some predicate is True
def fibonacci(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b

print list(takewhile(lambda n: n < 50, fibonacci()))

# other examples: dropwhile, product, combinations, permutations

[1, 1, 2, 3, 5, 8, 13, 21, 34]

V. Efficiency¶

One reason to use generators is that they can efficiently represent certain constructs.

memory efficiency¶

For algorithms that require the use of only a subset of the entire return value, generators can prove far more memory efficient than their functional equivalents.

In [16]:

def pairwise(xs):
    xs = iter(xs)
    pairings = []
    x = next(xs)
    for y in xs:
        pairings.append([x,y])
        x = y
    return pairings

print pairwise(xrange(10))
# print pairwise(xrange(1000000))

[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9]]

In [1]:

def pairwise(xs):
    xs = iter(xs)
    x = next(xs)
    for y in xs:
        yield x, y
        x = y

print list(pairwise(xrange(10)))
print pairwise(xrange(1000000))

[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
<generator object pairwise at 0x1054c98c0>

Note that this can be written very tersely and very generically by combining helpers from `itertools`

In [20]:

from itertools import tee, izip, islice
nwise = lambda g,n=2: izip(*(islice(g,i,None) for i,g in enumerate(tee(g,n))))

print list(nwise(xrange(10)))

[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]

time efficiency¶

Generators tend to be fairly efficient in practice: <performance/bythrees> vs <performance/bythrees.py>

In [2]:

from math import ceil, sqrt
isprime = lambda n: 1 < n < 4 or all(n % d for d in xrange(2,int(ceil(sqrt(n)))+1,2))
   
%timeit -n100 isprime(11984395091324)

100 loops, best of 3: 2.22 us per loop

In [3]:

from math import ceil, sqrt
def isprime(n):
    if 1 < n < 4:
        return True
    for d in xrange(2, int(ceil(sqrt(n)))+1, 2):
        if n % d == 0:
            return False
    return True

%timeit -n100 isprime(11984395091324)

100 loops, best of 3: 1.33 us per loop

In [4]:

from math import ceil, sqrt
isprime = lambda n, ng: 1 < n < 4 or all(ng)
   
n = 11984395091324
ng = (n % d for d in xrange(2,int(ceil(sqrt(n)))+1,2))

%timeit -n100 isprime(n, ng)

100 loops, best of 3: 200 ns per loop

structural considerations¶

Generators are opaque building-blocks, so they can be swapped out very easily with more efficient representations: <nwise_main.py>

VI. Modelling¶

Someone asked me about numpy arrays versus generators. Numpy arrays are both efficient in practice and also very convenient to use. While generators can be very efficient and convenient, their real draw is in the ability to better model problems.

stream data processing & pipeline flow¶

Generators allow us to model programmes with a stream processing or pipeline conceptualisation.

presumptions about return type¶

In [56]:

def fibonacci(n, a=1, b=1):
    rv = [a, b]
    while rv[-1] + rv[-2] < n:
        rv.append(rv[-1] + rv[-2])
    return rv

print fibonacci(20)
print set(fibonacci(20))
print tuple(fibonacci(20))

% timeit fibonacci(20000)
% timeit set(fibonacci(20000))
% timeit tuple(fibonacci(20000))

[1, 1, 2, 3, 5, 8, 13, 21]
set([1, 2, 3, 5, 8, 13, 21])
(1, 1, 2, 3, 5, 8, 13, 21)
100000 loops, best of 3: 3.11 us per loop
100000 loops, best of 3: 4.27 us per loop
100000 loops, best of 3: 3.31 us per loop

In [58]:

def fibonacci(n, a=1, b=1):
    while a < n:
        yield a
        a, b = b, a+b

print list(fibonacci(20))
print set(fibonacci(20))
print tuple(fibonacci(20))

%timeit set(fibonacci(20000))
%timeit list(fibonacci(20000))
%timeit tuple(fibonacci(20000))

[1, 1, 2, 3, 5, 8, 13]
set([1, 2, 3, 5, 8, 13])
(1, 1, 2, 3, 5, 8, 13)
100000 loops, best of 3: 2.79 us per loop
100000 loops, best of 3: 2.8 us per loop
100000 loops, best of 3: 2.53 us per loop

presumptions about return values¶

In [62]:

# fibonacci numbers up to but not exceeding n
def fibonacci(n, a=1, b=1):
    rv = [a, b]
    while rv[-1] + rv[-2] < n:
        rv.append(rv[-1] + rv[-2])
    return rv
        
print fibonacci(20)

[1, 1, 2, 3, 5, 8, 13]

In [63]:

# fibonacci numbers up to but not exceeding n
def fibonacci(n, a=1, b=1):
    rv = [a, b]
    for _ in xrange(2,n):
        rv.append(rv[-1] + rv[-2])
    return rv

print fibonacci(20)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

In [65]:

from itertools import takewhile, islice

def fibonacci(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b

print list(islice(fibonacci(), 0, 20)) # first twenty values
print list(takewhile(lambda n: n < 20, fibonacci())) # values up to but not exceeding 20

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
[1, 1, 2, 3, 5, 8, 13]

presumptions about use of values¶

In [67]:

from time import sleep

# fibonacci numbers up to but not exceeding n
def fibonacci(n, a=1, b=1):
    rv = [a, b]
    for _ in xrange(2,n):
        rv.append(rv[-1] + rv[-2])
        sleep(.01)
    return rv

print fibonacci(20)[0]
% timeit fibonacci(20)[0]

1
10 loops, best of 3: 182 ms per loop

In [68]:

from time import sleep

def fibonacci(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b
        sleep(.01)

print next(fibonacci())
% timeit next(fibonacci())

1
1000000 loops, best of 3: 390 ns per loop

In [103]:

from datetime import date, timedelta
from time import sleep

holidays = { 'new years':        date(2013, 1, 1),
             'mlk day':          date(2013, 1, 21),
             'presidents day':   date(2013, 2, 18),
             'good friday':      date(2013, 3, 29),
             'memorial':         date(2013, 5, 27),
             'independence day': date(2013, 6, 4),
             'labour day':       date(2013, 9, 2),
             'columbus day':     date(2013, 10, 14),
             'veterans day':     date(2013, 11, 11),
             'thanksgiving':     date(2013, 11, 29),
             'christmas':        date(2013, 12, 24) }

def next_business_day(refdate, n=1, holidays=set(holidays.values())):
    sleep(.01)
    while refdate.weekday() in (5,6) or refdate in holidays:
            refdate += timedelta(days=1)    
    while n:
        refdate += timedelta(days=1)
        while refdate.weekday() in (5,6) or refdate in holidays:
            refdate += timedelta(days=1)
        n -= 1
    return refdate

#         July                 August              September        
# Su Mo Tu We Th Fr Sa  Su Mo Tu We Th Fr Sa  Su Mo Tu We Th Fr Sa  
#     1  2  3  4  5  6               1  2  3   1  2  3  4  5  6  7  
#  7  8  9 10 11 12 13   4  5  6  7  8  9 10   8  9 10 11 12 13 14  
# 14 15 16 17 18 19 20  11 12 13 14 15 16 17  15 16 17 18 19 20 21  
# 21 22 23 24 25 26 27  18 19 20 21 22 23 24  22 23 24 25 26 27 28  
# 28 29 30 31           25 26 27 28 29 30 31  29 30    

print next_business_day(date(2013, 8, 30))
print next_business_day(date(2013, 9, 1))

def next_business_days(refdate, n=10):
    next_days = [next_business_day(refdate)]
    for _ in xrange(n-1):
        next_days.append(next_business_day(ten_days[-1]))
    return next_days

print next_business_days(date(2013, 1, 1), 10)
% timeit next_business_days(date(2013, 1, 1), 90)

2013-09-03
2013-09-04
[datetime.date(2013, 1, 3), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17), datetime.date(2013, 9, 17)]
1 loops, best of 3: 916 ms per loop

In [104]:

def next_business_days(refdate, holidays=set(holidays.values())):  
    sleep(.01)
    while refdate.weekday() in (5,6) or refdate in holidays:
            refdate += timedelta(days=1)        
    while True:
        refdate += timedelta(days=1)
        while refdate.weekday() in (5,6) or refdate in holidays:
            refdate += timedelta(days=1)
        yield refdate

print list(islice(next_business_days(date(2013, 1, 1)), None, 10))
% timeit list(islice(next_business_days(date(2013, 1, 1)), None, 90))

[datetime.date(2013, 1, 3), datetime.date(2013, 1, 4), datetime.date(2013, 1, 7), datetime.date(2013, 1, 8), datetime.date(2013, 1, 9), datetime.date(2013, 1, 10), datetime.date(2013, 1, 11), datetime.date(2013, 1, 14), datetime.date(2013, 1, 15), datetime.date(2013, 1, 16)]
100 loops, best of 3: 10.4 ms per loop

knobs and buttons and modalities¶

In [3]:

from functools import wraps

# messy
def pumped(gen):
    @wraps(gen)
    def inner(*args, **kwargs):
        g = gen(*args, **kwargs)
        next(g)
        return g.send
    return inner

In [4]:

@pumped
def predicate(x, state=0):
    value = yield
    while True:
        if state+value <= x: # take values until you exceed the maximum
            state += value
            value = yield True 
        else:
            value = yield False

from itertools import repeat, chain, takewhile
greedy = lambda items, predicate: chain.from_iterable(takewhile(predicate,repeat(x)) for x in items)

In [14]:

from __future__ import division, unicode_literals
from itertools import groupby
from random import randint

denominations = [1,5,10,25,100,500,1000,2000]

for _ in xrange(10):
    amount = randint(0,1000) # randomly pick a dollar amount
    pred = predicate(amount) # create the predicate

    coins = greedy(reversed(denominations), pred) # greedy algorithm

    # pretty print
    print 'your change for {:>5.2f}$ = {}'.format(amount/100, 
          ' + '.join('{:>2d}×{:<3}'.format(sum(1 for _ in cs),
          (('{:d}¢' if c < 100 else '{:.0f}$').format(c if c < 100 else c/100))) for c,cs in groupby(coins)))

your change for  9.89$ =  1×5$  +  4×1$  +  3×25¢ +  1×10¢ +  4×1¢ 
your change for  0.10$ =  1×10¢
your change for  8.52$ =  1×5$  +  3×1$  +  2×25¢ +  2×1¢ 
your change for  7.40$ =  1×5$  +  2×1$  +  1×25¢ +  1×10¢ +  1×5¢ 
your change for  6.57$ =  1×5$  +  1×1$  +  2×25¢ +  1×5¢  +  2×1¢ 
your change for  0.91$ =  3×25¢ +  1×10¢ +  1×5¢  +  1×1¢ 
your change for  0.74$ =  2×25¢ +  2×10¢ +  4×1¢ 
your change for  5.06$ =  1×5$  +  1×5¢  +  1×1¢ 
your change for  9.25$ =  1×5$  +  4×1$  +  1×25¢
your change for  2.91$ =  2×1$  +  3×25¢ +  1×10¢ +  1×5¢  +  1×1¢

In [23]:

roman = {  1:  'i',   4: 'iv',    5:  'v',   9: 'ix',  10: 'x',
          40: 'ix',  50:  'x',   90: 'xc', 100:  'c', 400: 'cd',
         500:  'd', 900: 'cm', 1000:  'm',}

for _ in xrange(10):
    year = randint(1900,2200) # randomly pick a year
    pred = predicate(year) # create the predicate
    
    numerals = greedy(reversed(sorted(roman)), pred) # greedy algorithm
    
    # pretty print
    print 'the year {} is written {}'.format( year,''.join(roman[x].upper() for x in list(numerals)))

the year 2012 is written MMXII
the year 2172 is written MMCXXXII
the year 2129 is written MMCXXIX
the year 1990 is written MCMXC
the year 1907 is written MCMVII
the year 2192 is written MMCXCII
the year 1932 is written MCMXXXII
the year 2173 is written MMCXXXIII
the year 2097 is written MMXCVII
the year 1989 is written MCMXXXXIX

VII. Showcase¶

The showcase is one of the main attractions of `The Price is Right.` 70+ games. Drew Carey has lost a lot of weight. Who remembers Bob Barker? The `Price is Right` is a global phenomenon: 購物街 (高博) Showcase is the last game; spin the wheel.

In [ ]:

from itertools import repeat, izip, count, chain
from random import randrange
from time import sleep

# helper function
sleep = lambda n, sleep=sleep: lambda: sleep(n)

randoms = (randrange(0,63) for _ in count())
pauses = chain(repeat(sleep(0), 2500), repeat(sleep(0.01), 250), repeat(sleep(0.1), 25), repeat(sleep(1), 5))

for pause, random in izip(pauses, randoms):
    pause()
    print random

Lets add our own pseudo-random number generator.

In [153]:

# ref: en.wikipedia.org/wiki/Mersenne_twister
def mersenne(seed = 1, period=397, length=624):
    state, tm = [seed & 0xffffffff], lambda op, x: x ^ op(x)
    for i in xrange(1,length):
        state.append((0x6c078965 * (state[-1] ^ (state[-1] >> 30)) + i) & 0xffffffff)
    while True:
        for i in xrange(length):
            y = (state[i] & 0x80000000) + (state[(i+1)%length] & 0x7fffffff)
            state[i] = (state[(i+period)%length] ^ (y >> 1)) ^ (0x9908b0df if y%2 else 0)
        for i in xrange(length):
            yield tm(lambda x: x >> 18, tm(lambda x: (x << 15) & 0xefc60000, tm(lambda x: (x << 7) & 0x9d2c5680, tm(lambda x: x >> 11, state[i]))))
 
from itertools import takewhile
def randrange(start, stop, mersenne=mersenne(seed=1)):
    size = 2**32 // (stop - start)
    return start + next(takewhile(lambda x: 0 <= x < (stop-start)*size,mersenne)) % (stop-start)

m = mersenne()
assert list(islice(m,0,10)) == [1791095845, 4282876139, 3093770124, 4005303368, 491263, 550290313, 1298508491, 4290846341, 630311759, 1013994432]

How can we better simulate the wheel?

In [ ]:

from random import randrange

class Wheel(object):
    def __init__(self, start=0, players=100):
        self.start = start
        self.players = players
        
    def spin(self):
        state = self.start
        for _ in xrange(randrange(100,200)):
            print '| {:>2f} |'.format(self.state)
            self.state = (self.state + 1) % players
    
    # ...

Can we simulate this more simply?

In [38]:

from __future__ import division
from time import sleep
from random import random

forward, backward = lambda n: n+1, lambda n: n-1
def wheel(iterable, state=0, direction=forward):
    values = list(iterable)
    while True:
        direction = (yield values[state]) or direction
        state = direction(state) % len(values)

transition = lambda v,t: v-v/abs(v)*5*random()-abs(v)/(2+random())*t
def spin(wheel, velocity=500, stop=0.25, transition=transition):
    next(wheel) # ugly
    while abs(velocity) > stop:
        yield wheel.send(forward if velocity > 0 else backward)		
        sleep(1/abs(velocity))
        velocity = transition(velocity,1/velocity)

Notice that we have more control over the wheel.

In [26]:

def spin(wheel, velocity=500, stop=0.25, transition=transition):
	next(wheel) # ugly
	while abs(velocity) > stop:
		yield wheel.send(lambda n: n + int(velocity)) # <--
		sleep(1/abs(velocity))
		velocity = transition(velocity,1/velocity)

Notice how easy it is to test.

In [45]:

w = wheel([0,1,2])
assert next(w) == 0
assert next(w) == 1
assert next(w) == 2
assert next(w) == 0
assert next(w) == 1

w = wheel([0,1,2], direction=backward)
assert next(w) == 0
assert next(w) == 2
assert next(w) == 1
assert next(w) == 0
assert next(w) == 2

w = wheel([0,1,2], direction=lambda n: n+3)
assert next(w) == 0
assert next(w) == 0

w, v = wheel([0,1,2]), wheel(xrange(3))
assert next(w) == next(v)
assert next(w) == next(v)

w = wheel([0,1,2])
% timeit list(spin(w, velocity=10, stop=10))
% timeit list(spin(w, velocity=10, stop=0, transition=lambda v,t: v-5*v*t))

1000000 loops, best of 3: 1.17 us per loop
1 loops, best of 3: 301 ms per loop

We can further modularise this.

In [161]:

friction = lambda v,t: v-v/abs(v)*5*random()-abs(v)/(2+random())*t
def velocity(start=500, stop=0.25, friction=friction):
	state = start
	while abs(state) > stop:
		yield state
		state = friction(state, 1/state)

def spin(wheel, velocity):
	next(wheel) # ugly
	for vel in velocity:
		yield wheel.send(lambda n: n + int(vel))
		sleep(1/abs(vel))

In [170]:

v = velocity(500, 0.25)
assert next(v) > next(v)

v = velocity(500, 0.25)
assert list(v)

v = velocity(500, 0.25)
print list(v)

[500, 499.0817964316207, 496.7659122515505, 495.08552010237815, 491.282387088325, 487.93842180536495, 484.19405001694713, 482.0057844732008, 478.7238688452039, 475.5032114360953, 471.7675016676754, 469.8864501437916, 466.2870622381248, 464.83320557959144, 460.15425099202787, 456.00283619126964, 451.76537550458596, 449.44247485720877, 445.5739938836977, 443.8688028914643, 443.325138533312, 442.82904870257494, 441.573631315599, 439.8352065176586, 436.94307003243193, 434.56333918383905, 431.1159779876828, 428.1545743352637, 423.28181795374263, 420.5611098275818, 417.40925406234214, 414.4591870065937, 411.69219033962656, 408.7512452534986, 407.83220138412423, 406.46865706447596, 401.7756579653891, 396.7108031076217, 394.170516421267, 391.96703747194175, 391.14707228105, 388.7501117908976, 386.27118072215046, 383.7167324660817, 378.7833303992562, 373.75069101453533, 372.46980539238854, 369.9234513315834, 366.1096856671547, 364.20210560769794, 362.3976165089374, 359.0982179794059, 355.1211082334828, 353.80910869541975, 350.5842100128526, 349.71959531563124, 347.4153776039645, 346.23949269226483, 342.2879433016071, 338.3870290850201, 337.69996339837417, 333.46246641050396, 330.7195703326987, 328.74298200804674, 323.73148763236213, 322.9350618404671, 321.50542524013883, 318.00531062434254, 312.78912037261307, 309.647363266313, 307.0125075672744, 302.8325850039156, 297.5424573016874, 295.03958576192764, 293.80615443507736, 292.9430656464813, 291.49572805467665, 286.8501542297024, 282.15802579958404, 278.42359894762967, 276.4002892182105, 273.1661480124695, 269.5892064459307, 266.29859379573486, 264.40349547795034, 260.51177311272176, 256.12510786022915, 250.839432935257, 250.31090838268625, 245.86669039857406, 241.1075028644655, 239.09201197791702, 234.98520989686176, 233.710311945322, 231.1764567996815, 226.85486446455076, 224.33052547781725, 222.02378340970938, 220.14326829387144, 216.27894192326022, 213.1725406367333, 209.04975184292624, 205.48271789189957, 203.86217350447987, 200.00882850245154, 199.44886903332224, 198.3552806126174, 194.5012476067534, 191.15447739869526, 187.96570344222883, 183.83655030916793, 179.08611446749487, 174.15381040273087, 170.42673599855806, 167.69726753382565, 162.46211068150646, 160.21851704250344, 155.43863201051002, 154.5082199179937, 149.94752380647537, 148.41710951581513, 147.49207850633084, 145.88619185925617, 140.8416525561992, 139.81195314947087, 135.6007287434456, 130.80348490620517, 129.5140589596599, 129.04567776925992, 127.84644885358462, 125.67759942246292, 124.24685276928172, 119.79599230876926, 118.81323602189435, 118.00389009146554, 117.28552955566607, 114.37531199507367, 111.54099257368635, 109.27078291882988, 105.12798596501703, 102.7552346803562, 99.90479577436477, 97.62957499202311, 94.83351178598595, 90.61025732397695, 86.42644343625584, 83.44703389761457, 82.04680513629611, 78.22340649000053, 75.78900274645054, 73.24509816475968, 71.81252408317644, 69.07134255317911, 67.06764269403341, 64.12557842590694, 62.25526449444695, 58.185535596252734, 53.25096015345708, 50.01623638424963, 45.21374690677783, 42.20997207866244, 40.02867570300589, 34.64041753783563, 34.03253790830072, 29.017420898377953, 28.086514851300553, 25.76920462146157, 21.232521445238767, 16.93779084404379, 14.986564436514094, 10.503979648158625, 7.967383833679981, 6.2877142369347325, 2.8718434777339663, 1.8450054139716494, -2.4157473566898378, 2.2611475223068744, -1.1143165268282922, 0.2625693314053857, -3.815865511492414, 0.7030720821363874, -3.2367212976233937, -1.4588499894114804, 1.0872610466296941, -0.4092751853535173, 3.813448600861101, 1.4590528069405848, 0.7340765522835442, -2.1093497629134537, 3.006970624175923, 1.8369818179220516, 0.2776043233310767, -0.5968984314029906, 4.76530376422617, 2.01106324288153, 0.7107035608560084, -2.6214121637054304, -0.76157451582592, 3.737767438416472, 3.2149405855890194, 2.1945749324327033, 1.5692558741721352]

All together...

In [173]:

from __future__ import division
from time import sleep
from random import random

forward, backward = lambda n: n+1, lambda n: n-1
def wheel(iterable, state=0, direction=forward):
	values = list(iterable)
	while True:
		direction = (yield values[state]) or direction
		state = direction(state) % len(values)

friction = lambda v,t: v-v/abs(v)*5*random()-abs(v)/(2+random())*t
def velocity(start=500, stop=0.25, friction=friction):
	state = start
	while abs(state) > stop:
		yield state
		state = friction(state, 1/state)

def spin(wheel, velocity):
	next(wheel) # ugly
	for vel in velocity:
		yield wheel.send(lambda n: n + int(vel))
		sleep(1/abs(vel))

In [174]:

from random import randrange, shuffle

players, prizes = range(25), ['book'] + ['t-shirt']*5 + ['mug']*5
winners = [(player, prize) for player in players for prize in prizes]
shuffle(winners)

state, velocity = randrange(0, len(winners)), velocity(randrange(500, 750))

for number, prize in spin(wheel(winners, state=state), velocity=velocity):
    print '| {:>2}  {:<{}} |'.format(number, prize, max(len(p) for p in prizes))

print 'you won a ... {}, #{}'.format(prize, number)

|  3  mug     |
| 16  t-shirt |
|  2  mug     |
|  9  mug     |
| 16  mug     |
| 21  t-shirt |
| 16  book    |
| 11  t-shirt |
|  9  mug     |
| 13  t-shirt |
|  8  t-shirt |
| 21  mug     |
| 15  mug     |
| 11  t-shirt |
| 19  t-shirt |
|  8  mug     |
| 18  mug     |
|  9  t-shirt |
| 10  mug     |
| 11  t-shirt |
|  0  mug     |
| 10  t-shirt |
|  4  mug     |
|  1  mug     |
| 20  t-shirt |
|  1  mug     |
| 18  t-shirt |
| 17  mug     |
| 11  mug     |
|  2  t-shirt |
| 11  t-shirt |
| 24  t-shirt |
| 14  mug     |
| 23  t-shirt |
| 18  mug     |
| 11  mug     |
|  4  t-shirt |
|  4  mug     |
| 22  t-shirt |
| 18  t-shirt |
| 11  mug     |
| 18  t-shirt |
|  3  t-shirt |
| 17  t-shirt |
| 24  t-shirt |
| 18  mug     |
|  1  mug     |
|  9  t-shirt |
| 18  t-shirt |
| 20  t-shirt |
| 23  t-shirt |
| 11  t-shirt |
| 17  mug     |
| 22  book    |
| 15  mug     |
| 24  t-shirt |
| 22  book    |
|  9  t-shirt |
| 22  mug     |
| 15  mug     |
| 20  mug     |
|  5  t-shirt |
| 10  mug     |
| 21  t-shirt |
|  9  mug     |
|  1  t-shirt |
| 15  mug     |
| 18  book    |
| 13  mug     |
| 14  mug     |
| 13  mug     |
|  3  mug     |
| 16  t-shirt |
| 21  t-shirt |
|  4  mug     |
| 22  t-shirt |
|  4  mug     |
| 17  mug     |
| 11  t-shirt |
| 10  book    |
|  9  t-shirt |
|  0  t-shirt |
| 23  t-shirt |
| 11  t-shirt |
|  8  mug     |
| 15  mug     |
|  0  mug     |
|  1  book    |
| 15  t-shirt |
| 22  mug     |
|  8  mug     |
| 11  mug     |
| 12  mug     |
| 24  book    |
| 18  t-shirt |
| 14  mug     |
| 18  mug     |
|  2  t-shirt |
|  5  mug     |
| 23  t-shirt |
| 24  t-shirt |
|  4  t-shirt |
| 23  mug     |
|  7  mug     |
|  7  t-shirt |
| 15  book    |
|  7  t-shirt |
| 23  t-shirt |
| 18  mug     |
| 22  mug     |
| 21  t-shirt |
| 20  t-shirt |
| 16  t-shirt |
|  7  mug     |
| 19  t-shirt |
| 15  mug     |
|  1  book    |
| 10  book    |
| 12  mug     |
|  1  book    |
| 20  t-shirt |
|  1  mug     |
| 12  t-shirt |
|  0  t-shirt |
| 23  mug     |
|  0  mug     |
| 24  mug     |
| 17  mug     |
|  2  book    |
|  5  t-shirt |
|  7  t-shirt |
| 21  mug     |
|  9  book    |
| 19  t-shirt |
|  7  mug     |
|  5  mug     |
| 20  t-shirt |
|  8  mug     |
| 19  book    |
| 24  t-shirt |
|  2  mug     |
| 14  mug     |
| 24  book    |
| 19  mug     |
| 14  t-shirt |
| 21  mug     |
|  2  t-shirt |
|  6  t-shirt |
|  3  mug     |
|  9  mug     |
| 14  t-shirt |
| 11  t-shirt |
|  4  mug     |
| 18  t-shirt |
| 12  t-shirt |
|  3  t-shirt |
| 17  mug     |
| 23  t-shirt |
|  1  t-shirt |
| 11  mug     |
| 11  t-shirt |
| 18  t-shirt |
|  9  t-shirt |
| 19  mug     |
| 21  t-shirt |
|  5  mug     |
| 19  book    |
| 23  t-shirt |
|  6  mug     |
| 15  t-shirt |
|  4  t-shirt |
| 10  book    |
| 13  t-shirt |
|  9  mug     |
| 14  mug     |
|  6  mug     |
| 17  t-shirt |
|  6  mug     |
| 10  t-shirt |
| 15  t-shirt |
|  3  mug     |
| 12  t-shirt |
|  8  book    |
|  5  t-shirt |
|  9  mug     |
| 13  mug     |
| 17  mug     |
|  4  mug     |
| 12  mug     |
| 19  mug     |
|  7  mug     |
|  4  mug     |
| 21  book    |
| 24  mug     |
| 18  book    |
|  4  t-shirt |
|  4  mug     |
| 12  mug     |
|  7  t-shirt |
|  3  t-shirt |
|  1  t-shirt |
|  6  mug     |
| 13  t-shirt |
|  9  t-shirt |
| 24  mug     |
| 13  t-shirt |
| 21  mug     |
| 14  mug     |
| 13  mug     |
| 10  t-shirt |
| 11  mug     |
| 17  mug     |
|  1  t-shirt |
| 16  mug     |
| 21  t-shirt |
| 21  t-shirt |
| 16  mug     |
|  2  book    |

---------------------------------------------------------------------------
StdinNotImplementedError                  Traceback (most recent call last)
<ipython-input-174-ea387a5aa081> in <module>()
      9 for number, prize in spin(wheel(winners, state=state), velocity=velocity):
     10     print '| {:>2}  {:<{}} |'.format(number, prize, max(len(p) for p in prizes))
---> 11 raw_input('you won a ... {}, #{}'.format(prize, number))

/home/powell/scratch/ipython/local/lib/python2.7/site-packages/IPython/zmq/ipkernel.pyc in <lambda>(prompt)
    343             raw_input = lambda prompt='': self._raw_input(prompt, ident, parent)
    344         else:
--> 345             raw_input = lambda prompt='' : self._no_raw_input()
    346 
    347         if py3compat.PY3:

/home/powell/scratch/ipython/local/lib/python2.7/site-packages/IPython/zmq/ipkernel.pyc in _no_raw_input(self)
    698         """Raise StdinNotImplentedError if active frontend doesn't support
    699         stdin."""
--> 700         raise StdinNotImplementedError("raw_input was called, but this "
    701                                        "frontend does not support stdin.") 
    702 

StdinNotImplementedError: raw_input was called, but this frontend does not support stdin.

VIII. Sign-Off¶

‘James Powell, reminding you to help control the pet population.¶

‘Remember to spay and neuter your pets!’¶