☰

我可以做 [ $(($1 % $check)) -ne 0 ];表现更好而不被杀死？

tag-icon • tag-icon shell-script scripting performance
我可以做 [ $(($1 % $check)) -ne 0 ];表现更好而不被杀死？

如果有以下代码，它在几秒钟内最多可以运行 13（第 2 行），但是当我尝试执行上十几和 20 时，它会在几分钟后被杀死。

divisible_by () {
  for ((check=2; check<13; check++)) {
    if [ $(($1 % $check)) -ne 0 ]; then
      return
    fi  
  }
  echo "$1 is divisible by all the numbers"
  exit 0
}
d=0
while true; do
  d=$((d+1))
  divisible_by $d
done

我尝试使用

if $(($1 % $check)) -ne 0; then

但我得到1: command not found

我试过

if $(($1 % $check)) -ne 0; then

但我得到了1:command not found并且-ne command not found

我试过

 if [ $($1 % $check) -ne 0 ]; then

但我得到了1:command not found并且-ne: unary operator expected

我试过

 if [ $1 % $check -ne 0 ]; then

但我得到了[: too many arguments

答案1

假设这里的目标是找到可被整数 2 到 n 整除的最小数，尝试检查每个整数的效率非常低。我能想到的最简单的算法是使用一系列因素，这些因素最终会相乘得到答案。它开始是空的。然后，按顺序取出每个数字，并除掉我们的独特因子集中已有的因子。剩下的都将添加到唯一因子集中，并且我们知道该集合将可以被当前数字整除。由于该集合的乘积包含满足所有必要除法的最小质因数集合，因此保证它是可被 2 到 n 的所有数字整除的最小数字。

upto=20
uniqueFactors=()
for ((i=2; i <= upto; i++)) 
do
  newFactors=$i
  for factor in "${uniqueFactors[@]}" #loop over array of factors
  do
    if [ $(($newFactors%$factor)) -eq 0 ]; then
      newFactors=$(($newFactors/$factor));
    fi;
  done
  uniqueFactors+=($newFactors);
done

product=1
for factor in "${uniqueFactors[@]}"
do
  product=$(bc <<< "$product*$factor") #use bc for numbers outside integer range
done

echo $product

在我的机器上，这会在 4 毫秒内计算出第一个能被 2-20 整除的数字 (232792560)。它在 0.425 秒内计算出 100 (69720375229712477164533808935312303556800)，并在 4.813 秒内计算出 1000（具有几百位小数的数字）。如果你要尝试迭代那么多数字，你就必须担心你的过程会被宇宙的热寂杀死。优化单条生产线可为您带来百分比或数量级的改进。改变你的算法可以给你带来对数级的改进。

答案2

((您可以利用当结果非零时返回零的事实：

if (( $1 % check )); then
  ...
fi

答案3

我会按降序迭代。循环可以更快终止。

for ((check=12; check>1; --check)) {

代替

for ((check=2; check<13; check++)) {

考虑一下。如果这个数不能被 12 整除，它也不能被 4、3 和 2 整除。反之则不然。

相关内容