0

の解決策を見つけたいSpoiler alert Euler #41 problem。私が尋ねた質問は、それのサブ問題です。質問に対する解決策はありますが、問題は解決策にあります。これが私がチェックしている実際のものです： -

large = 0
x = ''

for i in range(1,10):
x += '%d' %i
for perm in permutations(x):
    if(isPrime(int(perm))):
        large = perm

print large

ここに順列関数があります:-

def permutations(val):
    res = []
    if len(val) == 1:
        res = [val]
    else:
        for i, c in enumerate(val):
            for perm in permutations(val[:i]+val[i+1:]):
                res += [c+perm]

return res

上記のプログラムは、1 から 987654321 までの順列で、すべての素数の順列を見つけます。

しかし問題は大=7652413以降で、大ではそれ以上の伸びはありません。プログラムは約 3 秒でこの値に到達しますが、プログラムは約 4 分で完了します。そこで、この時間を短縮する方法はないかと考えていました。

この質問は、関数が目的の結果を得るのに時間がかかりすぎているかどうかを示す関数を見つける方法として一般化することもできます。

4

2 に答える 2

2

目前の直接的な質問にのみ答えると、 を使用してコードを大幅に高速化できますitertools.permutations。

しかし、数学的には、必要な素数が最大 7 桁までであることを認識することで、問題を減らすことができます。8 の場合、1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36は 3 で割り切れるため、素数にはなりません。9 を足すと 45 になり、これも 3 で割り切れます。

于 2013-07-09T21:53:57.833 に答える
1

ヒューリスティックとしてタイムアウトを適用して、「おそらく完了」したことを伝え、作業を停止する方法を探しているようです。

これを行う簡単な方法は、開始時またはインクリメントするたびに現在の時刻を取得しlarge(関連すると思われる時刻に応じて)、それ以降の時刻を頻繁に確認し、それを過ぎた場合はキャンセルすることです。

コードを手動で「頻繁にチェックする」ことが合理的でない場合は、バックグラウンド スレッドを使用してそれを行うことができますが、ここではその必要がないように思われるため、単純にしておきましょう。

そう：

class Timeout(object):
    def __init__(self, timeout_seconds):
        self.timeout = datetime.timedelta(0, timeout_seconds)
        self.reset()
    def reset(self):
        self.start = datetime.datetime.now()
        self.stop = self.start + self.timeout
    def check(self):
        if datetime.datetime.now() > self.stop:
            raise Exception('Timeout!')

これで、次のことができます。

t = Timeout(30)
for perm in permutations(x):
    if isPrime(int(perm)):
        large = perm
        t.reset()
    t.check()

秒数の代わりに更新以降のループ回数を使用したい場合、またはより洗練されたヒューリスティックを使用したい場合は、これ以上複雑ではありません。ヒューリスティックを記述してコードに変換するだけです。

于 2013-07-09T21:52:58.347 に答える