Write the most succinct NumPy code possible to compute a 2D array that contains all "legal" allocations to 4 stocks:
Benchmarks and compilation by: Yaser Martinez (yaser.martinez@me.com)
%%timeit
from numpy import indices, vstack
x1_3 = indices((11,11,11)).reshape(3,1331)
x4 = 10 - x1_3.sum(axis=0)
valid_idx = x4 > -1
allocations = 0.1*vstack((x1_3, x4)).T[valid_idx]
10000 loops, best of 3: 127 us per loop
%%timeit
allocations = [(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)]
10000 loops, best of 3: 144 us per loop
%%timeit
lf_allocations = []
for i_bucketA in range(0, 11):
for i_bucketB in range(0, 11 - i_bucketA):
for i_bucketC in range(0, 11 - i_bucketA - i_bucketB):
i_bucketD = 10 - i_bucketA - i_bucketB - i_bucketC
lf_allocations.append((i_bucketA / 10.0, i_bucketB / 10.0, i_bucketC / 10.0, i_bucketD / 10.0))
10000 loops, best of 3: 189 us per loop
%%timeit
allocations = [[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)]
1000 loops, best of 3: 220 us per loop
%%timeit
a = []
i,j,k = 0,1,2
while True:
# print [i,j-i-1,k-j-1,12-k]
a.append([i/10.,(j-i-1)/10.,(k-j-1)/10.,(12-k)/10.])
if i < j-1:
i += 1
elif j < k-1:
i,j = 0,j+1
elif k < 12:
i,j,k = 0,1,k+1
else:
break
1000 loops, best of 3: 238 us per loop
%%timeit
a=[]
def y(last, i=0, j=0, k=0, l=0):
if len(a)==0:
a.append([10,0, 0, 0])
else:
a.append([last[0]+i,last[1]+j,last[2]+k, last[3]+l])
last = a[-1][:]
if last[0]>0:
y(last, i=-1, j=1, k=0, l=0)
if last[1] ==0:
y(last, i=-1, j=0, k=1, l=0)
if last[2] ==0:
y(last, i=-1, j=0, k=0, l=1)
(y(a))
g = [[a[j][i]/10.0 for i in range(4)] for j in range(len(a))]
1000 loops, best of 3: 701 us per loop
%%timeit
from numpy import linspace, rollaxis, indices
x = linspace(0,1,11)[rollaxis(indices((11,) * 4), 0, 4+1).reshape(-1, 4)]
valid_allocations = x[abs(x.sum(axis=1)-1)<1e-8]
1000 loops, best of 3: 1.29 ms per loop
%%timeit
import numpy as np
def assemble_legal(ary, element, total, left):
if( left <= 1 ):
element.append(total);
ary.append(element);
return
for i in range(0,total + 1):
assemble_legal(ary, element + [i] , total - i, left - 1)
def make_legal_allocations( num_symbols, max_divisor ):
output = []
assemble_legal(output,[],max_divisor, num_symbols)
output = np.reshape(output,(-1,num_symbols))
return output / float(max_divisor)
np.shape(make_legal_allocations(4,10))
1000 loops, best of 3: 1.68 ms per loop
%%timeit
import numpy as np
n = 11
a = np.empty((n**4, 4))
r = np.arange(0, n**4)
a[:,0] = np.mod(r / (n**0), n)
a[:,1] = np.mod(r / (n**1), n)
a[:,2] = np.mod(r / (n**2), n)
a[:,3] = np.mod(r / (n**3), n)
result = a[a.sum(axis=1) == (n-1)] / 10
1000 loops, best of 3: 1.79 ms per loop
%%timeit
import numpy as np
ids = np.float16(np.indices((11,)*4)) / 10
t = np.concatenate(
[
ids[0].flat[:][..., np.newaxis],
ids[1].flat[:][..., np.newaxis],
ids[2].flat[:][..., np.newaxis],
ids[3].flat[:][..., np.newaxis]
], axis=1)
allocations = t[abs(t.sum(axis=1)-1) < 0.01]
100 loops, best of 3: 2.69 ms per loop
%%timeit
import numpy as np
legal=np.zeros((286,4))
count = 0
for i in range (0,11):
for j in range(0,11-i):
for k in range(0,11-i-j):
for l in range(10-(i+j+k),11-i-j-k):
legal[count,:]=[i*.1,j*.1,k*.1,l*.1]
count = count +1
100 loops, best of 3: 2.77 ms per loop
%%timeit
import numpy as np
def getAlloc():
global weights
weights = np.zeros((0,4))
getAllocRec([0,0,0,0], 0, 10)
weights /= 10.0
return
def getAllocRec(legal, index, n):
global weights
if index == 3:
legal[index] = n
weights = np.vstack((weights, legal))
return
if n == 0:
legal[index] = 0
getAllocRec(legal, index+1, 0)
return
for i in range(n+1):
legal[index] = i
getAllocRec(legal, index+1, n-i)
getAlloc()
100 loops, best of 3: 5.48 ms per loop
%%timeit
from numpy import linspace, rint, array, fromiter as fi
from scipy.misc import comb
from itertools import chain, combinations_with_replacement as cwr
cfi = chain.from_iterable
k = 4
d = 0.1
n = int(rint(1/d))
c = comb(n+k-1,k-1,exact=1)
B = linspace(0, 1, n+1)
W = lambda S: array(S+(1,))-array((0,)+S)
A = fi(cfi(W(S) for S in cwr(B,k-1)),dtype='float64',count=c*k).reshape((c,k))
100 loops, best of 3: 5.86 ms per loop
%%timeit
import numpy as np
def generate_alloc():
# Generate all numbers from 0 to 9999
A=range(10000)
# A4 represents the thousands, A3 represents the hundreds
# A2 represents the tens, A1 represents the units
# of all numbers between 0 and 9999
A1=np.multiply(1/10.,np.floor(np.multiply(1/1000.,np.remainder(A,10000))))
A2=np.multiply(1/10.,np.floor(np.multiply(1/100.,np.remainder(A,1000))))
A3=np.multiply(1/10.,np.floor(np.multiply(1/10.,np.remainder(A,100))))
A4=np.multiply(1/10.,np.floor(np.multiply(1/1.,np.remainder(A,10))))
# add the diagonal 1 matrix
A1=np.append(A1,[1.0,0.0,0.0,0.0])
A2=np.append(A2,[0.0,1.0,0.0,0.0])
A3=np.append(A3,[0.0,0.0,1.0,0.0])
A4=np.append(A4,[0.0,0.0,0.0,1.0])
# B will be the matrix
B=np.array([A1,A2,A3,A4])
# only take 'legal' allocation
C=B[:,np.sum(B,axis=0)==1.0]
return(C)
generate_alloc()
100 loops, best of 3: 9.71 ms per loop
%%timeit
import numpy as np
def findPartitions(n, k):
if k==1: return np.array([n])
if n==0: return np.repeat(0, k).reshape(1, -1)
res = np.empty(shape=(0, k), dtype=int)
for firstTerm in np.arange(n+1):
partialRes = findPartitions(n - firstTerm, k-1)
part1 = np.repeat(firstTerm, partialRes.shape[0])
part2 = np.column_stack((part1, partialRes))
res = np.vstack((res, part2))
return res
findPartitions(10, 4)/10.0
100 loops, best of 3: 11.2 ms per loop
%%timeit
def normalize_portfolio(portfolio):
normalized = portfolio.copy()
s = sum(portfolio.values())
for symbol, weight in portfolio.iteritems():
normalized[symbol] = 1.0 * weight / s
return normalized
def challenge(symbols,num_intervals):
'''Creates all valid portfolios for the given symbols.
I use integer numbers to avoid rounding problems and normalize afterwards.
'''
stack = []
stack.append((num_intervals,symbols[:],{}))
count = 0
portfolios = []
while(len(stack)>0):
(unallocated,unallocated_symbols,portfolio)=stack.pop()
if(len(unallocated_symbols)==0):
count+=1
# Here i test my portfolio. But for the challange let's just add
# the portfolio to a list.
portfolios.append(normalize_portfolio(portfolio))
else:
new_symbol = unallocated_symbols.pop()
# If this is the last symbol all must be allocated
allocate = 0 if len(unallocated_symbols) > 0 else unallocated
while(allocate <= unallocated):
new_portfolio = portfolio.copy()
new_portfolio[new_symbol] = allocate
stack.append((unallocated-allocate,unallocated_symbols[:],new_portfolio))
allocate += 1
return portfolios
# Execute for interval 0.1
portfolios10 = challenge(['GOOG', 'AAPL', 'XOM', 'GLD'],10) # for interval 0.1
100 loops, best of 3: 13.9 ms per loop
%%timeit
from numpy import indices
[append(x,10-sum(x))*0.1 for x in indices((11,11,11)).T.reshape((1331,3)) if sum(x) <= 10]
100 loops, best of 3: 18.2 ms per loop
%%timeit
import numpy as np
inc = 0.1
incs = np.arange(0, 1 + inc, inc)
test_allocs = np.around([[a, b, c, d]
for a in incs
for b in incs
for c in incs
for d in incs
if a + b + c + d == 1.0], 4)
10 loops, best of 3: 26.7 ms per loop
%%timeit
import itertools as it
all_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)))))
10 loops, best of 3: 135 ms per loop
%%timeit
import itertools
map(list, filter(lambda x: sum(x) == 1, itertools.product(np.linspace(0,1,11), repeat=4)))
1 loops, best of 3: 272 ms per loop
%%timeit
import numpy as np
portfolio = []
for index in np.ndindex(11, 11, 11, 11):
if (np.sum(index)==10):
portfolio.append(np.array(index)/float(10))
1 loops, best of 3: 339 ms per loop
%%timeit
import numpy as np
allocs = np.zeros((10000,4))
n = 0
for i in range(0,11):
for j in range(0,11):
for k in range(0,11):
for l in range(0,11):
row = [i/10.0,j/10.0,k/10.0,l/10.0]
if sum(row)==1.0:
allocs[n,:]=row
n = n+1
allocs = allocs[0:n,:]
1 loops, best of 3: 284 ms per loop