java - 增加 n^2 次的算法

Question

好吧，我得到的代码基本上循环遍历 30,000 行文本，并且对于每一行，它遍历另一个文件中的 20,000,000 行文本以与之进行比较。

while(x.hasNextLine())
    while(y.hasNextLine())

其中 x 有 30,000 行，y 有 20,000,000 行。显然，这需要永远。现在我知道了更好的算法，但我试图将一个字符串与另一个字符串进行比较，所以这有点困难。我在 x 中拆分了一个字符串，在 y 中拆分了一个字符串。如果 x 的第 1 部分和 y 的第 2 部分相等，我会递增并做一些其他的事情。通常，x 在 y 中出现几百次左右。

那么，有什么想法吗？我尝试在每次通过后删除 y 中的行，然后重写文件，以便每次它在第二个循环中通过 less 进行解析，但显然这在编写 >500MB 的文件时没有帮助。

Answer 1

如果我没看错，您正在从磁盘读取 20M 行 (500MB) 文件 30,000 次？

如果 30k 的字符串小到足以保存在内存中，您可以反转循环的内部/外部位，并且只遍历 500MB 文件一次。假设 DiskIO 是瓶颈，这将节省大量时间。