F #에서 매트릭스 계산 개선

Question

F #을 사용하여 몇 가지 기본 매트릭스 계산을 수행하는 코드를 작성했습니다. 계산 시간을 줄이기 위해이 코드에서 몇 가지 가능한 개선 사항이 있는지 알고 싶습니다. 실제로 수행되는 연산은 매우 기본입니다 (2 행렬의 곱셈과 주로 조옮김). 그러나 행렬의 크기는 (대략 10000 * 100000) 높으므로 계산 시간이 길어집니다 (몇 시간).

내 질문/발언은 다음과 같습니다

1. 다음 코드를 개선 할 수있는 방법이 있습니까? " 루프의 경우"알고리즘이 심각하게 느려질 수 있습니다. 그러나이은 "for 루프"를 피하는 방법을 모릅니다.
2. 초기 값이 0 인 초기 Matrix를 만들고 두 번째로 결과를 채 웁니다. 어쩌면 초기화의 첫 단계를 피할 수 있습니다. 여기

는 알고리즘 :

// I use the #time function to calculate the calculation duration of the algorithm 
#time 

#r "Microsoft.Office.Interop.Excel" 
#r "FSharp.PowerPack.dll" 

open System 
open System.IO 

open Microsoft.FSharp.Math 
open System.Collections.Generic 

// Algorithm 
let matrixCalculation (matA : matrix) (matB : matrix) (matC : matrix) = 

    // First step : Renamed the matrix A and B size to initialize the matrix "matrixCalcul" 
    let nbrOfElementsA = matA.NumRows 
    let nbrOfElementsB = matB.NumRows 
    let nbrOfCaracteristicsA = matA.NumCols 
    let nbrOfCaracteristicsB = matB.NumCols 

    // Second step : MatB has to be transposed 
    let tmatB = matB.Transpose 

    // Initialisation of the final output named matrixCalcul. A weighted vector is also initialised 
    let mutable matrixCalcul = Matrix.create (nbrOfElementsA + 1) (nbrOfElementsB + 1) 0.    
    let mutable weightedVector = Matrix.create nbrOfCaracteristicsA 1 0.     

    // The first column of matA and matB represents IDs, and are "copy/past" in matrixCalcul's first colum and first row respectively 
    matrixCalcul.[1.. ,0..0] <- matA.[0..,0..0] 
    matrixCalcul.[0..0,1 ..] <- matB.[0..,0..0].Transpose 

    // Then the core of the matrix named "matrixCalcul" can be calculated 
    for j = 0 to (nbrOfElementsB - 1) do 
     weightedVector <- matC * tmatB.[1..(nbrOfCaracteristicsB - 1),0..(nbrOfElementsB-1)].Columns(j,1)      
     for i = 0 to (nbrOfElementsA - 1) do 
      let mutable acc = matA.[0..(nbrOfElementsA - 1),1..(nbrOfCaracteristicsA-1)].Rows(i,1) * weightedVector     
      matrixCalcul.[i+1,j+1] <- (acc.[0,0]) 
    matrixCalcul 


// Two matrix generators (one for matA and matB and another one for matC) 

let matrixTestGeneratorAandB nbrOfElements nbrOfCaracteristics = 
    let matrixTestGeneratedAandB = Matrix.create nbrOfElements nbrOfCaracteristics 0. 
            |> Matrix.mapi (fun i j value -> if j = 0 then float(i + 1) elif j % 2 = 0 then 1. else 0.) 
    matrixTestGeneratedAandB 

let matrixTestGeneratorC nbrOfElements nbrOfCaracteristics = 
    let matrixTestGeneratedC = Matrix.create nbrOfElements nbrOfCaracteristics 0. 
           |> Matrix.mapi (fun i j value -> if j = 0 then 0. elif j % 2 = 0 then 1. else 0.) 
    matrixTestGeneratedC 


// Generation of matrixA, matrixB and matrixC 

let matrixA = matrixTestGeneratorAandB 100 179 

let matrixB = matrixTestGeneratorAandB 100 639 

let matrixC = matrixTestGeneratorC 178 638 

// Calculation 
matrixCalculation matrixA matrixB matrixC 

는 기본적으로 계산 지속 시간이 2 초 년경 금액,하지만 당신은 10000까지 matrixA 및 matrixB의 수를 변경하는 경우, 그것은 시간이 걸릴 수 있습니다. 정보를 위해서, 알고리즘에서 matrixC의 크기는 일정하게 유지 될 것이고, 행렬 A와 B 만 증가 할 수 있습니다.

개선에 대한 아이디어가 있다면 알려주세요.

Answer 1

코드에서 달성하려는 내용을 이해하는 것은 매우 어렵습니다. 나는 다음과 같이 행렬 d[0..m, 0..n]을 계산하는 의미 생각 :

(첫 번째 열을 손질 matA 후) 세 개의 행렬의 곱셈 matA1 핵심 부분 (내부 매트릭스 d[1..m, 1..n]) 인

+---------+-------------------------+ 
    | 0.0  | b00 b10 ...... b(n-1)0 | 
    +---------+-------------------------+ 
    | a00  | d11 d12 ...... d1n  | 
    | a10  | d21 d22 ...... d2n  | 
    | ...  | ... ... ...... ...  | 
    | ...  | ... ... ...... ...  | 
    | ...  | ... ... ...... ...  | 
    | a(m-1)0 | dm1 dm2 ...... dmn  | 
    +---------+-------------------------+ 

, matC 및 matB1 (matB 첫 번째 열을 다듬고 전치 한 후).

행렬 연산을 이해하려면 행렬 크기를 추론하는 것이 좋습니다. ra, ca, rb, cb, rc 및 cc 각각 matA, matB 및 matC에서 행과 열의 수를 나타내는 보자. 곱셈은 ​​크기가 ra x (ca-1), rc x cc 및 (cb-1) x rb 인 세 개의 행렬 중 하나입니다. rc = ca-1 및 cc = cb-1 인 경우에만 의미가 있습니다. 결과 행렬 d은 (ra+1) x (rb+1)입니다.

let calculate (matA : matrix) (matB : matrix) (matC : matrix) = 
    let ra = matA.NumRows 
    let ca = matA.NumCols 
    let rb = matB.NumRows 
    let cb = matB.NumCols 
    let matrixCalcul = Matrix.zero (ra+1) (rb+1) 

    matrixCalcul.[1.., 0..0] <- matA.[0.., 0..0] 
    matrixCalcul.[0..0, 1..] <- matB.[0.., 0..0].Transpose 

    matrixCalcul.[1.., 1..] <- (matA.Columns(1, ca-1) * matC) * matB.Columns(1, cb-1).Transpose 
    matrixCalcul 

I는 각각 matA, matB 및 matC 크기 200x279, 200x1279과 278x1238으로 테스트 한 :

여기에 어떤 for 루프를 사용하지 않고 내 시도이다. 두 버전은 동일한 결과를 가져오고 나의 기능은 원래 것보다 더 빠른 40x입니다. 그 이유는 여러 가지가 있지만 일반적으로 벡터화 된 버전은 행렬 계산과 관련하여 훨씬 뛰어난 성능을 제공합니다.