このコードをスピードアップする方法は？行列の行と列を反復する計算法

Question

行列と行を繰り返して行列を計算するコードがあります。実行された計算の一部は、コサイン距離測定であり、インターネット上で見つけたコードを使用しています（リンクをすぐに取得できませんでした）。

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を扱うように見えます。あなたが（半）マトリックスを埋めるので、n^2です。各要素（ドットプロダクト/ fnorm）を満たすメソッドが時間nを要するため、再び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が比較的アイドル状態に座っている場合はマルチスレッドのみが大幅に速度が向上します。