使用并行来加速递归 shell max 函数？

2024-6-8 • tag-icon

我需要一个 max 函数，来查找数组（350 个 int 值）中的最高值，并且作为递归的朋友，我尝试了一种递归方法：

max () {
    len=$#
    a=$1
    b=$2
    case $len in
        0)
            echo NaN
            ;;
        1)
            echo $1
            ;;
        2)
            (( a > b )) && echo $a || echo $b
            ;;
        *)
            shift; shift
            max $(max $a $b) $(max $@)
            ;;
    esac
}

速度慢得令人震惊。 350 个值需要 2.6 秒。

是的，规范的unix方式是

time (echo ${yvals[@]} | tr " " "\n" | sort -n | tail -n 1 )

这需要 0,005 秒和一个 while 循环

max () {
    anz=$#
    max=$1
    while ((anz > 0))
    do
        b=$2
        (( b > max )) && max=$b
        shift
        anz=$#
    done
    echo $max
}

与 0,010 秒相差不远——嗯，速度慢了一倍，但对于如此低的值，误差范围可能会比测量值更高。我对最快的性能不太感兴趣，只要值计数不太高即可。然而，我很好奇，gnu-parallel 是否可以带来改进，并且很长一段时间以来，我一直在等待机会了解更多有关并行的知识，但我更喜欢通过现实世界的示例进行学习，并且很少有示例，这可能从并行化中受益。

所以我天真的方法是尝试递归版本

time parallel max ::: ${yvals[@]}

并添加了一些并行实验选项，例如 -j+0，这会产生 350 个值，每个值都不与其他值进行比较，因此本身就是最大值。 :)

除了查阅联机帮助页之外，我还观看了 Ole Tange 的 4 个 YT 视频中的 2 个，他是gnu 并行，找到一个与我的用例足够接近的示例，通过小的修改来采用它，但没有找到任何示例。

所以我有向SE询问的想法，但由于其他事情而分心，我扰乱了我的6 shell windows历史记录，所以我开始写我的问题，并想记录命令，我尝试过，但现在我写了：

time parallel -X max ::: ${yvals[@]} 
6933
1689
23676
31553

令人惊讶的是，它确实有效。是的，4 个核心，所以有 4 个结果，很容易找出哪个是最大的。我可以编写一个 max 函数，它取这些最大值中的最大值。

time max $(parallel -X max ::: ${yvals[@]}) 
31553

real    0m0,501s (Only a 5th of the time, used without parallel).

因此，对于在 shell 中进行交互工作来说，半秒是可以接受的范围，但是当然，这只是运气好，只有正确的记录数量才能实现这种体验。 shell 是否因递归性能不佳而闻名？这不是我的主要问题。

主要问题是，是否存在一种规范的并行方式，可以对结果再次执行该函数，这是函数式编程中解决问题的典型方式，称为折叠。我猜map/reduce 原则上是一样的。

由于大多数时候，我处理的数据很小，我缺乏机会和痛苦来学习并行进出。

答案1

max对于 Bash 中的前 500 个值，您的函数运行时间为 O(n^2)。这很可能是由于您max使用剩余值进行调用所致。因此必须复制这些值。

mmax() {
    max $(seq $1)
}

seq 10000 | env_parallel --joblog bash.log mmax
(echo '#Bash';echo '#JobRuntime in seconds';field 10,4 < bash.log |sort -n) |
  head -n 1000 | plotpipe