生成无限列表？

Question

知道这很可能会以失败告终，我想知道 Python 将如何处理这种情况以及我的代码是否实际上 "makes sense"，至少在原则上是这样。所以这是我的尝试，我对 python（几天前）还很陌生，所以我相信我的代码对那些有更多经验的人来说似乎很有趣，但请多多包涵。

def make_inf_lst(lst):
  lst = [0]
  while 1 == 1:
    for i in range(0, len(lst)):
      add = lst[i] + 1
      lst.append(add)
print(make_inf_lst([]))

这是我在 DOS window 中尝试运行以上内容时遇到的错误：

Traceback (most recent call last):
  File "break_python.py", line 7, in <module>
    print(make_inf_lst([]))
  File "break_python.py", line 6, in make_inf_lst
    lst.append(add)
MemoryError

提前致谢。

Answer 1

具有 "infinite" 数据结构的语言实际上正在生成延迟生成其值的对象，或 "on-demand"。他们不是预先创建整个列表，而是创建一个对象，当被要求提供一个值时，可以在那个时候创建它。

在 Python 中，使用生成器最容易管理。

def make_inf_sequence():
    x = 0
    while True:
        yield x
        x = x + 1

# This returns immediately
naturals = make_inf_sequence()

# This loop runs forever
for i in naturals:
    print(i)

Answer 2

无限数据结构确实有意义，但它们总是必须延迟计算。这意味着您的数据结构无法立即构建其所有元素，然后自行移动（就像我们通常对适合内存的 list 所做的那样）。相反，您的数据结构需要根据您的需要为您提供值。

在 Python 中，你不能有无限的 list 因为 list 是渴望的，而不是懒惰的（就像 Python 中的大多数事情一样，渴望是默认）。需要明确的是，我在这里谈论 list 类型 w.r.t。 Python 术语，而不是一些序列的抽象概念（某些人可能称之为列表）。

惰性求值的方法是使用一种叫做 generator 的东西。如果你想生成序列1,2,3,4,...，你可以用下面的代码来完成：

def gen_natural_numbers():
    cur = 1
    while True:
        yield cur
        cur += 1

natural_num_gen = gen_natural_numbers()
print("One: ", next(natural_num_gen))
print("Two: ", next(natural_num_gen))
print("Three: ", next(natural_num_gen))

这个输出：

One:  1
Two:  2
Three:  3

显然，您不必在 3 处停止。您不必在任何地方停止（除非您创建的 int 实际上不适合内存）。如果你一直调用 next，生成器会一直返回值给你。

随着您的进行，垃圾收集器可以从内存中删除不再包含引用的值。这完全是另一个话题，但应该注意的是，只要您不永远保留引用，您的程序在使用生成器时也不会运行内存不足。

Answer 3

基本上有两件事可以阻止打印无限列表（这似乎是您代码的最终目标）：

计算机将运行内存不足。
列表的创建将花费无限时间，这意味着它永远不会完成，实际打印也永远不会开始。

如果你想象一台具有无限内存和无限计算速度的假想计算机，可以打印列表。

然而，某些语言通过 "lazy" 支持无限列表，这意味着它们将只计算列表中特定点所需的部分。然后你可以定义一个无限列表并要求它打印出来，例如其中的前 100 个值。

更多关于惰性计算的信息： https://en.m.wikipedia.org/wiki/Lazy_evaluation

Answer 4

从您可以立即访问宇宙中所有成员的意义上说，它不可能是无限的。那是不可能的——无限长度意味着需要无限的内存。从你得到的错误可以看出，你没有无限的内存。正如其他人所说，您可以用速度换取长度：

from copy import deepcopy
class infinite_ints:
    def __init__(self):
        self.list = []
        self.trans = lambda x: x;

    def __getitem__(self,at):
        try:
            return self.trans(self.list[at])
        except IndexError:
            self.list += [i for i in range(len(self.list),at+1)]
        return self.trans(self.list[at])

    def apply(self,function):
        new_list = deepcopy(self)
        new_list.trans = lambda x,f=function,p=self.trans: f(p(x))
        return new_list

>>> x[2]
2
>>> x[12]
12
>>> x[43]
43
>>> y = x.apply(lambda x: x+1)
>>> y[59]
60

在这里，如果需要，我将常规列表与即时扩展结合起来。我不必从一个空列表开始，如果我愿意的话，我可以预先制作前 N 个元素。

您当然可以重载运算符（+、- 随便什么）。关键是一切都是一次性完成的。以这种方式工作，您甚至可以添加和减去无限列表。

您甚至可以使用内存管理来改进这一点，如果有一段时间不查看，则删除列表的开头，但我认为这超出了范围。更实用的方法是保存当前数字和继续的方式（我添加了一个 prev 类似于内置 __next__:

def prev(x):
    return x.__prev__()

class infinity_functional:
    def __init__(self):
        self.n=0
    def __next__(self):
        Next   = infinity_functional()
        Next.n = self.n + 1
        return Next
    def __prev__(self):
        Prev   = infinity_functional()
        Prev.n = self.n - 1
        return Prev
    def __repr__(self):
        return str(self.n)

enter code here

>>>x=infinity_functional()
>>>x
0
>>> next(next(next(x)))
3
>>> y=next(next(next(x)))
>>> prev(y)
2

同样，可以轻松实现运算符（不仅仅是表示）或跳转多个运算符。

Answer 5

您的计算机在构建列表时有时内存不足，这就是导致您看到的错误的原因。无限列表是不可能的，因为内存是一种有限的资源。

或者，您可以使用无限迭代器。标准库提供了一些无限迭代器。根据你的例子，我认为最适合你的情况是 itertools.count.

示例用法：

>>> from itertools import count
>>> it = count()
>>> next(it)
0
>>> next(it)
1

您还可以指定自定义起点：

>>> from itertools import count
>>> it = count(5)
>>> next(it)
5
>>> next(it)
6

和自定义步骤：

>>> from itertools import count
>>> it = count(5, 2)
>>> next(it)
5
>>> next(it)
7
>>> next(it)
9

生成无限列表？

Generating an infinite list?

python

list

infinite

python-3.x