awk:从列中找到最小的10个值

Question

我有一个像这样排列的文件:

a  123
b 45
c -23
d 166

我是awk的新手,我想找到第2列中的十(或x)个最低数字,并在新文件中打印这些行.

目前我们使用以下代码并观察结果,看看我们是否大约有十个.如果没有,我们将-5.0更改为其他内容,依此类推:

cat input.txt | awk '{if($2 < -5.0) {print $1" "$2}}' >> output.txt

Answer 1

没有AWK,您可以轻松完成此操作:

$ sort -nk 2 input.txt | head -10 > output.txt

它对输入文件进行排序并打印前10行(第2列中的值最低).如果您的输入文件特别大,这可能不合适.这sort可能使用O(N log N)排序算法(对于N行输入).

如果您只想要最小值,那么AWK中的解决方案就是单线程.在这种情况下,它有点棘手,因为您必须保持多个最低值.尝试这样的事情:

lowest.awk

#!/usr/bin/awk -f
BEGIN{if (X=="") X=10; s=0}
{ # insert new value in order
    for (i=0; i<s && $2>a[i]; ++i);
    if (s==X && i==s) next
    for (j=s; j>i; --j) {
        a[j] = a[j-1]
        b[j] = b[j-1]
    }
    a[i] = $2
    b[i] = $0
    if (s<X) s++
}
END{ # print stored lines
    for (i=0; i<s; ++i)
        print b[i]
}

要在命令行上运行它:

$ awk -f lowest.awk infile.txt > outfile.txt

您可以从命令行指定要打印的最低值的数字X-v X=10:

$ awk -v X=10 -f lowest.awk infile.txt > outfile.txt

但是10是默认值.

这会将每个值(在第2列中)与数组的每个元素进行比较a,并在需要时插入新值.该数组b存储最后$0要打印的整行().的(使用)尺寸a和b是s.

通常,您应该使用类似的东西遍历数组中的条目for (i in a),但在这种情况下,a[s]在打印结果时必须忽略一个额外的条目,因此块中的for (i=0; i<s; ++i)格式END.

在最坏的情况下,将N个值中的每一个与X值进行比较a.所以这是O(XN),这是对O(N log N)sort版本的改进.此外,它需要更少的内存,因为您只存储O(X)值而不是内存中的所有N行.

请注意,这会通过插入来维护顺序.在X = N的情况下,您保留所有值并按顺序列出它们 - 换句话说,排序.当X接近N时,O(XN)公式接近O(N ²),这是插入排序算法的复杂性.因此,这AWK版本只比一个O更有效(ñ日志ñ)基于排序的方法,其中X是远远小于ñ.