☰

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 工具，如下 -->刪除大型單字清單中重複項目的最快方法？

相關內容