python - 在python中生成序列的第30亿个元素

Question

我正在尝试生成以下序列:

011212201220200112 ... constructed as follows: first is 0, 
then repeated the following action: 
already written part is attributed to the right with replacement 
0 to 1, 1 to 2, 2 to 0.
E.g.

0 -> 01 -> 0112 -> 01121220 -> ...

我试图找到这个序列的第 30 亿个元素。我意识到序列呈指数增长，因此得出:

log(base2) (3 billion)  ~ 32

所以我只需要生成这个序列 32 次。

这是我在 python 中尝试的:

import os
import sys



s=['0']
num_dict = {'0':'1' , '1':'2' , '2':'0'}

def mapper(b):  
    return num_dict[b]  


def gen(s):
    while True:         
        yield s     
        s.extend( map(mapper,s) )


a = gen(s)
for i in xrange(32):
    a.next()

print a.next()[3000000000 - 1]

问题是我的 RAM 在达到 30 亿大关之前就被填满了。有没有更好的方法来解决这个问题？

编辑:该程序可能会使您的机器崩溃。请尝试使用 xrange(25) 进行测试

Answer 1

评论中有足够的提示，您应该能够找到单行解决方案。我认为尝试使用更通用的工具(即隐式数据结构)来推导它会更有趣。这是单例列表的类。

class Singleton:
    def __init__(self, x):
        self.x = x

    def __getitem__(self, i):
        if not isinstance(i, int): raise TypeError(i)
        elif not (0 <= i < len(self)): raise IndexError(i)
        else: return self.x

    def __len__(self): return 1

我们可以像这样使用这个类。

>>> lst = Singleton(42)
>>> lst[0]
42
>>> len(lst)
1

现在我们定义一个连接类和一个映射器类，后者接受一个函数并将其隐式应用于每个列表元素。

class Concatenation:
    def __init__(self, lst1, lst2):
        self.lst1 = lst1
        self.lst2 = lst2
        self.cachedlen = len(lst1) + len(lst2)

    def __getitem__(self, i):
        if not isinstance(i, int): raise TypeError(i)
        elif not (0 <= i < len(self)): raise IndexError(i)
        elif i < len(self.lst1): return self.lst1[i]
        else: return self.lst2[i - len(self.lst1)]

    def __len__(self): return self.cachedlen


class Mapper:
    def __init__(self, f, lst):
        self.f = f
        self.lst = lst

    def __getitem__(self, i): return self.f(self.lst[i])

    def __len__(self): return len(self.lst)

现在让我们重写您的代码以使用这些类。

a = Singleton(0)
for i in range(32):
    a = Concatenation(a, Mapper({0: 1, 1: 2, 2: 0}.get, a))
print(a[3000000000 - 1])

作为练习:为什么我们需要 cachedlen？