在大量迭代之后,Java while循环会随着时间的推移而显着减慢

Question

我的程序在while循环中逐行读取文本文件.然后它处理每一行并提取要在输出中写入的一些信息.它在while循环中所做的一切都是O(1),除了两个我认为是O(N)的ArrayList indexOf()方法调用.该程序在开始时以合理的速度运行(每100秒1M行),但随着时间的推移它会大幅减速.我在输入文件中有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))。