python - 在Python Itertools中获取一组迭代次数中最大值的索引

Question

(这是 Project Euler Problem 14)

我正在尝试通过使用 Itertools 来丰富我的 Python 技能。

我想从 Python 的 itertools 中的生成器中获取设定迭代次数 (1,000,000) 中的最大返回值的索引。

该函数有效，但我无法弄清楚如何有效地获得最大值而不将其存储在一个巨大的一百万长列表中，我认为这对此几乎没有效率。有没有一种聪明的方法呢？ (编辑:也许这是最简单的方法？)

当前的代码是当链达到 100 时停止，这是错误的。

#Project Euler Problem 14
#Which starting number, under one million, produces the longest chain?

import itertools

def length():
    x=1

    while True:
        l=0

        c=x #Create the running integer.
        while c>1:
            if c%2==0:
                #Number is even, divide it by two.
                c=c/2
                l+=1
            else:
                #Number is odd, multiply by three and add one.
                c=3*c+1
                l+=1

        yield l+1   #Add the final one as well and show the chain length.
        x+=1        #Increment


print list(itertools.takewhile(lambda x:x<100,length()))

Answer 1

我按如下方式解决了这个问题:

import functools

def euler_014(max_=1000000):
    longest = max_len = None
    for n in range(1, max_):
        length = len_collatz(n)
        if max_len is None or length > max_len:
            max_len, longest = length, n
    return longest

def memoize(f):
    cache = {}
    @functools.wraps(f)
    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return func

@memoize
def len_collatz(n):
    if n == 1:
        return 1
    if n % 2:
        n = (n * 3) + 1
    else:
        n //= 2
    return 1 + len_collatz(n)

这里 memoize 通过存储 len_collat​​z 的先前结果使事情变得更加高效，len_collat​​z 告诉您来自 n 的序列的长度 到 1(没有实际生成整个序列的列表)，而 euler_014 只需跟踪最长长度和相关的 值n。请注意，它不会保留所有结果 - 只保留迄今为止最长序列的长度以及生成该序列的 n 值。