计算Collatz序列

Question

我写了一个小脚本来计算Collatz序列。有关背景，请阅读关于Collatz猜想。到目前为止，我在实现过程中尝试过的最大数目是93571393692802302 (维基百科声称，这个数字需要10e17以下的大部分步骤)，需要2091个步骤。显然，我与维基百科不同，因为我的len(collatz(93571393692802302))是2092年，但我包括数字本身以及最后的1。

Collatz序列接受一个数字，并按顺序计算下一个数字如下：

• 如果是偶数，除以二。
• 如果是奇数，三倍加一。

Collatz猜想声称，所有这样创建的序列都收敛到1，这是未经证明的，但似乎大多数数学家怀疑它是真的。

“守则”没有进一步说明，而是：

from typing import List


collatz_cache = {}


def _calc(number: int) -> int:
    """
    Caches this number in the collatz_cache, and returns the next in sequence.
    :param number: Integer > 1.
    :return: Integer > 0
    """
    if number % 2 == 0:
        next_number = number // 2
    else:
        next_number = number * 3 + 1
    collatz_cache[number] = next_number
    return next_number


def collatz(number: int) -> List[int]:
    """
    Returns the collatz sequence of a number.
    :param number: Integer > 0
    :return: Collatz sequence starting with number
    """
    if not isinstance(number, int):
        raise TypeError(f"Collatz sequence doesn't make sense for non-integers like {type(number).__name__}")
    if number < 1:
        raise ValueError(f"Collatz sequence not defined for {type(number).__name__}({number})")
    new_number = number
    result = [number]
    while new_number not in collatz_cache and new_number != 1:
        new_number = _calc(new_number)
        result.append(new_number)
    while result[-1] != 1:
        result.append(collatz_cache[result[-1]])
    return result

在重复的尝试中，我尝试将计算时间最小化，方法是为每个数字创建一个映射到序列中的下一个数字。首先，我只是映射到完整的列表，但这将使字典比我真正想要的要大一些。

我觉得清单的建设应该有所收获，但我不知道该怎么做。

这个代码的目的基本上是一个通用的库函数。我想：

• 快一点
• 在我的缓存中提高内存效率
• 处理多个相等/部分重叠序列
• 处理完全不同的序列

所有这些都同时发生。当然，任何代码风格的改进都是受欢迎的，但是任何改进上述目标而又不与其他目标不成比例的缺点的建议也是值得欢迎的。

Answer 1

我认为缓存的处理可以改进。将其添加到_calc中的缓存中，然后在collatz中检查缓存。为什么不让_calc来处理缓存呢？这样，collatz就不需要知道_calc是如何得到它的结果的。我会把它改成这样的：

def _calc2(number: int) -> int:
    if number in collatz_cache:  # Let it do the lookup
        return collatz_cache[number]

    if number % 2 == 0:
        next_number = number // 2
    else:
        next_number = number * 3 + 1

    collatz_cache[number] = next_number
    return next_number

def collatz2(number: int) -> List[int]:
    if number < 1:
        raise ValueError(f"Collatz sequence not defined for {type(number).__name__}({number})")

    results = [number]

    new_number = number
    while new_number != 1:
        new_number = _calc2(new_number)
        results.append(new_number)

    return results

我也不认为collatz真的需要对number进行isinstance检查。你已经通过类型提示说它只接受整数。如果你要走这条路，可以说每个函数都应该检查它的参数是什么。我认为防止float被传递可能是值得的，因为这会悄悄地扰乱结果，但是您只能用手握住用户。

不过，我会注意到你的手动回忆录是不必要的。functools为此找了个装饰师：

from functools import lru_cache

@lru_cache(maxsize=int(1e6))  # This could probably be smaller
def _calc3(number: int) -> int:
    if number % 2 == 0:
        next_number = number // 2
    else:
        next_number = number * 3 + 1

    return next_number

使用使用种子随机数的脏timeit定时，我发现这三个版本对我的性能几乎相同：

from timeit import timeit
from random import randint, seed

timeit(lambda: collatz(randint(5, 100)),
       setup=lambda: seed(12345),
       number=int(1e6))

# All take between 7 seconds for me

我使用了随机数，所以缓存实际上得到了充分的测试，而不是一次又一次地返回相同的数字。随机数是seed编辑的，所以结果应该是可靠的。

我要指出的是，您还可以编写自己的赤裸的memoize装饰器：

def memoize(f):
    cache = {}

    def wrapper(*args):
        if args in cache:
            return cache[args]

        else:
            result = f(*args)
            cache[args] = result
            return result

    return wrapper

@memoize
def tester(n, m):
    print("Called with", n, m)
    return n + m

>>>> tester(1, 3)
Called with 1 3
4

>>> tester(1, 3)
4

不过，我也要注意，如果您想要将其概括，可以将其变成生成器：

from typing import Generator

def collatz3(number: int) -> Generator[int, None, None]:
    yield number  # To be consistent with the other functions

    new_number = number
    while new_number != 1:
        new_number = _calc3(new_number)
        yield new_number

这可能被证明是更有效的内存更长的序列，取决于它是如何使用。现在，整个序列不需要同时保存在内存中。

Answer 2

我同意@Carcigenicate的观点，即将缓存责任分成两个函数并不是一个好主意。但与他相反，我会让主collatz函数来处理它，因为它具有特定的知识，一旦您访问缓存，您知道其余的序列也将在那里。

这是一个实现。

from typing import List

_cache = { 1: None }

def _next(i: int) -> int:
    """
    Returns the next element in the Collatz sequence
    """
    if i % 2:
        return 3 * i + 1
    else:
        return i // 2

def collatz(i: int) -> List[int]:
    """
    Returns the collatz sequence of a number.
    :param number: Integer > 0
    :return: Collatz sequence starting with number
    """
    r=[] 
    while i not in _cache: 
        r.append(i) 
        n = _next(i) 
        _cache[i] = n 
        i = n
    while i: 
        r.append(i) 
        i = _cache[i] 
    return r

这使得这个版本对我来说更快了一些。

Answer 3

我是自学成才的Python，没有你那么有经验。所以我对你的代码有几个问题。我主要想知道，为这么简单的问题，你为何要建立这么复杂的逻辑呢？TBH，我甚至不确定我是否完全理解您的代码在做什么。下面我已经粘贴了我的代码，它在0.0005中给出了正确的答案(2091步)，我想这足够小了。您是否试图在比这更短的时间内运行它，从而导致复杂的逻辑？

def collatz(n):
    steps = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = (n * 3) + 1
        steps += 1

    print(steps)