☰

Linux 中最快的“uniq”工具

tag-icon • tag-icon sed awk memory sort uniq
Linux 中最快的“uniq”工具

我有一个很大的文本文件（1.5 G），

我想知道 Linux 中最快、更可靠的工具是什么。

我通常使用：

awk '!x[$0]++' file.txt

但是当我使用htop命令时，我发现我的内存使用量正在增加。

我想知道对于大文件来说最快、更可靠的是什么。

uniq?
sort?
sed?
awk?

为什么？

答案1

让我们考虑一下每个解决方案的工作原理。

  • uniq这要求文件已经排序。如果没有，则必须sort先通过管道将其通过，这意味着sort必须将整个文件读入内存，重新排序（O(n log n)），然后将其写入管道。的工作uniq非常便宜，因为它只需要比较其输入的相邻行。

  • sort -u这结合了 的工作sort | uniq。这必须像脚本一样将所有唯一的输入收集到内存中awk，但它也会在生成输出之前浪费时间对它们进行排序。O(n log n)尽管在本例中n是唯一项的数量，而不是所有输入的数量，但这是。所以它比管道更好。

  • sed我不知道你为什么列出这个，因为我根本想不出一个好方法来做到这一点sed。也许如果您首先对其进行排序并通过管道传输到sed脚本，则可以通过一种方法来比较相邻行。因此，我们sed只会做该uniq做的事情，而且uniq可能会尽可能高效地做。

  • awk这可能是最好的，因为它只完成最少的必要工作。当它读取每一行时，它会进行有效的哈希查找，以查看该行是否已在其内存中，并且仅将唯一的行存储为哈希键，并将计数器存储为值。 （如果该行以前不存在，则条件将为真，因此该行将被打印。否则不会。）这会占用O(n)时间和O(uniq n)内存。

每种方法都会使用大量内存，要么用于对输入进行排序，要么用于跟踪已看到的输入，以便删除重复项。

答案2

我只是想指出 gnuuniq看起来非常慢，即使在排序列表上也是如此。

我只是尝试从排序的文件名列表中获取目录前缀列表：

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/s]

sort -u 似乎是 uniq 的两倍，这是从 stdin 读取排序并写入 stdout，所以我还没有看到它进行任何并行化。我不知道为什么 uniq 应该比排序慢得多，因为它不必对列表进行排序......

该命令的输出非常小（有很多重复项），只有264kb，并且排序在pv完成后立即终止。

如果你改变命令的顺序，速度仍然相同，我的流程受这里的 cpu 时间限制，而不是磁盘访问和缓存（我只有 8GB RAM 并且我的交换区未使用）

我在带有 gnu coreutils sort 和 uniq 以及 gnu awk 的 fedora 31 机器上运行它；区域设置设置为 en_US.UTF-8

更新，因为这让我很感兴趣，所以我做了一些更多的测试，让我们把剪切的部分移开，并确保文件被很好地排序

cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test

这需要 8.4 分钟。测试现在7.9GB大

让我们在文件上而不是在管道中运行这些工具，这将允许这些工具进行更多优化，例如排序将是多线程的。也来自更快的固态硬盘。

您可能没有注意到 sort 也占用了大量内存，因为它对 /tmp 中的临时文件进行了巧妙的处理，这些临时文件可能是 tmpfs 并且将位于您的 ram 中（尝试对大于 /tmp 的文件进行排序，您将遇到空间问题，这就是为什么我需要上面命令中的 -T 标志）

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

所以它看起来你的 awk 解决方案是这 3 个中最快的，并且实际上使用最少的内存

更新2 现在有一个更简单的语言环境

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

这次uniq确实赢得了比赛...正如 Stéphane Chazelas 在评论中暗示的那样，将语言环境设置为 C 可以使排序和 uniq 更快！

答案3

我发现 sort 似乎是最快的 uniq 工具，如下所示 -->删除大型单词列表中重复项的最快方法？

相关内容