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

Question

У меня есть кусок кода, который выполняет вычисления на матрице, просматривая ее строки и столбцы. Выполненное исчисление - это мера косинусного расстояния с кодом, который я нашел в Интернете (не удалось получить ссылку прямо сейчас).

Там может быть 10000 строк и цв. Матрица симметрична, поэтому мне просто нужно повторить половину. Значения являются плавающими.

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

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