This has a couple of twists which I personally found rather awkward... All code can be downloaded in a read-to-run format from here
The problem
Consider a classic interview question: "Find given pairs with a specific difference in a given array"
Here I impose the unique conditions:
- The array is non-decreasing
- Consider combinations not permutations
arr[i],arr[j] == arr[j],arr[i] - To make the operation more interesting, calculate the correlation function defined as
((arr[i]-mean_arr)*(arr[j]-mean_arr)).mean() - Consequently, when no pairs are found the return should be
np.nan
Benchmark Naiive Example
This will scale terribly but is easy to read
import itertools
import numpy as np
diff = 0.1 # difference
arr = np.linspace(0,1,11) # input array example
def naiiveFn(arr, diff, tol=1e-5):
# get all combinations of the list with itself
all_pairs = list(itertools.product(*[list(arr)]*2))
all_pairs = np.asarray(all_pairs)
# select all valid pairs
pairs = all_pairs[np.abs(np.diff(all_pairs, axis=1).ravel() - diff) < tol]
# calculate the correlation function ((pair1_i - mean)*(pair2_i - mean)).mean()
result = np.prod(pairs- arr.mean(), axis=1).mean()
return result
The target is speed speed speed!!!
Test cases
In this section I provide two examples for accuracy and performance testing
Performance
A good benchmark case to challenge performance requires a lot of varied separations but must hold the non-decreasing property.
The following provides a good example, where we want performance to scale well with n
diff = 0.1; n = 2000
perf_arr_small = np.cumsum(np.around(np.random.exponential(diff, n), 1))
and when run for our basic function
%timeit naiiveFn(perf_arr, diff)
1 loop, best of 3: 1.85 s per loop
A more challenging case is n > 20000: I ran naiiveFn at n=20000, went for a coffee break and it was still going when I came back!
Accuracy
Obviously a function is totally useless if if doesn't do what it is supposed to. This will test six cases that I picked to exhibit particular behaviours these are generated by running genTestData() from below
from scipy.special import binom
import numpy as np # it's beyond me that neither np.binom or math.binom exist
def testFn(results, test, res_pairs=None):
"""Takes in two arrays of your function results and compares to test data
If you pass the pairs you found to res_pairs it will also neatly display those
Required Inputs
results :: list :: list of results from test function
test :: list :: list of test cases to compare against
Optional Inputs
res_pairs :: list of lists/np.arrays :: list of pairs that were found
"""
outcomes = ["Failed","Passed"]
print "\nTest outcomes..."
if res_pairs is None: res_pairs = len(test)*[None]
for i,(r,t, pairs) in enumerate(zip(results, test, res_pairs)):
try:
np.testing.assert_almost_equal(r,t)
passed = True
except:
passed = False
pr = " test:{} :: {} :: res: {:7.4f} actual: {:7.4f}".format(i+1, outcomes[passed], r, t)
if pairs is not None: pr += " pairs: "+" ".join(["{:d}x({:3.1f} {:3.1f})".format(n,i,j) for (i,j),n in Counter(tuple(p) for p in pairs).iteritems()])
print pr
pass
def genTestData():
"""Generate test data
test_cases :: list of 6 test arrays each of length 10
test_set1 :: the four test cases with 0.1 separation
test_set2 :: the four test cases with no separation
"""
n = 10
# Examples to catch most common errors
a = np.array([0.1]*10) # case of everything the same
b = np.linspace(0.1, 1, 10) # everything spaced equally
c = np.array([0.1]*5+[0.2]*5) # intersection of two repeating segments
d = np.array([0.1, 0.2, 0.3] + [0.4]*5 + [0.5]*2) # a mash-up
e = np.array([0.4]*3 + [0.5]*3 + [0.6]*3 + [5]) # series of identicals
f = np.asarray([0, 0.2, 0.4, 0.6, 0.8] + [0.9]*3 + [1.0]*2) # no match then matches
# a quick function used a fair bit in the case of equal incrementation
equalSpacing = lambda seg, mean, sep: np.sum((seg[:seg.size-sep]-mean)*(seg[sep:]-mean))
nCr52 = binom(5,2) # ways of choosing n from r where order matters
nCr32 = binom(3,2)
dm = d.mean() # both means used a lot so declaring saves space
em = e.mean()
fm = f.mean()
# the test cases for 0.1 separation
sep = 0.1
t1a = np.nan
t1b = equalSpacing(b, b.mean(), 1)/float(n-1)
t1c = (0.1-c.mean())*(0.2-c.mean()) #*5**2/5**2
t1d = (equalSpacing(d[:3], dm, 1) + (.3-dm)*(.4-dm)*5. + 5.*2*(.4-dm)*(.5-dm))/(2.+5.+2.*5.)
t1e = ((0.4-em)*(0.5-em)*3.*3. + (0.5-em)*(0.6-em)*3*3)/(3.*3.+3.*3)
t1f = ((0.8-fm)*(0.9-fm)*3. + (0.9-fm)*(1.0-fm)*2.*3.)/(3.+2.*3.)
# test caess for 0 separation
sep = 0.0
t2a = 0.0
t2b = np.nan
t2c = ((0.1-c.mean())**2*nCr52 + (0.2-c.mean())**2*nCr52)/(nCr52+nCr52)
t2d = ((0.4-dm)**2*nCr52 + (.5-dm)**2)/(nCr52+1)
t2e = ((0.4-em)**2*nCr32 + (.5-em)**2*nCr32 + (0.6-em)**2*nCr32)/(3*nCr32)
t2f = ((0.9-fm)**2*nCr32 + (1.0-fm)**2)/(nCr32+1)
cases = [a,b,c,d,e, f]
test_set1 = [t1a, t1b, t1c, t1d, t1e, t1f]
test_set2 = [t2a, t2b, t2c, t2d, t2e, t2f]
return cases, test_set1, test_set2
abs(diff-sep) < tol): don't check forback < nto control the loop.) Re missing cases: specified difference 1 and a sequence like1, 1, 2, 2, 2, 4…looks challenging - one pair or six? \$\endgroup\$l_ansandr_ansare both just floats, so there isn't amean()method that can be called on their product. If that's the case, then this is off topic and I'm voting to close. \$\endgroup\$arras a tensor(n,M)wherenare the number of MCMC samples andMis the N-dim lattice \$\endgroup\$