☰

*********** 更新 ********

tag-icon • tag-icon bash awk performance sort
*********** 更新 ********

我需要对一个大的单词列表进行重复删除。我尝试了几个命令并做了一些研究Linux 中最快的“uniq”工具和如何删除大型多 GB 文本文件中的重复行？他们解释说，消除重复单词列表的最快方法似乎是使用awk.

awk  --> O(n) ?
sort --> O(n log n) ?

然而，我发现这似乎并非如此。这是我的测试结果：

time sort -u input.txt -o output.txt 
real    0m12.446s  
user    0m11.347s  
sys 0m0.906s**


time awk '!x[$0]++' input.txt > output.txt
real    0m47.221s  
user    0m45.419s  
sys 0m1.260s

所以使用sort -u速度快了3.7倍。为什么是这样？有没有更快的方法来进行重复数据删除？

*********** 更新 ********

正如有人在评论中指出的那样，可能我的单词列表已经在某种程度上进行了排序。为了排除这种可能性，我使用生成了两个单词列表随机数词表生成器.py。

List1 = 7 Mb  
List2 = 690 Mb

**Results AWK:**  
***List1***  
real    0m1.643s  
user    0m1.565s  
sys     0m0.062s

***List2***  
real    2m6.918s  
user    2m4.499s  
sys     0m1.345s

**Results SORT:**  
***List1***  
real    0m0.724s  
user    0m0.666s  
sys     0m0.048s

***List2***  
real    1m27.254s  
user    1m25.013s  
sys     0m1.251s

答案1

您问了错误的问题，或者在错误的堆栈中错误地提出了问题，这是在编程/堆栈溢出中提出的更好的问题，以便人们根据 awk 和排序中使用的算法为您提供答案。

PS：还可以使用 nawk、mawk 和 gawk 进行所需的操作，为我们提供更多“区域划分”的详细信息；）并使用最小值、最大值、平均值和标准差分别运行 100 次。

无论如何，回到当前的问题，来自 CompSci 210，它与所使用的算法有关。排序会根据大小和内存限制使用多种方法，将文件保存到磁盘中的临时文件中，以便在内存不足时进行合并排序，并且您必须查看源代码以了解什么特定的 sort(1) 命令在您运行它的特定操作系统上使用，但根据经验，它会尽可能多地加载到内存中，对其进行一些快速排序，写入磁盘，冲洗重复，然后在最后它将对小排序文件进行合并排序。因此，这里您将获得各个部分的 O(n*log2(N))，然后进行近似 O(n*log(n)) 合并操作

awk：x[$0]++ 机制“假设”使用散列。但是散列（假定的 O(1)“查找”操作）的问题在于冲突以及冲突的处理。当数据没有很好地传播，也没有填充存储桶等时，这可能会导致问题，并且在大型列表中，如果冲突处理不正确，则散列可能会成为一个大内存问题（并且您可能需要针对预期数据调整哈希算法），然后您需要查看实际哈希函数的性能，然后 O(1) 可能更接近于插入的 O(log(n))（即 O (1) 对于第一次搜索，如果它不存在，则添加它，这可能是 O(log(n)))，然后 n*O(1) 变为 an*O(log(n))= > O(n*log(n))，更不用说你也在以“解释”的方式做事:)

答案2

在突破一些严肃的脚本语言（Python/Perl/Raku，很可能在排序之后）之前，我会努力寻找如何使用sort -u（可能需要进一步的开关！）来完成任务，并且只有在看到对最高速度的绝对需要之后，我才会考虑其他替代方案。

答案3

速度差异是因为“排序”是一个命令（关联），而“awk”是一种编程语言（关联）。

“sort”命令接受输入并返回输出。而“awk”是一种编程语言，它首先解释代码（终端命令），然后开始对其进行处理。就那么简单。

相关内容