performance - 如何以非常有效的方式比较排序文件(文件大小> 1GB)中的所有行

Question

假设输入文件是:

Hi my name NONE
Hi my name is ABC
Hi my name is ABC
Hi my name is DEF
Hi my name is DEF
Hi my name is XYZ

我必须创建以下输出:

Hi my name NONE 1
Hi my name is ABC 2
Hi my name is DEF 2
Hi my name is XYZ 1

一行中的字数可以从 2 到 10 不等。文件大小将超过 1GB。

如何在尽可能短的时间内获得所需的输出。我当前的实现使用 C++ 程序从文件中读取一行，然后将其与下一行进行比较。此实现的运行时间始终为 O(n)，其中 n 是文件中的字符数。

要缩短运行时间，下一个选项是使用 mmap。但在实现之前，我只是想确认是否有更快的方法来做到这一点？使用任何其他语言/脚本？

Answer 1

uniq -c filename | perl -lane 'print "@F[1..$#F] $F[0]"'

perl 步骤只是获取 uniq 的输出(看起来像“2 Hi my name is ABC”)并将其重新排序为“Hi my name is ABC 2”。您可以为其使用不同的语言，或者完全不使用它。

至于你关于运行时的问题，big-O 似乎放错了地方；肯定没有任何机会在 少于 的时间内扫描整个文件。 mmap 和 strchr 看起来像是常数因子加速的可能性，但基于 stdio 的方法可能已经足够好了，除非你的 stdio 很烂。

code for BSD uniq可以在这里说明。它使用 fgets、strcmp 和很少的变量来完成非常简单的工作。