大量迭代后，Java while 循环会随着时间的推移而显着变慢

Question

我的程序在 while 循环中逐行读取文本文件。然后它处理每一行并提取一些要写入输出的信息。它在 while 循环内所做的一切都是 O(1)，除了我认为是 O(N) 的两个 ArrayList indexOf() 方法调用。该程序在开始时以合理的速度(每 100 秒 100 万行)运行，但随着时间的推移它会急剧减慢。我在输入文件中有 70 M 行，因此循环迭代了 7000 万次。理论上这应该需要大约 2 个小时，但实际上需要 13 个小时。问题出在哪里？

这是代码片段:

BufferedReader corpus = new BufferedReader(
            new InputStreamReader(
                        new FileInputStream("MyCorpus.txt"),"UTF8"));

Writer outputFile = new BufferedWriter(new OutputStreamWriter(
            new FileOutputStream("output.txt"), "UTF-8"));

List<String> words = new ArrayList();
//words is being updated with relevant values here   

LinkedHashMap<String,Integer> DIC = new LinkedHashMap();
//DIC is being updated with relevant key-value pairs here    

String line = ""; 
while ((line = corpus.readLine()) != null)
    String[] parts = line.split(" ");
    if (DIC.containsKey(parts[0]) && DIC.containsKey(parts[1])) {

        int firstIndexPlusOne = words.indexOf(parts[0])+ 1;
        int secondIndexPlusOne = words.indexOf(parts[1]) +1;

        outputFile.write(firstIndexPlusOne +" "+secondIndexPlusOne+" "+parts[2]+"\n");
        } else { 
            notFound++;
            outputFile.write("NULL\n");
        }
    }
outputFile.close();

Answer 1

我假设你在你的 words ArrayList 中添加单词。

您正确地指出 words.indexOf 是 O(N)，这就是您的问题的原因。随着 N 的增加(您将单词添加到列表中)，这些操作需要的时间越来越长。

为避免这种情况，请保持列表排序并使用 binarySearch .

要保持排序，请对每个单词使用 binarySearch 来找出将其插入的位置。这使您的复杂性从 O(n) 到 O(log(N))。