3

关于整数加单行，存在几种建议的 shell 脚本解决方案；
然而，仔细研究选择的每个解决方案，都存在固有的局限性：

  • awk那些会以任意精度和整数大小窒息（毕竟它的行为类似于 C）
  • bc一些人宁愿对任意长的输入不满意：(sed 's/$/+\\/g';echo 0)|bc

了解可能存在跨平台的可移植性问题（请参阅 [1] [2]），这是不希望的，是否有一个通用的解决方案，它在实用性和简洁性方面都是赢家？

提示：SunOS 和 MacOSX 是可移植性问题的示例。
菲。命令是否dc允许处理任意大的 2^n、整数或其他输入？

[1] awk: https://stackoverflow.com/a/450821/1574494或https://stackoverflow.com/a/25245025/1574494或在 awk 中打印长整数

[2] bc: Bash 命令对一列数字求和

4

5 回答 5

6

dc(1)在读取输入时求和的最佳解决方案：

$ jot 1000000 | sed '2,$s/$/+/;$s/$/p/' | dc
500000500000
于 2017-09-16T00:27:43.840 回答
3

我通常使用的是paste -sd+|bc：

$ time seq 1 20000000 | paste -sd+|bc
200000010000000

real    0m10.092s
user    0m10.854s
sys     0m0.481s

（对于严格的Posix 合规性，paste需要提供一个明确的参数：paste -sd+ -|bcpaste

但是，对于较大的输入，这将失败，因为bc在评估之前将整个表达式缓冲在内存中。在我的系统上，bc尝试添加 1 亿个数字时内存不足，尽管它能够完成 7000 万个。但其他系统可能具有较小的容量。

由于bc有变量，您可以通过重复添加到变量而不是构造单个长表达式来避免长行。这是（据我所知）100% Posix 兼容，但有 3 倍的时间损失：

$ time seq 1 20000000|sed -e's/^/s+=/;$a\' -es|bc
200000010000000

real    0m29.224s
user    0m44.119s
sys     0m0.820s

处理输入大小超过bc的缓冲容量的另一种方法是使用标准xargs工具将数字添加到组中：

$ time seq 1 100000000 |
> IFS=+ xargs sh -c 'echo "$*"' _ | bc | paste -sd+ | bc
5000000050000000

real    1m0.289s
user    1m31.297s
sys     0m19.233s

每个xargs评估使用的输入行数会因系统而异，但通常会有数百个，并且可能更多。显然，xargs | bc可以任意链接调用以增加容量。

在超出命令容量的系统上，可能需要使用开关限制xargs扩展的大小。除了进行实验来确定缓冲区限制之外，没有可移植的方法来确定该限制可能是多少，但它肯定不低于保证至少为 2048 的限制。即使有 100 位加数，这也将允许减少了 20 倍，因此假设您准备等待几个月才能完成，那么 10 个管道链将处理超过 10 13 个加数。-sARG_MAXbcbcLINE_MAXxargs|bc

作为构建大型固定长度管道的替代方法，您可以使用函数递归地管道输出，xargs|bc直到只产生一个值：

radd () { 
    if read a && read b; then
        { printf '%s\n%s\n' "$a" "$b"; cat; } |
          IFS=+ xargs -s $MAXLINE sh -c 'echo "$*"' _ |
          bc | radd
    else
        echo "$a"
    fi
}

如果你对 使用一个非常保守的值MAXLINE，上面的速度会很慢，但如果值更大，它不会比简单的paste|bc解决方案慢很多：

$ time seq 1 20000000 | MAXLINE=2048 radd
200000010000000

real    1m38.850s
user    0m46.465s
sys     1m34.503s

$ time seq 1 20000000 | MAXLINE=60000 radd 
200000010000000

real    0m12.097s
user    0m17.452s
sys     0m5.090s

$ time seq 1 100000000 | MAXLINE=60000 radd 
5000000050000000

real    1m3.972s
user    1m31.394s
sys     0m27.946s

除了bc解决方案之外，我还计算了其他一些可能性。如上图，输入 2000 万个数字，paste|bc耗时 10 秒。这几乎与将 2000 万个数字相加所用的时间相同

gawk -M '{s+=$0} END{print s}'

诸如python并被perl证明更快的编程语言：

# 9.2 seconds to sum 20,000,000 integers
python -c $'import sys\nprint(sum(int(x) for x in sys.stdin))'
# 5.1 seconds
perl -Mbignum -lne '$s+=$_; END{print $s}'

我无法dc -f - -e '[+z1<r]srz1<rp'在大输入上进行测试，因为它的性能似乎是二次的（或更差）；它在 3 秒内将 25000 个数字相加，但将 500000 和 1900000 用了 19 秒，而将 1000000000000000000000000000000000000000000000000000000000000000000000 加了 90 秒。

虽然bc不是最快的并且内存限制需要笨拙的解决方法，但它的优点是可以在符合 Posix 的系统上开箱即用，而无需安装任何标准实用程序 ( awk) 的增强版本或 Posix 不需要的编程语言 (perl和python) .

于 2017-06-27T01:38:45.880 回答
1

您可以使用gawk-M标志：

$ seq 1 20000000 | gawk -M '{s+=$0} END{print s}'
200000010000000

或者启用Perlbignum ：

$ seq 1 20000000 | perl -Mbignum -lne '$s+=$_; END{print $s}'
200000010000000
于 2017-06-27T03:15:45.267 回答
1

$ seq 1000|(sum=0;while read num; do sum=`echo $sum+$num|bc -l`;done;echo $sum) 500500

此外，这个不会赢得最高速度奖，但它是：

  • oneliner，是的。
  • 便携的
  • 添加任意长度的列表
  • 添加任意精度的数字（每个数字的长度仅受 MAXLINE 限制）
  • 不依赖外部工具，如 python/perl/awk/R 等

稍加伸展，您也可以称其为优雅；-) 来吧，伙计们，展示更好的方法！

于 2017-07-12T16:58:46.940 回答
0

似乎以下方法可以解决问题：

$ seq 1000|dc -f - -e '[+z1<r]srz1<rp'
500500

但是，这是最佳解决方案吗？

于 2017-06-27T01:30:54.677 回答