java - 文本搜索的运行时间非常慢 [优化]

Question

我想做什么

我有一个 8.5 GB 的巨大文本文件，其中包含 300 万行的单词格式，后跟 300 个数字，如下所示:

单词 0.056646 -0.0256464 0.05246(等等)

单词后面的 300 个数字构成一个表示单词的 vector 。我有 3 个词，我必须使用类比模型(我正在使用加法、乘法和方向)找到最接近代表第 4 个词的 vector 。

另外，它看起来像这样:

假设你有词 vector a、b 和 c，那么我会做 c - a + b。然后我将遍历所有 300 万行并使用余弦相似度通过寻找最大结果来找到第四个单词 d。所以它看起来像这样: d = max(cos(d', c-a+b)) 其中 d' 代表当前行的单词。

问题是什么

上述示例代表一个查询。我必须执行总共 20000 个查询。我不仅对加法类比模型执行它，还对乘法和方向执行它。当我运行我的程序时，它仍在尝试计算第一个查询的第一个类比模型(加法)的第 4 个词，总共耗时 30 秒!我的程序急需优化。

首先，我对 300 万行(3 次)进行简单迭代，以找到词 vector a、b 和 c 所需的 vector 。使用 System.nanoTime() 我了解到，对于这些 vector 中的每一个，找到一个 vector 大约需要 1.5 毫秒。找到全部 3 个大约需要 5 毫秒。

接下来，我使用自己编写的类在 vector 之间进行计算(我似乎没有找到任何处理 vector 计算的标准 API):

public class VectorCalculation {

    public static List<Double> plus(List<Double> v1, List<Double> v2){
        return operation(new Plus(), v1, v2);
    }

    public static List<Double> minus(List<Double> v1, List<Double> v2){
        return operation(new Minus(), v1, v2);
    }

    public static List<Double> operation(Operator op, List<Double> v1, List<Double> v2){
        if(v1.size() != v2.size())  throw new IllegalArgumentException("The dimension of the given lists are not the same.");
        List<Double> resultVector = new ArrayList<Double>();
        for(int i = 0; i < v1.size(); i++){
            resultVector.add(op.calculate(v1.get(i), v2.get(i)));
        }
        return resultVector;
    }
}

public interface Operator {
    public Double calculate(Double e1, Double e2);
}

public class Plus implements Operator {

    @Override
    public Double calculate(Double e1, Double e2) {
        return e1+e2;
    }
}

public class Minus implements Operator {

    @Override
    public Double calculate(Double e1, Double e2) {
        return e1-e2;
    }
}

vector 的计算在这里:

public class Addition extends AnalogyModel {

    @Override
    double calculateWordVector(List<Double> a, List<Double> b, List<Double> c, List<Double> d) {
        //long startTime1 = System.nanoTime();
        List<Double> result = VectorCalculation.plus(VectorCalculation.minus(c, a), b);
        //long endTime1 = System.nanoTime() - startTime1;
        double result2 = cosineSimilarity(d, result);
        //long endTime2 = System.nanoTime() - startTime1;
        //System.out.println(endTime1 + "       |       " + endTime2);
        return result2;
    }

    Double cosineSimilarity(List<Double> v1, List<Double> v2){
        if(v1.size() != v2.size())  throw new IllegalArgumentException("Vector dimensions are not the same.");

        // find the dividend
        Double dividend = dotProduct(v1, v2);

        // find the divisor
        Double divisor = dotProduct(v1, v1) * dotProduct(v2, v2);
        if(divisor == 0)    divisor = 0.0001;   // safety net against dividing by 0.

        return dividend/divisor;
    }

    /**
     * @return  Returns the dot product of two vectors.
     */
    Double dotProduct(List<Double> v1, List<Double> v2){
        System.out.println(v1);
        Double result = 0.0;
        for(int i = 0; i < v1.size(); i++){
            result += v1.get(i)*v2.get(i);
        }
        return result;
    }
}

计算结果所需的时间一开始很粗糙(大约 0.1 毫秒)，但很快下降到大约 0.025 毫秒。计算 result2 所需的时间通常也非常适中，大约为 0.005 毫秒。 d' 是通过遍历 300 万行并保存 vector 列表找到的。此操作大约需要 0.06 毫秒。

总结:完成一个查询所需的估计时间，对于一个类比模型，完成一个查询需要 5 + 3000000*(0.025 + 0.005 + 0.06) = 270005 毫秒或 270 秒或 4.5 分钟...考虑到我需要为其他类比模型再做两次，我总共需要做 20000 次，这显然是不够的。

文本文件中的单词没有排序。看起来 vector 计算量太大了，但是在文本文件中找到一个单词的 vector 所花费的时间也必须缩短。如果将文本文件拆分成较小的文件会有帮助吗？

更新 - 读取文件的代码

    /**
     * @param vocabularyPath    The path of the vector text file.
     * @param word              The word to find the vector for.
     * @return  Returns the vector of the given word as an array list.
     */
    List<Double> getStringVector(String vocabularyPath, String word) throws IOException{
        BufferedReader br = new BufferedReader(new FileReader(vocabularyPath));

        String input = br.readLine();
        boolean found = false;
        while(!found && input != null){
            if(input.contains(word))    found = true;
            else input = br.readLine();
        }

        br.close();
        if(input == null)   return null;
        else return getVector(input);
    }

    /**
     * @param inputLine A line from the vector text file.
     * @return  Returns the vector of the given line as an array list.
     */
    List<Double> getVector(String inputLine){
        String[] splitString = inputLine.split("\\s+");
        List<String> stringList = new ArrayList<>(Arrays.asList(splitString));
        stringList.remove(0); // remove the word at the front
        stringList.remove(stringList.size()-1); // remove the empty string at the end
        List<Double> vectorList = new ArrayList<>();
        for(String s : stringList){
            vectorList.add(Double.parseDouble(s));
        }
        return vectorList;
    }

Answer 1

有两个明显的问题:List<Double>和 Operator .

第一个表示 double 不是使用 8 个字节(顺便说一句。float 很可能会这样做)，你需要两倍多(一个包含值和引用的对象)。更糟糕的是:你失去了空间局部性，因为你的数字可能在内存中的任何地方。

第二个意味着您对每个点积执行 N 次虚拟调用。这可能不是当前的问题，但当您在运算符之间切换时，它可能会大大降低您的速度。

推荐

我猜你所有的 vector 都一样长，所以使用 double[] .您可以节省大量内存并获得不错的加速。

重写你的 operation类似

public static void operationTo(double[] result, Operator op, double[] v1, double[] v2){
    int length = result.length;
    if(v1.length != length || v2.length != length) {
        throw new IllegalArgumentException("The dimension of the given lists are not the same.");
    }
    switch (op) { // use an enum
        case PLUS:
            for(int i = 0; i < length; i++) {
                result[i] = v1[i] + v2[i];
            }
        break;
        ...
    }
}

查词

最快的方法是 HashMap<String, double[]> ，假设这一切都适合内存。否则，数据库(如已经建议的那样)可能是可行的方法。使用二进制搜索的排序文件也可以。但是，请注意除 Map 之外的任何其他解决方案。慢了 10 倍以上。

内存紧张时查词

你只有 3M 字，这很适合内存。将它们放入 ArrayList并对其进行排序。将 vector 写入按单词排序的二进制文件中。现在，要找到一个 vector ，您需要做的就是

long index = Arrays.binarySeach(wordList, word);
randomAccessFile.seek(index * vectorLength * Double.SIZE / Byte.SIZE)