如何加快這段代碼？微積分迭代遍歷矩陣的行和列

Question

我有一段代碼，它通過迭代遍歷行和列來對矩陣執行計算。執行的微積分是一個餘弦距離度量，我在Internet上找到的代碼（現在無法檢索鏈接）。

可以有10,000行和列。矩陣是對稱的，所以我只需要迭代它的一半。值是浮動的。

問題：它很慢（看起來需要3到6個小時）。任何人都可以指出我的改進？謝謝！

關於代碼的注意事項：它使用抽象類來實現靈活性：這樣，在單獨的類中定義的餘弦計算可以很容易地被另一個類替換。

代碼：

import Jama.Matrix; 
import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.concurrent.ExecutionException; 

public abstract class AbstractSimilarity { 

    HashSet<Triple<Double, Integer, Integer>> set = new HashSet(); 
    public ArrayList<Thread> listThreads = new ArrayList(); 

    public void transform(Matrix matrixToBeTransformed) throws InterruptedException, 
ExecutionException { 

     int numDocs = termDocumentMatrix.getColumnDimension(); 

     Main.similarityMatrix = new Matrix(numDocs, numDocs); 

     System.out.println("size of the matrix: " + numDocs + "x " + numDocs); 

     //1. iteration through all rows of the matrixToBeTransformed 
     for (int i = numDocs - 1; i >0 ; i--) { 
      System.out.println("matrix treatment... " + ((float) i/(float) numDocs * 100) + "%"); 

      //2. isolates the row i of this matrixToBeTransformed 
      Matrix sourceDocMatrix = matrixToBeTransformed.getMatrix(
        0, matrixToBeTransformed.getRowDimension() - 1, i, i); 



      // 3. Iterates through all columns of the matrixToBeTransformed 
//   for (int j = 0; j < numDocs; j++) { 
//    if (j < i) { 
// 
//     //4. isolates the column j of this matrixToBeTransformed 
//     Matrix targetDocMatrix = matrixToBeTransformed.getMatrix(
//       0, matrixToBeTransformed.getRowDimension() - 1, j, j); 


        //5. computes the similarity between this given row and this given column and writes it in a resultMatrix 
//     Main.resultMatrix.set(i, j, computeSimilarity(sourceDocMatrix, targetDocMatrix)); 
//    } else { 
//     Main.resultMatrix.set(i, j, 0); 

//    } 
// 
//   } 
     } 

做定義的計算類：

import Jama.Matrix; 

public class CosineSimilarity extends AbstractSimilarity{ 

    @Override 
    protected double computeSimilarity(Matrix sourceDoc, Matrix targetDoc) { 
    double dotProduct = sourceDoc.arrayTimes(targetDoc).norm1(); 
    double eucledianDist = sourceDoc.normF() * targetDoc.normF(); 
    return dotProduct/eucledianDist; 
    } 

} 

Answer 1

你似乎是處理正^ 3的算法。因爲你正在填充（半）矩陣。再次計算n，因爲填充每個元素的方法（點積/ fnorm）花費時間n。好消息是，因爲計算不依賴於對方，你可以多線程來加速。

public class DoCalc extends Thread 
{ 
    public Matrix localM; 
    int startRow; 
    int endRow; 
    public DoCalc(Matrix mArg, int startArg, int endArg) 
    { 
    localM=mArg; 
    startRow=startArg; 
    endRow=endArg; 
    } 

    public void doCalc() 
    { 
    //Pseudo-code 
    for each row from startRow to endRow 
     for each column 0 to size-1 
     result[i][j] = similarityCalculation 
    } 
    public void run() 
    { 
    doCalc(); 
    } 
} 

public void transform(Matrix toBeTransformed) 
{ 
    int numDocs = termDocumentMatrix.getColumnDimension(); 

    Main.similarityMatrix = new Matrix(numDocs, numDocs); 
    Vector<DoCalc> running = new Vector<DoCalc>(); 
    int blockSize = 10; 
    for (int x = 0; x < numDocs-1;x+=blockSize) 
    { 
    DoCalc tempThread = new DoCalc(toBeTransformed,x,(x+blockSize>numDocs-1)?numDocs-1:x+blockSize); 
    tempThread.start(); 
    running.add(tempThread); 
    } 

    for (DoCalc dc : running) 
    dc.join(); 

} 

重要提示：

這是一個非常幼稚的做法。如果你嘗試用你的大小的數組來運行它，它會產生1000個線程。您可以擺弄blockSize或查看線程池。

最好這會讓你多倍增加速度，4倍等。如果你想要數量級的增加，你將需要正確地分析和/或改變你的算法，以提高效率。鑑於你試圖執行的任務（在Matrix中的每個元素上運行相對昂貴的任務），後者可能是不可能的。

編輯：多線程將只會顯着提高速度，如果你是CPU綁定，並有一個核心坐在相對閒置的多核CPU。