logo标签列表

Bash - 求N以下3或5的倍数之和 - 超时

bash
5

我正在尝试在Bash中计算所有小于N的3或5的倍数之和，但我的尝试在速度基准测试中失败了。

输入格式描述如下：

The first line is T, which denotes the number of test cases, followed by T lines, each containing a value of N.
Sample input:

2
10
100

Expected output:

23
2318

这是我的尝试：

  • 使用 bc：
#!/bin/bash

readarray input

printf 'n=%d-1; x=n/3; y=n/5; z=n/15; (1+x)*x/2*3 + (1+y)*y/2*5 - (1+z)*z/2*15\n' "${input[@]:1}" |
bc
  • 使用纯粹的 bash：
#!/bin/bash

read t
while (( t-- ))
do
    read n
    echo "$(( --n, x=n/3, y=n/5, z=n/15, (1+x)*x/2*3 + (1+y)*y/2*5 - (1+z)*z/2*15 ))"
done

备注：我使用t，因为输入不以换行符结尾...

这两个解决方案都被评为“太慢”，但我真的不知道还有什么可以进一步改进的。你有什么想法吗？

1
这可能很有用：A126592 - 小于或等于n的3或5的倍数之和 在 整数序列在线百科全书（OEIS） 上。 - pjh
@pjh 谢谢您，这个公式似乎和问题中的一样。我在考虑接受 @oguzismail 的答案，因为它展示了一个经过优化的版本。遗憾的是，awk 没有足够的整数精度，所以我不能直接使用它；我可以做的最好的事情就是用 awk 预处理输入并将其管道传输到 bc；然而，这也被认为是“太慢”了。我即将得出结论，使用 bash + 标准工具无法满足约束条件。 - Fravadona
6个回答
3

使用 awk：

BEGIN {
  split("0 0 3 3 8 14 14 14 23 33 33 45 45 45", sums)
  split("0 0 1 1 2 3 3 3 4 5 5 6 6 6", ns)
}
NR > 1 {
  print fizzbuzz_sum($0 - 1)
}
function fizzbuzz_sum(x, q, r) {
  q = int(x / 15)
  r = x % 15
  return q*60 + q*(q-1)/2*105 + sums[r] + (x-r)*ns[r]
}

在我的旧笔记本电脑上，它非常快，该笔记本配备了AMD A9-9410处理器

$ printf '%s\n' 2 10 100 | awk -f fbsum.awk
23
2318
$
$ time seq 0 1000000 | awk -f fbsum.awk >/dev/null

real    0m1.532s
user    0m1.542s
sys     0m0.010s
$

而且使用 bc，以防您需要它能够处理大数字：

{
  cat <<EOF
s[1] = 0; s[2] = 0; s[3] = 3; s[4] = 3; s[5] = 8
s[6] = 14; s[7] = 14; s[8] = 14; s[9] = 23; s[10] = 33
s[11] = 33; s[12] = 45; s[13] = 45; s[14] = 45

n[1] = 0; n[2] = 0; n[3] = 1; n[4] = 1; n[5] = 2
n[6] = 3; n[7] = 3; n[8] = 3; n[9] = 4; n[10] = 5
n[11] = 5; n[12] = 6; n[13] = 6; n[14] = 6

define f(x) {
  auto q, r
  q = x / 15
  r = x % 15
  return q*60 + q*(q-1)/2*105 + s[r] + (x-r)*n[r]
}

EOF
  awk 'NR > 1 { printf "f(%s - 1)\n", $0 }'
} | bc

虽然速度慢了很多。

$ printf '%s\n' 2 10 100 | sh ./fbsum.sh
23
2318
$ 
$ time seq 0 1000000 | sh ./fbsum.sh >/dev/null

real    0m4.980s
user    0m5.224s
sys     0m0.358s
$
感谢@oguzismail。使用awk我得到了一个“错误答案”。看起来计算需要GNU的--bignum选项，但显然在VM上不可用：awk: unrecognized option: bignum BusyBox v1.30.1 (2019-06-12 17:51:55 UTC) multi-call binary. - Fravadona
@Fravadona 因为那样更好。请查看我的编辑。 - oguz ismail
没错，它要慢得多，而且不能通过限制...但我得出结论，他们的要求是不可能用bash和标准工具来满足的。 - Fravadona
使用bash解决方案和1000000 seq 1 1000000，你可以去睡觉，第二天早上起来它仍然会在单个核心上以100%的速度运行... - David C. Rankin
@DavidC.Rankin，你对纯Bash解决方案的期望有点悲观。我已经发布了Bash代码，可以在40秒内处理一百万个输入。与awk或其他替代方案相比，这很差，但并不是无法忍受的糟糕。 - pjh
3

让我们从基础开始，并尽可能优化：

#!/usr/bin/env bash
read N
sum=0
for ((i=1;i<N;++i)); do
  if ((i%3 == 0 )) || (( i%5 == 0 )); then
      (( sum += i ))
  fi
done
echo $sum

在上面的代码中，我们运行循环N次，最少进行N次比较和最多2N次求和（i和sum）。我们可以通过使用步长为3和5的多个循环来加快速度，但是我们必须注意避免重复计数：
#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3;i>=3;i-=3)); do (( sum+=i )); done
for ((i=N-N%5;i>=5;i-=5)); do (( i%3 == 0 )) && continue; ((sum+=i)); done
echo $sum

我们现在最多有2N/3 + 2N/5 = 16N/15个求和和N/5个比较。这已经快得多了。我们可以通过添加一个额外的循环，步长为3*5，来减去重复计数，进一步优化它。

#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3 ; i>=3 ; i-=3 )); do ((sum+=i)); done
for ((i=N-N%5 ; i>=5 ; i-=5 )); do ((sum+=i)); done
for ((i=N-N%15; i>=15; i-=15)); do ((sum-=i)); done
echo $sum

这将使我们最大限度地使用2(N/3 + N/5 + N/15) = 17N/15 的加法和零次比较。虽然这是最优的，但我们仍然每个循环周期调用一个算术表达式。我们可以将其吸收到for循环中：
#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3 ; i>=3 ; sum+=i, i-=3 )); do :; done
for ((i=N-N%5 ; i>=5 ; sum+=i, i-=5 )); do :; done
for ((i=N-N%15; i>=15; sum-=i, i-=15)); do :; done
echo $sum

最后，最简单的方法是使用算术级数公式，消除所有循环。请记住，bash使用整数算术（即m = p*(m/p) + m%p），可以这样写：

#!/usr/bin/env bash
read N
(( sum = ( (3 + N-N%3) * (N/3) + (5 + N-N%5) * (N/5) - (15 + N-N%15) * (N/15) ) / 2 ))
echo $sum

后者是最快的方式（除了数字小于15），因为它不调用任何外部二进制文件，如bc或awk，并且可以在没有任何循环的情况下执行任务。

1
你忘了 N-- : 在下面 N 的位置 !!: echo $(( N--, ( (3 + N-N%3) * (N/3) + (5 + N-N%5) * (N/5) - (15 + N-N%15) * (N/15) ) / 2 )) - F. Hauri - Give Up GitHub
1
在第 for ((i=N-N%5;i>=5;i-=5)); do (( i%3 == 0 )) && continue; ((sum+=i)); 行中添加了 ((...))。 - Wiimm
2

像这样的东西怎么样？

#! /bin/bash

s35() {
    m=$(($1-1)); echo $(seq -s+ 3 3 $m) $(seq -s+ 5 5 $m) 0 | bc   
}

read t
while read n
do
    s35 $n
done

或者

s35() {
    m=$(($1-1)); 
    { sort -nu <(seq 3 3 $m) <(seq 5 5 $m) | tr '\n' +; echo 0; } | bc   
}

去重。

2

这个经过Shellcheck清理的纯Bash代码可以在非常普通的Linux虚拟机上，仅用40秒就能处理从echo 1000000; seq 1000000（一百万个输入）输入的数据。

#! /bin/bash -p

a=( -15  1 -13 -27 -11 -25 -9  7 -7 -21 -5 11 -3 13 -1 )
b=(   0 -8  -2  18  22  40 42 28 28  42 40 22 18 -2 -8 )

read -r t
while (( t-- )); do
    read -r n
    echo "$(( m=n%15, ((7*n+a[m])*n+b[m])/30 ))"
done

该代码依赖于以下事实：每个值n的总和可以用形如(7*n**2+A*n+B)/30的二次函数计算。A和B的值取决于n模15的值。代码中的数组a和b包含了每个可能模数值（{0..14}）的A和B的值。（为避免进行代数运算，我编写了一个小型Bash程序来生成a和b数组。）
该代码可以轻松地转换成其他编程语言，并且在许多编程语言中运行速度会更快。
1

对于纯Bash方法，

#!/bin/bash

DBG=1

echo -e "This will generate the series sum for multiples of each of 3 and 5 ..."
echo -e "\nEnter the number of summation sets to be generated => \c"
read sets

for (( k=1 ; k<=${sets} ; k++))
do
    echo -e "\n============================================================"
    echo -e "Enter the maximum value of a multiple => \c"
    read max
    echo ""

    for multiplier in 3 5
    do
        sum=0
        iter=$((max/${multiplier}))
        for (( i=1 ; i<=${iter} ; i++ ))
        do
            next=$((${i}*${multiplier}))
            sum=$((sum+=${next}))
            test ${DBG} -eq 1 && echo -e "\t ${next}   ${sum}"
        done
        echo -e "TOTAL:  ${sum}  for ${iter} multiples of ${multiplier} <= ${max}\n"
    done
done

当 DBG=1 时的会话日志：

This will generate the series sum for multiples of each of 3 and 5 ...

Enter the number of summation sets to be generated => 2

============================================================
Enter the maximum value of a multiple => 15

     3   3
     6   9
     9   18
     12   30
     15   45
TOTAL:  45  for 5 multiples of 3 <= 15

     5   5
     10   15
     15   30
TOTAL:  30  for 3 multiples of 5 <= 15


============================================================
Enter the maximum value of a multiple => 12

     3   3
     6   9
     9   18
     12   30
TOTAL:  30  for 4 multiples of 3 <= 12

     5   5
     10   15
TOTAL:  15  for 2 multiples of 5 <= 12
1

虽然 awk 比 shell 更快，但在 bash 中，你可以使用 ((m % 3 == 0)) || ((m % 5 == 0)) 来识别小于 n 的 3 和 5 的倍数。你需要检查它是否符合时间限制，但它应该相对快速。

#!/bin/bash

declare -i t n sum        ## handle t, n and sum as integer values

read t || exit 1          ## read t or handle error

while ((t--)); do         ## loop t times
  sum=0                   ## initialize sum zero
  read n || exit 1        ## read n or handle error
  ## loop from 3 to < n
  for ((m = 3; m < n; m++)); do
    ## m is multiple of 3 or multiple of 5
    ((m % 3 == 0)) || ((m % 5 == 0)) && {
      sum=$((sum + m))    ## add m to sum
    }
  done
  echo $sum               ## output sum
done

示例用法/输出

使用脚本 mod35sum.sh 并将数据存储在 dat/mod35sum.txt 中，你将得到：

$ bash sum35mod.sh < dat/sum35mod.txt
23
2318
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接