Given an nxn array A of real positive numbers, I'm trying to find the minimum of the maximum of the element-wise minimum of all combinations of three rows of the 2-d array. Using for-loops, that comes out to something like this:
import numpy as np n = 100 np.random.seed(2) A = np.random.rand(n,n) global_best = 1000000000000000.0 # print(A) for i in range(n): for j in range(i+1, n): for k in range(j+1, n): # find the maximum of the element-wise minimum of the three vectors local_best = np.amax(np.array([A[i,:], A[j,:], A[k,:]]).min(0)) # if local_best is lower than global_best, update global_best if (local_best < global_best): global_best = local_best save_rows = [i, j, k] print global_best, save_rows
In the case for
n = 100, the output should be this:
Out: 0.492652949593 [6, 41, 58]
I have a feeling though that I could do this much faster using Numpy vectorization, and would certainly appreciate any help on doing this. Thanks.
This solution is 5x faster for
coms = np.fromiter(itertools.combinations(np.arange(n), 3), 'i,i,i').view(('i', 3)) best = A[coms].min(1).max(1) at = best.argmin() global_best = best[at] save_rows = coms[at]
The first line is a bit convoluted but turns the result of
itertools.combinations into a NumPy array which contains all possible
[i,j,k] index combinations.
From there, it's a simple matter of indexing into
A using all the possible index combinations, then reducing along the appropriate axes.
This solution consumes a lot more memory as it builds the concrete array of all possible combinations
A[coms]. It saves time for smallish
n, say under 250, but for large
n the memory traffic will be very high and it may be slower than the original code.