Bash计算小于N的3或5的倍数之和超时问题求助

问题描述 #

计算小于N的所有3或5的倍数之和，输入格式为：

第一行是测试用例数T，随后T行每行是一个N值。

示例输入：

2
10
100

预期输出：

23
2318

用户的两种尝试均因速度未通过基准测试：

1. 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

2. 纯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. 减少IO操作开销 #

原纯Bash实现每次循环都调用echo输出结果，多次IO操作会拖慢速度。可以先将所有计算结果存入数组，最后一次性批量输出：

#!/bin/bash
read -r t
results=()
while (( t-- )); do
    read -r n
    (( n--, x=n/3, y=n/5, z=n/15, sum=(1+x)*x/2*3 + (1+y)*y/2*5 - (1+z)*z/2*15 ))
    results+=("$sum")
done
printf '%s\n' "${results[@]}"

2. 简化数学公式，减少计算步骤 #

原公式可以合并为单次除法操作，减少算术运算次数：
原公式：3*(x*(x+1)/2) +5*(y*(y+1)/2) -15*(z*(z+1)/2)
简化后：(3*x*(x+1) +5*y*(y+1) -15*z*(z+1)) / 2
对应实现：

#!/bin/bash
read -r t
results=()
while (( t-- )); do
    read -r n
    (( n--, x=n/3, y=n/5, z=n/15, sum=(3*x*(x+1) +5*y*(y+1) -15*z*(z+1))/2 ))
    results+=("$sum")
done
printf '%s\n' "${results[@]}"

3. 批量读取输入，避免循环read #

当测试用例数量极大时，循环read的开销明显。改用readarray一次性读取所有输入，再批量处理：

#!/bin/bash
readarray -t inputs
t=${inputs[0]}
results=()
for ((i=1; i<=t; i++)); do
    n=${inputs[i]}
    (( n--, x=n/3, y=n/5, z=n/15, sum=(3*x*(x+1) +5*y*(y+1) -15*z*(z+1))/2 ))
    results+=("$sum")
done
printf '%s\n' "${results[@]}"

4. 省略中间变量，直接内联计算 #

极端场景下，可以去掉中间变量x/y/z，直接在算术表达式中计算，减少变量赋值开销：

#!/bin/bash
readarray -t inputs
t=${inputs[0]}
results=()
for ((i=1; i<=t; i++)); do
    (( n=inputs[i]-1, sum=(3*(n/3)*((n/3)+1) +5*(n/5)*((n/5)+1) -15*(n/15)*((n/15)+1))/2 ))
    results+=("$sum")
done
printf '%s\n' "${results[@]}"

内容的提问来源于stack exchange，提问作者Fravadona