3

私は現在、Project Euler の質問を Python で処理しようとしています (今日取り上げたものです)。私が取り組んでいる質問は、質問 5 です。

2520 は、1 から 10 までの各数値で割り切れる最小の数値です。

1 から 20 までのすべての数で割り切れる最小の正の数は?

以前にJavaを使用して問題を解決したことがあるので、以前と同じ方法を使用して、反復するループを作成しましたが、コードが終了しないようです。

パイソン:

i = 1
while 1:
    if i%2 == 0 and i%3==0 and i%4==0 and i%5==0 and i%6==0 and i%7==0 and i%8==0 and i%9==0 and i%10==0 and i%11==0 and i%12==0 and i%13==0 and i%14==0 and i%15==0 and i%16==0 and i%17==0 and i%18==0 and i%19==0:
        print i
        break
    i+=1

ジャワ:

public class p5
{
    public static void main(String[] args)
    {
        for (int i=1;;i++)
        {
            if (i%1==0&&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&&i%18==0&&i%19==0&&i%20==0)
            {
                System.out.println(i);
                break;
            }
        }
    }
}

Java は私のコンピューターで 3 秒以内にそれを実行しましたが、Python コードは決して終了していないように見えました。任意のヒント？

編集：

どうやら私は何か間違って入力したようで、それが原因で終了しませんでした。ただし、全体が正しく記述されていても (私の Java と同じ出力で)、それでも1 分 20 秒かかりましたが、Java の場合は約 1 ～ 2 秒かかりました。私は何か間違ったことをしていますか？それとも、Pythonのパフォーマンスはそれほど悪いのですか（これはよくあることではありません）

4

2 に答える 2

4

プリミティブints を使用した演算は、CPython の完全な整数オブジェクトを使用した場合よりも Java の方がはるかに高速です。つまり、30 倍のパフォーマンスの差は、コードにとって驚くべきことではありません。

アルゴリズムは非常に非効率的であり、1 から 50 までの数値など、わずかに大きな入力に対しては機能しないことに注意してください (時間がかかりすぎて、正しい結果は Java の max int/long よりも大きくなります)。

より効率的なアルゴリズムを使用して、私のマシンで 1 から 100 までのすべての数値の結果を計算するには ~100 マイクロ秒かかります。

#!/usr/bin/env python
from functools import reduce

def gcd(a, b):
    """Greatest common divisor (factor)."""
    while b: # Euclid's algorithm
        a, b = b, a % b
    return a

def lcm(*args):
    """Least common multiple."""
    # lcm(a, b, c) == lcm(lcm(a, b), c)
    return reduce(lambda a, b: a * b // gcd(a, b), args)

def f(n):
    """Smallest positive number evenly divisible by all numbers from 1
       to n including.
    """
    return lcm(*range(1, n + 1))

print(f(10)) # -> 2520
print(f(50)) # -> 3099044504245996706400

パフォーマンスを見積もるには:

#!/usr/bin/env python
import timeit
from functools import partial

def measure():
    for n in [10, 50, 100]:
        print("%d: %5.2f microseconds" % (n, timeit.timeit(partial(f, n),
                                                           number=1000*1000)))
measure()
于 2012-10-24T19:09:14.950 に答える
2

私の純粋なブルートフォース ソリューションは、pypy を使用して ~250 ミリ秒かかります。

i = 20
while 1:
    if i%20 == 0 and i%19==0 and i%18==0 and i%17==0 and i%16==0 and i%15==0 and i%14==0 and i%13==0 and i%12==0 and i%11==0:
        print i
        break
    i+=20

よりエレガントには、最大公約数や最小公倍数などを使用する必要があります。

于 2012-10-24T15:17:50.917 に答える