在迭代过程中向列表添加元素

Question

我知道在迭代列表时不允许删除元素，但是在迭代时是否允许向Python列表中添加元素呢？以下是一个例子：

for a in myarr:
    if somecond(a):
        myarr.append(newObj())

我在我的代码中尝试过这个方法，看起来运行得很好，但是我不知道是不是因为我运气好，而且它将在将来的某个时候出现问题？

我不想复制列表，因为myarr非常庞大，这样会导致速度太慢。而且我需要使用somecond()来检查追加的对象。

在某个时刻，somecond(a)将会返回false，所以不会出现无限循环。

myarr中的每个对象都有一个大小，每当somecond(a)为true并且一个新对象被追加到列表中时，新对象的大小将小于a。somecond()有一个epsilon来确定对象的最小大小，如果太小，它将返回"false"。

- WesDec

---

复制一个列表不需要太多时间。这是一份浅拷贝，而不是深拷贝。 - S.Lott

@S.Lott：该列表很容易超过1亿个元素，并且上述循环会重复多次。即使是浅拷贝也会很慢。 - WesDec

你说你已经做到了这一点，那么你的循环是否遍历了被添加到列表中的项以及原来列表里的项？ - Mike DeSimone

@WesDec：你似乎在谈论广度优先搜索。对于你所做的事情来说，一个简单的列表是不合适的。这听起来像是某种树结构，而不是一个简单的列表。 - S.Lott

@WesDec：此外，请不要添加道歉的评论。专注于正确地提出问题即可。 - S.Lott

解决这个问题的方法取决于是否希望迭代遍历新元素。 - Karl Knechtel

Answer 1

为什么不按照C语言的惯用方式来做呢？这样做应该是非常可靠的，但它可能不会很快。我相当确信在Python中对列表进行索引会遍历链接列表，因此这是一个“ Shlemiel the Painter”算法。但我通常不会担心优化，除非某个代码段确实成为了问题。先让它工作；然后如果必要，再考虑如何加速它。

如果你想迭代所有的元素：

i = 0  
while i < len(some_list):  
  more_elements = do_something_with(some_list[i])  
  some_list.extend(more_elements)  
  i += 1  

如果你只想遍历原来在列表中的元素：

i = 0  
original_len = len(some_list)  
while i < original_len:  
  more_elements = do_something_with(some_list[i])  
  some_list.extend(more_elements)  
  i += 1

- Johnny

---

Python的列表类似于C数组或C++向量; 它们的索引是常数时间。实际上，这是一个相当不错的解决方案，因为它可以执行与OP算法相同的操作，而不依赖于未定义的行为。 - Petr Viktorin

但那真的是C语言的方式，为什么不至少使用：for i in range(len(some_list))？ - borgr

Answer 2

根据http://docs.python.org/tutorial/controlflow.html

在循环中修改被迭代的序列是不安全的(只有可变序列类型（如列表）才可能发生这种情况)。如果需要修改正在迭代的列表(例如复制选定的项)，则必须在副本上迭代。

- Rohan Monga

---

我知道这段文本，但其他语言中的迭代器通常支持在迭代时向列表末尾添加新元素。我希望Python也支持这一点，因为这会使事情更简单、更易读。 - WesDec

我同意，但唯一的解决方案是制作一份副本，这也在教程中有所解释。 - Rohan Monga

用索引迭代列表而不是 for a in myarr 怎么样？也就是说，i = 0; while i < len(myarr): a = myarr[i]; i = i + 1; if somecond(a): myarr.append(newObj()) - HelloGoodbye

文件似乎已经有所改变，现在它没有说这是不安全的，只是说这可能很棘手：在迭代同一个集合时修改该集合的代码可能难以正确实现。相反，通常更加直接的方法是遍历该集合的副本或创建一个新的集合： - Motti

Answer 3

您可以使用 itertools 的 islice 来创建一个迭代器，该迭代器只迭代列表的一小部分。这样，您就可以在不影响正在迭代的项目的情况下向列表中添加条目：

islice(myarr, 0, len(myarr)-1)

更好的是，你甚至不需要遍历所有元素。你可以增加一个步长。

- wheaties

---

请不要这样做。据我所知，这是未定义的行为，可能会导致崩溃。Python的列表在底层类似于动态C数组（或C++ std::vector）：添加一个元素可能会导致整个数组的重新分配以适应新元素。如果发生这种重新分配，则我认为islice()将指向旧的、现在悬空的内存。最受赞同的答案绝对看起来像是在迭代列表时添加元素的唯一快速且安全的方法。它说“它不会很快”，但这是不正确的，它几乎和正常迭代一样快。 - Boris Dalstein

抱歉我之前给你的投票是负面的，我错了，现在我会给你一个正面的赞成票 :) （注意：我必须编辑你的答案才能改变我的投票）。另一个回答中提到的一个好的测试确实很不错：a = [0]\nfor i in a:\n print(a)\n if i < 100:\n a.append(i+1)。这个测试正确地打印出从0到100的所有整数。这证明了Python列表迭代器实际上并没有直接指向内存：它们存储了指向列表对象和索引的指针。 - Boris Dalstein

Answer 4

简而言之：如果你确信所有新对象都无法通过somecond（）检查，那么你的代码运行良好，只是浪费了一些时间迭代新添加的对象。

在给出适当答案之前，您必须了解为什么在迭代时更改列表/字典被认为是一个坏主意。在使用for语句时，Python试图变得聪明，并返回动态计算的每个项。以list为例，python记住一个索引，并每次返回l[index]给你。如果您更改了l，则结果l[index]可能会很混乱。

注意：这里有一个stackoverflow问题来证明这一点。

在迭代时添加元素的最坏情况是无限循环，请尝试（或不尝试，如果您能够读取错误）在Python REPL中执行以下操作：

import random

l = [0]
for item in l:
    l.append(random.randint(1, 1000))
    print item

它会不停地打印数字，直到内存被使用完或被系统/用户杀死。

为了理解原因，让我们讨论一些解决方案。以下是几种：

1. 复制原始列表

迭代原始列表，并修改复制的列表。

result = l[:]
for item in l:
    if somecond(item):
        result.append(Obj())

2. 控制循环结束的方式

不必将控制权交给 Python，您可以决定如何迭代列表：

length = len(l)
for index in range(length):
    if somecond(l[index]):
        l.append(Obj())

在迭代之前，计算列表长度，并仅循环length次。

3. 将添加的对象存储在新列表中

不要修改原始列表，将新对象存储在新列表中，然后进行连接。

added = [Obj() for item in l if somecond(item)]
l.extend(added)

- cizixs

---

你真是个大明星！我的脑子完全空白，就像个傻瓜一样，竟然没想到创建一个新列表。 - Thomas Pegler

Answer 5

你可以做到这一点。

bonus_rows = []
for a in myarr:
  if somecond(a):
      bonus_rows.append(newObj())
myarr.extend( bonus_rows )

- S.Lott

---

这不好，因为我还需要检查bonus_rows中的对象，如果其中一些对象满足somecond()条件，我也需要为它们创建新的对象。 - WesDec

@WesDec：这就是为什么你需要“嵌套”循环。将所有内容都包含在一个更大的循环中。 - S.Lott

@WesDec：或者停止使用简单列表，改用树形结构。这听起来像广度优先搜索，而列表是错误的数据结构。 - S.Lott

在纯Python中，基于类的树可能效率低下。 - tejasvi88

Answer 6

复制原列表，对其进行迭代，参见下面修改后的代码

for a in myarr[:]:
      if somecond(a):
          myarr.append(newObj())

- shahjapan

---

问题在于这个列表非常庞大，每次复制都会非常慢。 - WesDec

@WesDec：在宣称它“非常慢”之前，请先进行测量。这是一个浅拷贝，速度相当快。 - S.Lott

@S.Lott：该列表很容易超过1亿个元素，并且上述循环会重复多次。即使是浅拷贝也会很慢。 - WesDec

Answer 7

通过i直接访问列表元素，然后您可以将内容附加到列表中：

for i in xrange(len(myarr)):
    if somecond(a[i]):
        myarr.append(newObj())

- eumiro

---

@Justin Peel - 你用这个解决方案的速度更快。 - eumiro

这是一个很好的选择，如果你想在附加的项目上使用相同的循环代码，同时仍然保持DRY。似乎其他解决方案都没有预料到这种情况的使用。 - NeilG

Answer 8

我今天遇到了类似的问题。我有一个需要检查的项目列表；如果对象通过了检查，它们会被添加到结果列表中。如果它们没有通过检查，我会对它们进行一些改动，如果它们可能仍然有效（改动之后大小 > 0），我会将它们添加到列表的末尾以便重新检查。

我选择了以下解决方案：

items = [...what I want to check...]
result = []
while items:
    recheck_items = []
    for item in items:
        if check(item):
            result.append(item)
        else:
            item = change(item)  # Note that this always lowers the integer size(),
                                 # so no danger of an infinite loop
            if item.size() > 0:
                recheck_items.append(item)
    items = recheck_items  # Let the loop restart with these, if any

我的列表实际上是一个队列，可能应该使用某种类型的队列。但是我的列表很小（大约10个项目），这也可以。

- RemcoGerlich

Answer 9

如果您想让循环也遍历在循环期间添加到列表中的元素，可以使用索引和while循环代替for循环：

i = 0
while i < len(myarr):
    a = myarr[i];
    i = i + 1;
    if somecond(a):
        myarr.append(newObj())

- HelloGoodbye

Answer 10

扩展S.Lott的答案，以便新项目也可以被处理：

todo = myarr
done = []
while todo:
    added = []
    for a in todo:
        if somecond(a):
            added.append(newObj())
    done.extend(todo)
    todo = added

最终列表在done中。

- Mike DeSimone