python - 找到三个“连接”矩阵的最大最小值的最快方法
问题描述
这个问题给出了两个矩阵的答案,但我不确定如何将此逻辑应用于三个成对连接的矩阵,因为没有“自由”索引。我想最大化以下功能:
f(i, j, k) = min(A(i, j), B(j, k), C(i,k))
其中A
,B
和C
是矩阵,i
,j
和k
是范围到矩阵各自维度的索引。我想找到(i, j, k)
最大化f(i, j, k)
的。我目前这样做如下:
import numpy as np
import itertools
I = 100
J = 150
K = 200
A = np.random.rand(I, J)
B = np.random.rand(J, K)
C = np.random.rand(I, K)
# All the different i,j,k
combinations = itertools.product(np.arange(I), np.arange(J), np.arange(K))
combinations = np.asarray(list(combinations))
A_vals = A[combinations[:,0], combinations[:,1]]
B_vals = B[combinations[:,1], combinations[:,2]]
C_vals = C[combinations[:,0], combinations[:,2]]
f = np.min([A_vals,B_vals,C_vals],axis=0)
best_indices = combinations[np.argmax(f)]
print(best_indices)
[ 49 14 136]
这比遍历 all 更快(i, j, k)
,但是很多(也是大部分)时间都花在了构建_vals
矩阵上。这是不幸的,因为它们包含许多相同的重复值i
,j
并且k
出现多次。有没有办法做到这一点,(1)可以保留 numpy 矩阵计算的速度,(2)我不必构造内存密集型_vals
矩阵。
在其他语言中,您也许可以构造矩阵,以便它们包含指向和的指针A
,但我不知道如何在 Python 中实现这一点。B
C
编辑:在此处查看更多索引的后续问题
解决方案
我们可以使用广播暴力破解它,也可以numpy
尝试一些智能分支切割:
import numpy as np
def bf(A,B,C):
I,J = A.shape
J,K = B.shape
return np.unravel_index((np.minimum(np.minimum(A[:,:,None],C[:,None,:]),B[None,:,:])).argmax(),(I,J,K))
def cut(A,B,C):
gmx = min(A.min(),B.min(),C.min())
I,J = A.shape
J,K = B.shape
Y,X = np.unravel_index(A.argsort(axis=None)[::-1],A.shape)
for y,x in zip(Y,X):
if A[y,x] <= gmx:
return gamx
curr = np.minimum(B[x,:],C[y,:])
camx = curr.argmax()
cmx = curr[camx]
if cmx >= A[y,x]:
return y,x,camx
if gmx < cmx:
gmx = cmx
gamx = y,x,camx
return gamx
from timeit import timeit
I = 100
J = 150
K = 200
for rep in range(4):
print("trial",rep+1)
A = np.random.rand(I, J)
B = np.random.rand(J, K)
C = np.random.rand(I, K)
print("results identical",cut(A,B,C)==bf(A,B,C))
print("brute force",timeit(lambda:bf(A,B,C),number=2)*500,"ms")
print("branch cut",timeit(lambda:cut(A,B,C),number=10)*100,"ms")
事实证明,在给定的尺寸下,分支切割是非常值得的:
trial 1
results identical True
brute force 169.74265850149095 ms
branch cut 1.951422297861427 ms
trial 2
results identical True
brute force 180.37619898677804 ms
branch cut 2.1000938024371862 ms
trial 3
results identical True
brute force 181.6371419990901 ms
branch cut 1.999850495485589 ms
trial 4
results identical True
brute force 217.75578951928765 ms
branch cut 1.5871295996475965 ms
树枝切割是如何工作的?
我们选择一个数组(比如 A)并从大到小对它进行排序。然后,我们逐个遍历数组,将每个值与其他数组中的适当值进行比较,并跟踪最小值的运行最大值。只要最大值不小于 A 中的其余值,我们就完成了。由于这通常会很快发生,因此我们会节省大量资金。
推荐阅读
- sql - 快速 SQLite 数据库更新
- postman - 邮递员收集异步运行
- tensorflow - 如何在 tensorfow keras 中添加 2 个模型路径?
- rest - 在浏览器和 NodeJS 或 curl 中使用 Stack Exchange API 时的不同数据格式
- html - HTML 视频在 iPhone 上不可见
- vue.js - 折线图不呈现数据
- asp.net-core - Strict-Transport-Security 标头没有价值
- grpc - 如何为 grpc-java 客户端指定 User-Agent 标头?
- algorithm - 如何找到从 2 到 N + 1 的组总数
- r - 如何在大数据集中找到 30 个最常见的值?