最大化Collat??z猜想程式Python的效率

我的問題很簡單。

我寫這個程式純粹是為了娛樂。它需要一個數字輸入并找到每個 Collat??z 序列的長度，直到并包括該數字。

我想在演算法上或數學上讓它更快（即我知道我可以通過并行運行多個版本或用 C 撰寫它來使它更快，但這其中的樂趣在哪里？）。

歡迎任何和所有幫助，謝謝！

編輯：在 dankal444 的幫助下進一步優化代碼

from matplotlib import pyplot as plt
import numpy as np
import numba as nb

# Get Range to Check
top_range = int(input('Top Range: '))

@nb.njit('int64[:](int_)')
def collatz(top_range):
    # Initialize mem
    mem = np.zeros(top_range   1, dtype = np.int64)
    for start in range(2, top_range   1):
        # If mod4 == 1: (3x   1)/4
        if start % 4 == 1:
            mem[start] = mem[(start   (start >> 1)   1) // 2]   3
        
        # If 4mod == 3: 3(3x   1)   1 and continue
        elif start % 4 == 3:
            num = start   (start >> 1)   1
            num  = (num >> 1)   1
            count = 4

            while num >= start:
                if num % 2:
                    num  = (num >> 1)   1
                    count  = 2
                else:
                    num //= 2
                    count  = 1
            mem[start] = mem[num]   count

        # If 4mod == 2 or 0: x/2
        else:
            mem[start] = mem[(start // 2)]   1

    return mem

mem = collatz(top_range)

# Plot each starting number with the length of it's sequence
plt.scatter([*range(1, len(mem)   1)], mem, color = 'black', s = 1)
plt.show()

uj5u.com熱心網友回復：

在您的代碼上應用 numba 確實有很大幫助。

我洗掉了 tqdm，因為它對性能沒有幫助。

import time
from matplotlib import pyplot as plt
from tqdm import tqdm

import numpy as np
import numba as nb
@nb.njit('int64[:](int_)')
def collatz2(top_range):
    mem = np.zeros(top_range   1, dtype=np.int64)
    for start in range(2, top_range   1):
        # If mod(4) == 1: Value 2 or 3 Cached
        if start % 4 == 1:
            mem[start] = mem[(start   (start >> 1)   1) // 2]   3
        # If mod(4) == 3: Use Algorithm
        elif start % 4 == 3:
            num = start
            count = 0
            while num >= start:
                if num % 2:
                    num  = (num >> 1)   1
                    count  = 2
                else:
                    num //= 2
                    count  = 1
            mem[start] = mem[num]   count
        # If mod(4) == 2 or 4: Value 1 Cached
        else:
            mem[start] = mem[(start // 2)]   1
    return mem


def collatz(top_range):
    mem = [0] * (top_range   1)
    for start in range(2, top_range   1):
        # If mod(4) == 1: Value 2 or 3 Cached
        if start % 4 == 1:
            mem[start] = mem[(start   (start >> 1)   1) // 2]   3
        # If mod(4) == 3: Use Algorithm
        elif start % 4 == 3:
            num = start
            count = 0
            while num >= start:
                if num % 2:
                    num  = (num >> 1)   1
                    count  = 2
                else:
                    num //= 2
                    count  = 1
            mem[start] = mem[num]   count
        # If mod(4) == 2 or 4: Value 1 Cached
        else:
            mem[start] = mem[(start // 2)]   1
    return mem

# profiling here
def main():

    top_range = 1_000_000
    mem = collatz(top_range)
    mem2 = collatz2(top_range)
    assert np.allclose(np.array(mem), mem2)

對于 top_range = 1_000，優化函式的速度提高了大約 100 倍。對于 top_range = 1_000_000，優化后的函式大約快 600 倍：

    79                                           def main():
    81         1          3.0      3.0      0.0      top_range = 1_000_000
    83         1   24633045.0 24633045.0     98.7      mem = collatz(top_range)
    85         1      39311.0  39311.0      0.2      mem2 = collatz2(top_range)

標籤：Python 算法 表现 数学 考拉茨

上一篇：為什么Prolog看不到明顯的答案？

下一篇：Pandas資料幀上的SUMIF函式