Python Numpy 向量化组合学的嵌套 for 循环

Question

给定一个 nxn 数组 A 的实数正数，我试图找到二维数组三行的所有组合的元素最小值的最大值中的最小值。使用 for 循环，结果是这样的:

import numpy as np

n = 100
np.random.seed(2)
A = np.random.rand(n,n)
global_best = np.inf

for i in range(n-2):
    for j in range(i+1, n-1):
        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

在 n = 100 的情况下，输出应该是这样的:

Out[]: 0.492652949593 [6, 41, 58]

不过我有一种感觉，我可以使用 Numpy 向量化更快地完成这项工作，并且我当然会感谢任何帮助。谢谢。

Answer 1

此解决方案对于 n=100 快 5 倍:

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]

第一行有点复杂，但将 itertools.combinations 的结果转换为 NumPy 数组，其中包含所有可能的 [i,j,k] 索引组合。

从那里开始，使用所有可能的索引组合索引到 A，然后沿适当的轴减少是一件简单的事情。

此解决方案在构建所有可能组合的具体数组 A[coms] 时会消耗更多内存。对于较小的 n，例如低于 250，它可以节省时间，但是对于较大的 n，内存流量会非常高，并且可能比原始代码慢。