Numpy Challenge Benchmarks

gistfile1.py

{
 "metadata": {
  "name": "NumPy Programming Challenge"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "# NumPy Programming Challenge\n\nWrite the most succinct NumPy code possible to compute a 2D array that contains all \"legal\" allocations to 4 stocks:\n\n* \"Legal\" means: The allocations are in 0.10 chunks, and the allocations sum to 1.00\n* Only \"pure\" NumPy is allowed (no external libraries)\n* Can you do it without a \"for\"?\n\n*Benchmarks and compilation by: Yaser Martinez (yaser.martinez@me.com)*"
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Yaser Martinez(numpy)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nfrom numpy import indices, vstack\n\nx1_3 = indices((11,11,11)).reshape(3,1331)\nx4 = 10 - x1_3.sum(axis=0)\nvalid_idx = x4 > -1\nallocations = 0.1*vstack((x1_3, x4)).T[valid_idx]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "10000 loops, best of 3: 127 us per loop\n"
      }
     ],
     "prompt_number": 102
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Nick Poplas (pure python)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nallocations = [(0.1 * a, 0.1 * b, 0.1 * c, 0.1 * (10 - a - b - c)) for a in range(11) for b in range(11 - a) for c in range(11 - a - b)]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "10000 loops, best of 3: 144 us per loop\n"
      }
     ],
     "prompt_number": 65
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Karli Watson"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nlf_allocations = []\nfor i_bucketA in range(0, 11):\n    for i_bucketB in range(0, 11 - i_bucketA):\n        for i_bucketC in range(0, 11 - i_bucketA - i_bucketB):\n            i_bucketD = 10 - i_bucketA - i_bucketB - i_bucketC   \n            lf_allocations.append((i_bucketA / 10.0, i_bucketB / 10.0, i_bucketC / 10.0, i_bucketD / 10.0))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "10000 loops, best of 3: 189 us per loop\n"
      }
     ],
     "prompt_number": 66
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Miguel Angel (pure python)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nallocations = [[a*0.1,b*0.1,c*0.1,1-0.1*(a+b+c)] for a in range(0,11) for b in range(0,11-a) for c in range(0,11-a-b)]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 220 us per loop\n"
      }
     ],
     "prompt_number": 67
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Sergio Antoy"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\na = [] \ni,j,k = 0,1,2\n\nwhile True:\n    # print [i,j-i-1,k-j-1,12-k]\n    a.append([i/10.,(j-i-1)/10.,(k-j-1)/10.,(12-k)/10.])\n    if i < j-1:\n        i += 1\n    elif j < k-1:\n        i,j = 0,j+1\n    elif k < 12:\n        i,j,k = 0,1,k+1\n    else:\n        break",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 238 us per loop\n"
      }
     ],
     "prompt_number": 68
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Pawel Kozak (recursive no numpy)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\n\na=[]\ndef y(last, i=0, j=0, k=0, l=0):\n    if len(a)==0:\n        a.append([10,0, 0, 0])\n    else:\n        a.append([last[0]+i,last[1]+j,last[2]+k, last[3]+l])\n    last = a[-1][:]\n    if last[0]>0:\n        y(last, i=-1, j=1, k=0, l=0)\n        if last[1] ==0:\n            y(last, i=-1, j=0, k=1, l=0)\n            if last[2] ==0:\n                y(last, i=-1, j=0, k=0, l=1)\n        \n(y(a))\n\ng = [[a[j][i]/10.0 for i in range(4)] for j in range(len(a))]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 701 us per loop\n"
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Yaser Martinez (pure numpy)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nfrom numpy import linspace, rollaxis, indices\n\nx = linspace(0,1,11)[rollaxis(indices((11,) * 4), 0, 4+1).reshape(-1, 4)]\nvalid_allocations = x[abs(x.sum(axis=1)-1)<1e-8]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 1.29 ms per loop\n"
      }
     ],
     "prompt_number": 70
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Rich Dubielzig"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\ndef assemble_legal(ary, element, total, left):\n        if( left <= 1 ):\n                element.append(total);\n                ary.append(element);\n                return\n        for i in range(0,total + 1):\n                assemble_legal(ary, element + [i] , total - i, left - 1)\n\ndef make_legal_allocations( num_symbols, max_divisor ):\n        output = []\n        assemble_legal(output,[],max_divisor, num_symbols)\n        output = np.reshape(output,(-1,num_symbols))\n        return output / float(max_divisor)\n    \nnp.shape(make_legal_allocations(4,10))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 1.68 ms per loop\n"
      }
     ],
     "prompt_number": 71
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Andy Choi"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\nn = 11\na = np.empty((n**4, 4))\nr = np.arange(0, n**4)\na[:,0] = np.mod(r / (n**0), n)\na[:,1] = np.mod(r / (n**1), n)\na[:,2] = np.mod(r / (n**2), n)\na[:,3] = np.mod(r / (n**3), n)\nresult = a[a.sum(axis=1) == (n-1)] / 10",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1000 loops, best of 3: 1.79 ms per loop\n"
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Reach344 (Pure numpy)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\nids = np.float16(np.indices((11,)*4)) / 10\nt = np.concatenate(\n[\nids[0].flat[:][..., np.newaxis],\nids[1].flat[:][..., np.newaxis],\nids[2].flat[:][..., np.newaxis],\nids[3].flat[:][..., np.newaxis]\n], axis=1)\nallocations = t[abs(t.sum(axis=1)-1) < 0.01]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 2.69 ms per loop\n"
      }
     ],
     "prompt_number": 72
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "David Van Aken"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\nlegal=np.zeros((286,4))\ncount = 0\nfor i in range (0,11):\n    for j in range(0,11-i):\n        for k in range(0,11-i-j):\n            for l in range(10-(i+j+k),11-i-j-k):\n                legal[count,:]=[i*.1,j*.1,k*.1,l*.1]\n                count = count +1",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 2.77 ms per loop\n"
      }
     ],
     "prompt_number": 73
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Luigi Maio"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\ndef getAlloc():\n    global weights\n    weights = np.zeros((0,4))\n    getAllocRec([0,0,0,0], 0, 10)\n    weights /= 10.0\n    return\n  \ndef getAllocRec(legal, index, n):\n    global weights\n    if index == 3:\n        legal[index] = n\n        weights = np.vstack((weights, legal))\n        return\n    if n == 0:\n        legal[index] = 0\n        getAllocRec(legal, index+1, 0)\n        return\n    for i in range(n+1):\n        legal[index] = i\n        getAllocRec(legal, index+1, n-i)\ngetAlloc()",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 5.48 ms per loop\n"
      }
     ],
     "prompt_number": 74
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Tobias Brandt "
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nfrom numpy import linspace, rint, array, fromiter as fi\nfrom scipy.misc import comb\nfrom itertools import chain, combinations_with_replacement as cwr\n\ncfi = chain.from_iterable\nk = 4\nd = 0.1\nn = int(rint(1/d))\nc = comb(n+k-1,k-1,exact=1)\nB = linspace(0, 1, n+1)\nW = lambda S: array(S+(1,))-array((0,)+S)\nA = fi(cfi(W(S) for S in cwr(B,k-1)),dtype='float64',count=c*k).reshape((c,k))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 5.86 ms per loop\n"
      }
     ],
     "prompt_number": 75
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Laurent Laskowski"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\ndef generate_alloc():\n    # Generate all numbers from 0 to 9999\n    A=range(10000)\n    # A4 represents the thousands, A3 represents the hundreds\n    # A2 represents the tens, A1 represents the units\n    # of all numbers between 0 and 9999\n    A1=np.multiply(1/10.,np.floor(np.multiply(1/1000.,np.remainder(A,10000))))\n    A2=np.multiply(1/10.,np.floor(np.multiply(1/100.,np.remainder(A,1000))))\n    A3=np.multiply(1/10.,np.floor(np.multiply(1/10.,np.remainder(A,100))))\n    A4=np.multiply(1/10.,np.floor(np.multiply(1/1.,np.remainder(A,10))))\n    # add the diagonal 1 matrix\n    A1=np.append(A1,[1.0,0.0,0.0,0.0])\n    A2=np.append(A2,[0.0,1.0,0.0,0.0])\n    A3=np.append(A3,[0.0,0.0,1.0,0.0])\n    A4=np.append(A4,[0.0,0.0,0.0,1.0])\n    # B will be the matrix \n    B=np.array([A1,A2,A3,A4])\n    # only take 'legal' allocation\n    C=B[:,np.sum(B,axis=0)==1.0]\n    return(C)\ngenerate_alloc()",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 9.71 ms per loop\n"
      }
     ],
     "prompt_number": 76
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "JJ"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\n\nimport numpy as np\ndef findPartitions(n, k):\n    if k==1: return np.array([n])\n    if n==0: return np.repeat(0, k).reshape(1, -1)\n    \n    res = np.empty(shape=(0, k), dtype=int)\n    \n    for firstTerm in np.arange(n+1):\n        partialRes = findPartitions(n - firstTerm, k-1)\n        part1 = np.repeat(firstTerm, partialRes.shape[0])\n        part2 = np.column_stack((part1, partialRes))\n        res = np.vstack((res, part2))\n\n    return res\n\nfindPartitions(10, 4)/10.0",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 11.2 ms per loop\n"
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Martin H\u00fcnermund "
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\n\ndef normalize_portfolio(portfolio):\n    normalized = portfolio.copy()\n    s = sum(portfolio.values())\n    for symbol, weight in portfolio.iteritems():\n        normalized[symbol] = 1.0 * weight / s\n    \n    return normalized\n\ndef challenge(symbols,num_intervals):\n    '''Creates all valid portfolios for the given symbols.\n    \n    I use integer numbers to avoid rounding problems and normalize afterwards.\n    '''\n    \n    stack = []\n    stack.append((num_intervals,symbols[:],{}))\n    count = 0\n    \n    portfolios = []\n    \n    while(len(stack)>0):\n        (unallocated,unallocated_symbols,portfolio)=stack.pop()\n        if(len(unallocated_symbols)==0):\n            count+=1\n            \n            # Here i test my portfolio. But for the challange let's just add\n            # the portfolio to a list.\n                \n            portfolios.append(normalize_portfolio(portfolio))\n        else:\n            new_symbol = unallocated_symbols.pop()\n            \n            # If this is the last symbol all must be allocated\n            allocate = 0 if len(unallocated_symbols) > 0 else unallocated\n            \n            while(allocate <= unallocated):\n                new_portfolio = portfolio.copy()\n                new_portfolio[new_symbol] = allocate\n                stack.append((unallocated-allocate,unallocated_symbols[:],new_portfolio))\n                allocate += 1\n    \n    return portfolios\n\n# Execute for interval 0.1\nportfolios10  = challenge(['GOOG', 'AAPL', 'XOM', 'GLD'],10)  # for interval 0.1",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 13.9 ms per loop\n"
      }
     ],
     "prompt_number": 77
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Andrew Marshall (One-liner without itertools)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nfrom numpy import indices\n\n[append(x,10-sum(x))*0.1 for x in indices((11,11,11)).T.reshape((1331,3)) if sum(x) <= 10]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "100 loops, best of 3: 18.2 ms per loop\n"
      }
     ],
     "prompt_number": 78
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Evan Teitelman"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\ninc = 0.1\nincs = np.arange(0, 1 + inc, inc)\ntest_allocs = np.around([[a, b, c, d]\n\t\t\tfor a in incs\n\t\t\tfor b in incs\n\t\t\tfor c in incs\n\t\t\tfor d in incs\n\t\t\tif a + b + c + d == 1.0], 4)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "10 loops, best of 3: 26.7 ms per loop\n"
      }
     ],
     "prompt_number": 79
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Will Kriski"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport itertools as it\n\nall_allocations = 0.1*np.array(filter(lambda (a, b, c, d): a+b+c+d == 10, np.asarray(list(it.product(np.arange(0, 11, 1), repeat=4)))))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "10 loops, best of 3: 135 ms per loop\n"
      }
     ],
     "prompt_number": 80
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Daniel Vinegrad (functional approach + itertools)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport itertools\n\nmap(list, filter(lambda x: sum(x) == 1, itertools.product(np.linspace(0,1,11), repeat=4)))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1 loops, best of 3: 272 ms per loop\n"
      }
     ],
     "prompt_number": 81
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Wes Henderson"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\nimport numpy as np\n\nportfolio = []\n\nfor index in np.ndindex(11, 11, 11, 11):\n    if (np.sum(index)==10):\n        portfolio.append(np.array(index)/float(10))",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1 loops, best of 3: 339 ms per loop\n"
      }
     ],
     "prompt_number": 82
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": "Tucker Balch (brute force approach)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "%%timeit\n\nimport numpy as np\nallocs = np.zeros((10000,4))\nn = 0\nfor i in range(0,11):\n    for j in range(0,11):\n        for k in range(0,11):\n            for l in range(0,11):\n                row = [i/10.0,j/10.0,k/10.0,l/10.0]\n                if sum(row)==1.0:\n                    allocs[n,:]=row\n                    n = n+1\nallocs = allocs[0:n,:]",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "1 loops, best of 3: 284 ms per loop\n"
      }
     ],
     "prompt_number": 83
    }
   ],
   "metadata": {}
  }
 ]
}