파이썬에서 Min-plus 행렬 곱셈을 더 빠르게 만드는 방법은 무엇입니까?

Question

그래서 두 개의 행렬 A와 B가 있으며 여기에 주어진 최소값 곱을 계산하려고합니다 : Min-plus matrix multiplication. 이를 위해 다음을 구현했습니다 :

def min_plus_product(A,B): 
    B = np.transpose(B) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     Y[i] = (A + B[i]).min(1) 
    return np.transpose(Y) 

이 작업은 정상적으로 수행되었지만 큰 행렬에는 속도가 느립니다. 더 빠른 방법이 있습니까? 나는 C로 구현하거나 GPU를 사용하는 것이 좋은 선택이라고 들었다.

Answer 1

중간 크기가 충분하고 항목이 균일하게 분포되어있는 경우 조금 저장하는 알고리즘입니다. 가장 작은 합계는 일반적으로 두 가지 작은 용어에서 나올 것이라는 사실을 이용합니다.

import numpy as np 

def min_plus_product(A,B): 
    B = np.transpose(B) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     Y[i] = (A + B[i]).min(1) 
    return np.transpose(Y) 


def min_plus_product_opt(A,B, chop=None): 
    if chop is None: 
     # not sure this is optimal 
     chop = int(np.ceil(np.sqrt(A.shape[1]))) 
    B = np.transpose(B) 
    Amin = A.min(1) 
    Y = np.zeros((len(B),len(A))) 
    for i in range(len(B)): 
     o = np.argsort(B[i]) 
     Y[i] = (A[:, o[:chop]] + B[i, o[:chop]]).min(1) 
     if chop < len(o): 
      idx = np.where(Amin + B[i, o[chop]] < Y[i])[0] 
      for j in range(chop, len(o), chop): 
       if len(idx) == 0: 
        break 
       x, y = np.ix_(idx, o[j : j + chop]) 
       slmin = (A[x, y] + B[i, o[j : j + chop]]).min(1) 
       slmin = np.minimum(Y[i, idx], slmin) 
       Y[i, idx] = slmin 
       nidx = np.where(Amin[idx] + B[i, o[j + chop]] < Y[i, idx])[0] 
       idx = idx[nidx] 
    return np.transpose(Y) 

A = np.random.random(size=(1000,1000)) 
B = np.random.random(size=(1000,2000)) 

print(np.allclose(min_plus_product(A,B), min_plus_product_opt(A,B))) 

import time 
t = time.time();min_plus_product(A,B);print('naive {}sec'.format(time.time()-t)) 
t = time.time();min_plus_product_opt(A,B);print('opt {}sec'.format(time.time()-t)) 

샘플 출력 :

True 
naive 7.794037580490112sec 
opt 1.65810227394104sec 

Answer 2

가능한 간단한 numba 경로를 사용하는 것이다. 1000x1000 A의

from numba import autojit 
import numpy as np 
@autojit(nopython=True) 
def min_plus_product(A,B): 
    n = A.shape[0] 
    C = np.zeros((n,n)) 
    for i in range(n): 
     for j in range(n): 
      minimum = A[i,0]+B[0,j] 
      for k in range(1,n): 
       minimum = min(A[i,k]+B[k,j],minimum) 
      C[i,j] = minimum 
    return C 

타이밍은 B 행렬이다 :

1 개 루프 (3)의 기기 : 일본어 코드 루프 당 4.28 S

1 개 루프 (3)의 기기 : 루프 당 2.32의 numba 코드