Multiplexing Exercises¶

Monte Carlo π¶

A simple toy problem to get a handle on multiple engines is a Monte Carlo approximation of π.

Let's say we have a dartboard with a round target inscribed on a square board. If you threw darts randomly, and they land evenly distributed on the square board, how many darts would you expect to hit the target?

No description has been provided for this image

$\frac{A_c}{A_{sq}} = \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4}$

In [3]:

from random import random
from math import pi

def mcpi(nsamples):
    s = 0
    for i in xrange(nsamples):
        x = random()
        y = random()
        if x*x + y*y <= 1:
            s+=1
    return 4.*s/nsamples

In [8]:

for n in [10, 100, 1000, 10000, 100000, 1000000]:
    print "%8i" % n,
    for i in range(3):
        print "%.5f" % mcpi(n),
    print

      10 3.60000 2.80000 1.20000
     100 3.28000 3.20000 3.36000
    1000 3.16400 3.14400 3.12800
   10000 3.12880 3.13720 3.13320
  100000

3.15504

3.14420

3.13848
 1000000

3.13871

3.14190

3.13897

In [9]:

%timeit mcpi(1000000)

1 loops, best of 3: 502 ms per loop

It takes a lot of samples to get a good approximation. Can you write a function that will use your engines to break up the work?

def multi_mcpi(dview, nsamples):
    raise NotImplementedError("you write this")

In [27]:

from IPython import parallel
rc = parallel.Client()

view = rc[:]

In [28]:

%loadpy soln/mcpi.py

In [31]:

multi_mcpi(view, 10000000)

Out[31]:

3.1421404

Remote Iterators¶

Can you create an object that iterates through a remote iterable?

e0['a'] = range(5)

ra = remote_iterator(dview, 'a')

for element in ra:
    print element

Remote exceptions arrive as RemoteErrors with an ename attribute

In [47]:

from IPython.parallel.error import RemoteError

e0 = rc[0]
try:
    e0.execute("1/0", block=True)
except RemoteError as e:
    if e.ename == 'ZeroDivisionError':
        print "oops, divided by zero!"
    else:
        # unhandled error
        raise e

oops, divided by zero!

In [35]:

%loadpy soln/remoteiterhint.py

In [55]:

%loadpy soln/remoteiter.py

In [57]:

# Slightly modified version of:
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/511509

import heapq

def mergesort(list_of_lists, key=None):
    """ Perform an N-way merge operation on sorted lists.

    @param list_of_lists: (really iterable of iterable) of sorted elements
    (either by naturally or by C{key})
    @param key: specify sort key function (like C{sort()}, C{sorted()})

    Yields tuples of the form C{(item, iterator)}, where the iterator is the
    built-in list iterator or something you pass in, if you pre-generate the
    iterators.

    This is a stable merge; complexity O(N lg N)

    Examples::

    >>> print list(mergesort([[1,2,3,4],
    ...                      [2,3.25,3.75,4.5,6,7],
    ...                      [2.625,3.625,6.625,9]]))
    [1, 2, 2, 2.625, 3, 3.25, 3.625, 3.75, 4, 4.5, 6, 6.625, 7, 9]

    # note stability
    >>> print list(mergesort([[1,2,3,4],
    ...                      [2,3.25,3.75,4.5,6,7],
    ...                      [2.625,3.625,6.625,9]],
    ...                      key=int))
    [1, 2, 2, 2.625, 3, 3.25, 3.75, 3.625, 4, 4.5, 6, 6.625, 7, 9]


    >>> print list(mergesort([[4, 3, 2, 1],
    ...                      [7, 6, 4.5, 3.75, 3.25, 2],
    ...                      [9, 6.625, 3.625, 2.625]],
    ...                      key=lambda x: -x))
    [9, 7, 6.625, 6, 4.5, 4, 3.75, 3.625, 3.25, 3, 2.625, 2, 2, 1]
    """

    heap = []
    for i, itr in enumerate(iter(pl) for pl in list_of_lists):
        try:
            item = itr.next()
            if key:
                toadd = (key(item), i, item, itr)
            else:
                toadd = (item, i, itr)
            heap.append(toadd)
        except StopIteration:
            pass
    heapq.heapify(heap)

    if key:
        while heap:
            _, idx, item, itr = heap[0]
            yield item
            try:
                item = itr.next()
                heapq.heapreplace(heap, (key(item), idx, item, itr) )
            except StopIteration:
                heapq.heappop(heap)

    else:
        while heap:
            item, idx, itr = heap[0]
            yield item
            try:
                heapq.heapreplace(heap, (itr.next(), idx, itr))
            except StopIteration:
                heapq.heappop(heap)

Make a set of 'sorted datasets'

In [58]:

a0 = range(5,20)
a1 = range(10)
a2 = range(15,25)

Now, imagine these had been created in the remote engines by some long computation. In this simple example, we just send them over into the remote engines. They will all be called 'a' in each engine.

In [59]:

rc[0]['a'] = a0
rc[1]['a'] = a1
rc[2]['a'] = a2

And we now make a local object which represents the remote iterator

In [60]:

ra0 = remote_iterator(rc[0],'a')
ra1 = remote_iterator(rc[1],'a')
ra2 = remote_iterator(rc[2],'a')

Let's merge them, both locally and remotely:

In [61]:

print 'Merge the local datasets:'
print list(mergesort([a0,a1,a2]))
    
print 'Locally merge the remote sets:'
print list(mergesort([ra0,ra1,ra2]))

Merge the local datasets:
[0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 21, 22, 23, 24]
Locally merge the remote sets:
[0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 21, 22, 23, 24]

In [ ]: