как ускорить этот код? исчисление итерации по строкам и столбцам матрицы

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^2, потому что вы заполняете (половину) матрицу. Times n снова, потому что методы заполнения каждого элемента (dot product/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 раза и т. Д. Если вы хотите получить прирост порядка, вам нужно будет правильно профилировать и/или изменить свой алгоритм на что-то более эффективное. Учитывая задачу, которую вы пытаетесь выполнить (работа относительно относительно дорогостоящей задачи для каждого элемента в матрице), последнее может оказаться невозможным.

Редактирование: многопоточность будет значительно увеличивать скорость, если вы привязаны к процессору и имеете многоядерный процессор с ядрами, сидящими относительно холостым.