我有一段代码,它通过迭代矩阵的行和列来对矩阵执行计算。执行的演算是一个余弦距离测量,使用我在互联网上找到的代码(现在无法检索链接)。
可以有10000行和col。矩阵是对称的,所以我只需要迭代它的一半。值是浮动的。
问题是:它非常慢(看起来需要3到6个小时)。有人能告诉我改进的地方吗?Thx!
代码上的注意事项:它使用了一个抽象类来实现灵活性:这样,在一个单独的类中定义的余弦计算就可以很容易地被另一个类取代。
代码:
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;
}
}
您似乎正在处理一个n^3算法。n^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倍等。如果你想要数量级的增益,你需要正确地配置和/或将你的算法更改为更高效的算法。考虑到您要执行的任务(在矩阵中的每个元素上运行一个相对昂贵的任务),后者可能是不可能的。
编辑:多线程只会显著提高速度,如果你有cpu限制,并且有一个核心相对空闲的多核cpu。