python - Python で力ずくで Euler #14 を解く

Question

オイラー問題 14を python でブルートフォースしようとしましたが、あまり成功しませんでした。

itertools モジュールを使用しましたが、遅すぎました。そして、その問題を解く公式を見つけました。

ブルートフォースを使用して問題を解決する方法はありますか?

Answer 1

中間値を辞書に格納して、一種の動的計画法を実行できます。

numbers = {1:0}
max = -1
startMax = -1
for i in range(2, 1000 000):
    n = i
    steps = 0
    while n>=i:
        if n&2 == 0:
            n = n/2
        else:
            n = 3*n + 1
        steps = steps + 1
    # n < i, hence it must already be stored in the dictionary
    steps = steps + numbers[n]
    if steps > max:
        max = steps
        startMax = i
    numbers[i] = steps
    return startMax

もう 1 つの方法は、遭遇したすべての番号を保存し、現在使用している番号がマップにあるかどうかを常に確認することです。しかし、非常に多くの辞書検索があるため、これには少し時間がかかると思います。

numbers = {1:0}
max = -1
for i in range(2, 1000 000):
    if i in numbers:
        steps = numbers[i]
    else:
        n = i
        steps = 0
        found = False

        while not found:
            if n&2 == 0:
                n = n/2
            else:
                n = 3*n + 1
            if n in numbers:
                steps = numbers[n]
                found = True
            else:
                newNumbers.append(n)
        # Store all the new numbers into the dictionary
        for num in newNumbers:
            steps = steps + 1
            numbers[num] = steps
    if steps>max:
        max = steps
        startMax = i
return startMax

どちらが優れているかを調べるためにいくつかのテストを行いたいと思うかもしれませんが、私の賭けは最初のものになります.

Answer 2

pypyは「最適化がオンになっている python」です。

ここから入手してください: http://pypy.org/download.html#default-with-a-jit-compiler

それを使用するには、pypy通常書く場所に書くだけですpython。かなり互換性があります。主な違いは、python 用に書かれた C ベースの拡張機能は pypy では動作しないことですが、多くの人がこれを修正するために懸命に取り組んでいます。

---

私は自分の答えを擁護せざるを得ないと感じています。この非常に単純なブルート フォース ソリューションを考えると、次のようになります。

"Solve Project-Eueler #14"
from collections import namedtuple
Chain = namedtuple('Chain', 'length, start')


def calculate_chain(i):
    start = i
    length = 1
    while i != 1:
        length += 1
        if i & 1: # `i` is odd
            i = 3 * i + 1
        else:
            # Divide by two, efficiently.
            i = i >> 1
    return Chain(length, start)

def find_largest_chain(maxint):
    largest_chain = Chain(0, 0)
    for i in xrange(1, maxint+1):
        chain = calculate_chain(i)
        if chain > largest_chain:
            largest_chain = chain
    return largest_chain


def commandline_interface():
    from sys import argv
    maxint = int(argv[1])
    print find_largest_chain(maxint)

if __name__ == '__main__':
    commandline_interface()

Python での実行時間は 23 秒です。

$ /usr/bin/time python 10177836.py 999999
Chain(length=525, start=837799)
22.94user 0.04system 0:23.09elapsed 99%CPU (0avgtext+0avgdata 15648maxresident)k
0inputs+0outputs (0major+1109minor)pagefaults 0swaps

そしてpypyでは.93秒です：

$ /usr/bin/time ~/packages/pypy-1.8/bin/pypy 10177836.py 999999
Chain(length=525, start=837799)
0.66user 0.10system 0:00.93elapsed 81%CPU (0avgtext+0avgdata 63152maxresident)k
48inputs+0outputs (1major+4194minor)pagefaults 0swaps

pypy を使用するだけで、特定のアルゴリズムで 2373% の速度向上が得られます。OPが彼自身のコードで同様の改善を見ない理由はわかりません。