algorithm - 在两个给定的输入文件中搜索公共(public)字符串

Question

我有两个大小为 20Gb 的文件。我必须在其中搜索公共(public)字符串。假设字符串的最大长度为 20 字节。所以为了解决这个问题，我使用了以下算法，我使用的是具有四核 i3 CPU 的 8GB RAM 系统。

sort the files using any suitable sorting utility
open files A and B for reading
read wordA from A
read wordB from B
while (A not EOF and B not EOF)
{
    if (wordA < wordB)
        read wordA from A
    else if (wordA > wordB)
        read wordB from B
    else
        /* match found, store it into some other files */
        write wordA into output
        read wordA from A
}

当我在 6Gb RAM 和 120GB 可用磁盘空间以及 6 核 i3 处理器的系统中运行此算法时，上述系统配置成功运行......我的系统多次关闭。为什么会这样？

请告诉我任何其他解决此问题的方法!我们可以提高它的性能吗？

Answer 1

是的，您可以使用非常短的 awk 1-liner 显着提高性能

awk 'FNR==NR{a[$0]++;next}a[$0]' file1 file2

使用 awk，您可以找到唯一的行，而无需先对它们进行排序。你并没有真正说出你想用公共(public)线做什么，所以我只是假设你想把它们打印出来。

如果你只想打印出一个公共(public)行一次，不管它重复多少次你可以使用这个:

awk 'FNR==NR{a[$0]=1;next}a[$0]-- > 0' file1 file2