linux - 计算日志中最前面的重复行

Question

阅读标题会让您思考，这个问题我看了一百遍，您也看到了，但我正在寻找不同的东西:

常见的答案是

sort <input> | uniq -c | sort -nr

但是当输入是几千万行的时候，排序就变得不切实际了。排序是一个 O(n log(n)) 的算法。它可以被腭化，但它仍然需要 O(n) 的内存量。

我正在寻找一种可以更好地进行此计数的算法:使用以下假设:日志消息的类型数量远小于日志文件(数千)。我对前 50 条重复出现的消息感兴趣。

Answer 1

您可以使用 awk 实现一种简单类型的桶排序:

awk 'a[$0]++; END {for (line in a) { print a[line], line; }}' |  sort -k1,1nr | head -50

awk 命令计算每个唯一行的出现次数，并在 O(n) 时间内输出每行及其计数。 sort 然后简单地按倒数顺序按计数对输出进行排序，head 输出最大的 50 个。