java - 优化大数据集的搜索技术

Question

我目前正在开发一个项目，需要处理大约 300 万行长的 .csv 文件和大小范围在 10 行到超过 1000 行之间的不同 .xlsx 文件。我试图找到 .xlsx 文件和 .csv 文件中不同单元格之间的共性。去做这个。我已读取 .csv 文件和 .xslx 文件并将它们存储在 ArrayLists 中。我有我想要的工作，但是我使用的方法是 O(n^3)，使用 3 个嵌套的 for 循环在每个循环之间进行搜索。

//This is our .xlsx file stored in an ArrayList
for(int i = 1; i<finalKnowledgeGraph.size(); i+=3) {
            //loop through our knowledgeGraph again
            for(int j = 1; j<finalKnowledgeGraph.size(); j+=3) {
                //loop through .csv file which is stored in an ArrayList
                for(int k=1; k<storeAsserions.size(); k++) {
                   if(finalKnowledgeGraph.get(i).equals(storeAsserions.get(k)) && finalKnowledgeGraph.get(j+1).equals(storeAsserions.get(k+1))){
                      System.out.println("Do Something");
                   } else if(finalKnowledgeGraph.get(i+1).equals(storeAsserions.get(k)) && finalKnowledgeGraph.get(j).equals(storeAsserions.get(k+1))) {
                       System.out.println("Do something else");
                   }
                }
            }
        }

目前，在我的实际代码中，我的 System.out.println("Do Something") 只是将每个文件的特定部分写入新的 .csv 文件。

现在，我正在做的事情是我的问题是优化。显然，如果我在数百万个输入上运行一个 3 嵌套的 for 循环，它在我的一生中不会完成运行，所以我想知道我可以通过什么方法来优化代码。

我的一位 friend 建议将文件存储在内存中，这样读/写速度会快几倍。另一位 friend 建议将文件存储在哈希表而不是 ArrayList 中，以帮助加快该过程，但由于我基本上是在所述哈希表中搜索每个元素，所以我不知道这将如何加快该过程。看起来它将把搜索从一种数据结构转移到另一种数据结构。不过我说我也会在这里发布问题，看看人们是否对我如何优化这段代码有任何提示/建议。谢谢

注意:我本人对优化等一无所知，而且我发现有关 S/O 的其他问题对于我在该领域的知识来说过于具体，因此如果问题看起来重复，我可能已经看到了您的问题正在谈论已经无法理解的内容

编辑:存储在两个 ArrayList 中的所有内容都是动词:名词:名词对，我试图在每个 ArrayList 之间比较名词。由于我不关心动词，因此我从索引 1 开始搜索。(仅用于某些上下文)

Answer 1

一种可能的解决方案是使用数据库，只要有适当的索引，数据库就可以非常快地进行搜索。假设数据适合内存，您甚至可以更快。

原理

对于诸如此类的问题

for (X x : xList) {
    for (Y y : yList) {
        if (x.someAttr() == y.someAttr()) doSomething(x, y);
    }
}

您只需根据属性将一个列表划分为多个存储桶

Map<A, List<Y>> yBuckets = new HashMap<>();
yList.forEach(y -> yBuckets.compute(y.someAttr(), (k, v) ->
    (v==null ? new ArrayList<>() : v).add(y));

现在，您迭代另一个列表，并且只查看适当存储桶中的元素，例如

for (X x : xList) {
    List<Y> smallList = yBucket.get(x.someAttr());
    if (smallList != null) {
        for (Y y : smallList) {
            if (x.someAttr() == y.someAttr()) doSomething(x, y);
        }
    }
}

实际上可以省略比较，因为它总是正确的，但这不是重点。速度来自于消除并查看 equals 返回 false 的情况。

复杂性从二次降低到线性，再加上调用 doSomething 的次数。

您的案例

你的数据结构显然不适合。您将三元组扁平化为一个列表，这是错误的。您当然可以以某种方式解决它，但是创建一个 class Triplet {String verb, noun1, noun2} 会使一切变得更简单。对于 storeAsserions，看起来您正在使用成对的操作。它们似乎重叠，但这可能是一个错字，无论如何没关系。让我们使用三元组和对。

让我也重命名您的列表，以便代码更适合这个小窗口:

for (Triplet x : fList) {
    for (Triplet y : fList) {
        for (Pair z : sList) {
            if (x.noun1.equals(z.noun1) && y.noun2.equals(z.noun2)) {
                doSomething();
            } else if (x.noun2.equals(z.noun1) && y.noun1.equals(z.noun2)) {
                doSomethingElse();
            }
        }
    }
}

现在，我们需要对存储桶进行一些循环，以便至少有一个 equals 测试始终为 true，这样我们就不用处理不匹配的数据了。让我们集中讨论第一个条件

x.noun1.equals(z.noun1) && y.noun2.equals(z.noun2)

我建议像这样的循环

for (Pair z : sList) {
    for (Triplet x : smallListOfTripletsHavingNoun1SameAsZ) {
        for (Triplet y : smallListOfTripletsHavingNoun2SameAsZ) {
            doSomething();
        }
    }
}

小列表的计算方式与第一部分类似。

不会比较任何不匹配的条目，因此复杂性从立方减少到匹配数(= 到您的代码将打印的行数)。

附录 -yBuckets

假设 xList 看起来像

[
  {id: 1, someAttr: "a"},
  {id: 2, someAttr: "a"},
  {id: 3, someAttr: "b"},
]

那么yBuckets应该是

{
  "a": [
    {id: 1, someAttr: "a"},
    {id: 2, someAttr: "a"},
  ],
  :b": [
    {id: 3, someAttr: "b"},
  ],
}

一种简单的方法，如何创建这样的 map

yList.forEach(y -> yBuckets.compute(y.someAttr(), (k, v) ->
   (v==null ? new ArrayList<>() : v).add(y));

明文:

• 对于 yList 中的每个 y，
• 以(k, v)的形式获取对应的 map 条目,
• 当v为null时，则创建一个新的List
• 否则使用列表v
• 无论如何，请添加 y
• 并将其存储回 map (除非在第三步中创建新列表，否则这是无操作)。