Улучшение расчета матрицы в F #

Question

Я написал код для выполнения базовых вычислений Matrix с использованием F #.Я хотел бы знать, есть ли некоторые возможные улучшения в этом коде, чтобы уменьшить время расчета.Действительно, выполняемые операции довольно просты (умножение 2 матриц и в основном транспонирование), однако размеры матрицы велики (около 10000 * 100000), что приводит к огромной продолжительности вычислений (несколько часов).

Мои вопросы / замечанияследующие:

1. Есть ли способ улучшить следующий код?Есть много «для циклов», которые могут привести к серьезному замедлению алгоритма, но я не знаю, как избежать этих «для циклов».
2. Я создал некоторую начальную Матрицу с начальными значениями в 0и, во второй раз, заполнил их элементы результатами.Возможно, можно избежать первого шага инициализации.

Вот алгоритм:

// 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 секунд, но если вы изменитеКоличество matrixA и matrixB до 10000, это может занять час.Просто для информации, в моем алгоритме размер matrixC будет оставаться постоянным, только матрицы A и B могут иметь растущее число строк.

Если у вас есть идеи по улучшению, я так понимаю.

Answer 1

Из вашего кода довольно сложно понять, чего вы пытаетесь достичь.Я думаю, что вы хотите вычислить матрицу d[0..m, 0..n] следующим образом:

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

, где основная часть (внутренняя матрица d[1..m, 1..n]) является умножением трех матриц matA1 (matA после обрезки)первые столбцы), 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).

Вот моя попытка без использования какой-либо петли for:

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

Я тестировал с matA, matB и matC размером 200х279, 200х1279 и 278х1238 соответственно.Две версии дают одинаковый результат, и моя функция на 40x быстрее, чем оригинальная.Для этого есть много причин, но в целом векторизованная версия имеет гораздо лучшую производительность, когда дело доходит до вычисления матрицы.