文本搜索的运行时间非常慢 [优化]
Incredibly slow runtime on text search [Optimization]
我想做什么
我有一个 8.5 GB 的巨大文本文件，其中包含 300 万行的单词格式，后跟 300 个数字，如下所示：
word 0.056646 -0.0256464 0.05246（依此类推）
单词后面的 300 个数字构成一个表示单词的向量。我有 3 个词，我必须使用类比模型找到最接近代表第 4 个词的向量（我使用加法、乘法和方向）。
另外，它看起来像这样：
假设你有词向量a、b和c，那么我会做c - a + b。然后我将遍历所有 300 万行并使用余弦相似度通过寻找最大结果来找到第四个单词 d。所以它看起来像这样： d = max(cos(d', c-a+b)) 其中 d' 代表当前行的单词。
问题是什么
上述示例代表一个查询。我必须执行总共 20000 个查询。我不仅对加法类比模型执行它，还对乘法和方向执行它。当我 运行 我的程序时，它仍在尝试计算第一个查询的第一个类比模型（加法）的第 4 个词，总共耗时 30 秒！我的程序急需优化。
首先，我对 300 万行（3 次）进行简单迭代，以找到词向量 a、b 和 c 所需的向量。使用 System.nanoTime() 我了解到，对于这些向量中的每一个，找到一个向量大约需要 1.5 毫秒。找到全部 3 个大约需要 5 毫秒。
接下来我做一个向量之间的计算，使用我自己写的类（我好像没有找到处理向量计算的标准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;
}
}
向量的计算在这里：
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;
}
}
计算 result 所需的时间开始时很粗糙（大约 0.1 毫秒），但很快下降到大约 0.025 毫秒。计算 result2 所需的时间通常也非常适中，大约为 0.005 毫秒。 d' 是通过遍历 300 万行并保存矢量列表找到的。此操作大约需要 0.06 毫秒。
总结一下：完成一个查询的估计时间，对于一个类比模型，完成一个查询需要 5 + 3000000*(0.025 + 0.005 + 0.06) = 270005 毫秒或 270 秒或 4.5 分钟。 .. 考虑到我需要为其他类比模型再做两次，我总共需要做 20000 次，这显然是不够的。
文本文件中的单词没有排序。看起来向量计算量太大了，但是在文本文件中找到一个单词的向量所花费的时间也必须缩短。如果将文本文件拆分成较小的文件会有帮助吗？
更新 - 读取文件的代码
/**
* @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;
}
有两个明显的问题：List<Double>和Operator。
第一个意思是，不用 8 个字节用于 double（顺便说一句，float 很可能会这样做），你需要两倍多的空间（一个包含值和 a 的对象）参考）。更糟糕的是：您失去了 space 位置，因为您的号码可能在内存中的任何位置。
第二个意味着你为每个点积执行N个虚拟调用。这可能不是当前的问题，但是当您在运算符之间切换时，它可能会大大降低您的速度。
推荐
我猜你所有的向量都一样长，所以使用 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 并进行排序。将向量写入按单词排序的二进制文件中。现在，要找到一个向量，您需要做的就是
long index = Arrays.binarySeach(wordList, word);
randomAccessFile.seek(index * vectorLength * Double.SIZE / Byte.SIZE)
所以你试图在 300 维 space 的一组 300 万个坐标中回答 20000 nearest neighbor searches？
为每个查询遍历整个数据集肯定会很慢。通过将数据集插入可以有效回答最近邻查询的数据结构，例如 Ball Tree.
，您可能会获得最大的加速。
我想做什么
我有一个 8.5 GB 的巨大文本文件，其中包含 300 万行的单词格式，后跟 300 个数字，如下所示：
word 0.056646 -0.0256464 0.05246（依此类推）
单词后面的 300 个数字构成一个表示单词的向量。我有 3 个词，我必须使用类比模型找到最接近代表第 4 个词的向量（我使用加法、乘法和方向）。
另外，它看起来像这样：
假设你有词向量a、b和c，那么我会做c - a + b。然后我将遍历所有 300 万行并使用余弦相似度通过寻找最大结果来找到第四个单词 d。所以它看起来像这样： d = max(cos(d', c-a+b)) 其中 d' 代表当前行的单词。
问题是什么
上述示例代表一个查询。我必须执行总共 20000 个查询。我不仅对加法类比模型执行它，还对乘法和方向执行它。当我 运行 我的程序时，它仍在尝试计算第一个查询的第一个类比模型（加法）的第 4 个词，总共耗时 30 秒！我的程序急需优化。
首先，我对 300 万行（3 次）进行简单迭代，以找到词向量 a、b 和 c 所需的向量。使用 System.nanoTime() 我了解到，对于这些向量中的每一个，找到一个向量大约需要 1.5 毫秒。找到全部 3 个大约需要 5 毫秒。
接下来我做一个向量之间的计算，使用我自己写的类（我好像没有找到处理向量计算的标准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;
}
}
向量的计算在这里：
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;
}
}
计算 result 所需的时间开始时很粗糙（大约 0.1 毫秒），但很快下降到大约 0.025 毫秒。计算 result2 所需的时间通常也非常适中，大约为 0.005 毫秒。 d' 是通过遍历 300 万行并保存矢量列表找到的。此操作大约需要 0.06 毫秒。
总结一下：完成一个查询的估计时间，对于一个类比模型，完成一个查询需要 5 + 3000000*(0.025 + 0.005 + 0.06) = 270005 毫秒或 270 秒或 4.5 分钟。 .. 考虑到我需要为其他类比模型再做两次，我总共需要做 20000 次，这显然是不够的。
文本文件中的单词没有排序。看起来向量计算量太大了，但是在文本文件中找到一个单词的向量所花费的时间也必须缩短。如果将文本文件拆分成较小的文件会有帮助吗？
更新 - 读取文件的代码
/**
* @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;
}
有两个明显的问题：List<Double>和Operator。
第一个意思是，不用 8 个字节用于 double（顺便说一句，float 很可能会这样做），你需要两倍多的空间（一个包含值和 a 的对象）参考）。更糟糕的是：您失去了 space 位置，因为您的号码可能在内存中的任何位置。
第二个意味着你为每个点积执行N个虚拟调用。这可能不是当前的问题，但是当您在运算符之间切换时，它可能会大大降低您的速度。
推荐
我猜你所有的向量都一样长，所以使用 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 并进行排序。将向量写入按单词排序的二进制文件中。现在，要找到一个向量，您需要做的就是
long index = Arrays.binarySeach(wordList, word);
randomAccessFile.seek(index * vectorLength * Double.SIZE / Byte.SIZE)
所以你试图在 300 维 space 的一组 300 万个坐标中回答 20000 nearest neighbor searches？
为每个查询遍历整个数据集肯定会很慢。通过将数据集插入可以有效回答最近邻查询的数据结构，例如 Ball Tree.
，您可能会获得最大的加速。