bash 脚本的计算时间扩展得非常可怕

Question

我有以下代码可以解决下面的 Project Euler 问题：

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

我的脚本工作正常，生成 2520，因为它应该为 1-10 生成，我也有 1-17 的答案，共 12252240，看起来是这样的：

#!/bin/bash

for ((i=1; i<10000000000; i++))
 do
if (( i%2 == 0 )) && (( i%3 == 0 )) && (( i%4 == 0 )) && (( i%5 == 0 )) &&
   (( i%6 == 0 )) && (( i%7 == 0 )) && (( i%8 == 0 )) && (( i%9 == 0 )) && 
   (( i%10 == 0 )) && (( i%11 == 0 )) && (( i%12 == 0 )) && (( i%13 == 0 )) &&
   (( i%14 == 0 )) && (( i%15 == 0 )) && (( i%16 == 0 )) && (( i%17 == 0 )); then 
    # remaning terms to factor && (( i%18 == 0 )) && (( i%19 == 0 )) && (( i%20 == 0 )); then 
    int=$i
fi

if [[ $int ]]; then
 echo "Lowest integer = '$int'"
 break
 else
     continue
fi


done

然而，从分解约 12 项（实时大约 3/4 秒）到分解 17（实时 6 分钟），在计算时间上的跳跃是巨大的。

我还没有给出完整的 20 个因素运行，但所有欧拉计划问题都应该可以在中等功率的家用计算机上在几分钟内解决。

所以我的问题有 2 个：1) 就我如何对此进行编程而言，我是否走在正确的轨道上，以及 2) could/should 我如何做到尽可能高效？

Answer 1

So my question is 2 fold:

1) Am I on the right track in terms of how I approached programming this, and

恐怕你不是。您使用了错误的工具，即 shell 脚本语言来解决数学问题，并且想知道为什么它不能很好地执行。 "being solvable in a couple of minutes on a home computer" 并不意味着它应该是那样的，无论您选择的工具多么不同寻常。

2) how else could/should I have done it to make it as efficient as possible?

不要使用bash的算法。 Bash 是一个 shell，这意味着它的核心是解释器。这意味着它会花费很少的时间来计算，而会花很多时间来理解它应该做什么。举例说明：您的复杂公式首先必须解析成一棵树，告诉 bash 以何种顺序执行事物，然后必须识别这些事物，然后 bash 需要遍历该树并保存树的下一级的所有结果。它所花费的几条算术指令几乎不需要计算时间。

看看 numpy，这是一个 python 数学模块；它做事更快。如果您不害怕编译您的东西，请查看 C++ 或 C，它们都存在非常非常快的数学库。

Answer 2

算术条件支持逻辑运算符。速度增益并不大，但有一些：

if (( i % 2 == 0 && i % 3 == 0 && ... ))

另请注意，当您已经知道 i % 2 == 0 和 i % 5 == 0 时不需要测试 i % 10 == 0。

有一种无需遍历所有数字即可更快地获取数字的方法。

Answer 3

在不放弃蛮力方法的情况下，运行以相反顺序进行的内循环大致将运行时间减半。

for ((i=1; i<100000000; ++i)); do
  for ((j=17; j>1; --j)); do
    (( i%j != 0 )) && break
  done
  ((j==1)) && echo "$i" && break
done

通俗地说，几乎没有数字可以被 17 整除，而在这些数字中，几乎没有数字可以被 16 整除。因此，运行反向顺序的内循环删除了内循环的 16 次迭代 for大多数数字，其余大部分为 15。

其他优化很明显；例如，内部循环可以在 4 处结束，因为 2、3 和 4 已经被它们各自的正方形覆盖（所有能被 9 整除的数字也能被 3 整除，等等）。然而，与主要优化相比，这只是小菜一碟。

（您没有明确的内部循环，事实上，像您那样展开循环可能会获得很小的性能提升。我主要出于懒惰以及出于审美原因将其滚动到明确的循环中。 )

Answer 4

答案不是更快的编程语言。答案是更聪明的算法。

你知道你的最终答案必须能被所有数字整除，所以从你最大的数字开始，只检查它的倍数。找出是两个最大数字的倍数的最小数字，然后只检查下一个数字的倍数。

让我们看看这对 1 到 10 是如何工作的：

10  // not divisible by 9, keep adding 10's until divisible by 9
20  
30  
40  
50  
60
70
80
90  // divisible by 9, move on to 8, not divisible by 8, keep adding 90's
180
270
360 // divisible by 8, not divisible by 7, keep adding 360's
720
1080
1440
1800
2160
2520  // divisible by 7, 6, 5, 4, 3, 2, 1 so you're done!

所以只需 17 个步骤，您就有了答案。

此算法在 Ruby 中实现（以其速度着称）在速度适中的笔记本电脑上在 4.5 秒内找到了 1-5000 的答案。

bash 脚本的计算时间扩展得非常可怕

Computation time of a bash script scales horribly

math

bash