问题 为什么`mylist [:] = reverse(mylist)`工作?


以下内容将“就地”反转,并在Python 2和3中工作:

>>> mylist = [1, 2, 3, 4, 5]
>>> mylist[:] = reversed(mylist)
>>> mylist
[5, 4, 3, 2, 1]

为什么/怎么样?以来 reversed 给我一个迭代器,并不事先复制列表,从那以后 [:]= 取代“就地”,我很惊讶。以下,也使用 reversed,按预期打破:

>>> mylist = [1, 2, 3, 4, 5]
>>> for i, item in enumerate(reversed(mylist)):
        mylist[i] = item
>>> mylist
[5, 4, 3, 4, 5]

为什么不呢 [:] = 那样的失败?

是的,我知道 mylist.reverse()


6174
2018-06-02 18:45


起源

还有一个特例 l[a:b] = l。 - user2357112
@ user2357112哦,哇,真酷。不确定我是否曾经使用过它,但我可能会下意识地太害怕甚至不会想到它:-) - Stefan Pochmann
第一个片段是 不 执行就地算法(如在O(1)或恒定空间复杂度中),所以是时候开始质疑说它的来源了。 en.wikipedia.org/wiki/In-place_algorithm - Shashank
请注意wiki文章中的句子: 有时算法, 非正式地,只要它用输出覆盖其输入就称为就地。 但正式定义也需要恒定的空间复杂性。因此,混淆可能是由于短语的真实含义背后的误解造成的。 - Shashank
@Shashank嗯,我 没有 将“就地”放在引号中:-P。此外,如果右侧是一个列表,我认为它实际上将在严格的复杂意义上就位(似乎只是复制元素)。但实际上我有一个更宽松的定义,而不是算法的复杂性,而是在数据被写入旧对象而不是新对象的意义上。例如, list.sort() 记录为 “对列表中的项目进行排序。” 我不认为他们的意思是O(1)额外的空间。 - Stefan Pochmann


答案:


CPython list slice assigment将首先通过调用将iterable转换为列表 PySequence_Fast。资源: https://hg.python.org/cpython/file/7556df35b913/Objects/listobject.c#l611

 v_as_SF = PySequence_Fast(v, "can only assign an iterable");

即使PyPy也能做点什么 类似

def setslice__List_ANY_ANY_ANY(space, w_list, w_start, w_stop, w_iterable):
    length = w_list.length()
    start, stop = normalize_simple_slice(space, length, w_start, w_stop)
    sequence_w = space.listview(w_iterable)
    w_other = W_ListObject(space, sequence_w)
    w_list.setslice(start, 1, stop-start, w_other)

这里 space.listview 将会通知 ObjSpace.unpackiterable 解压缩iterable,然后返回一个列表。


12
2018-06-02 18:52



很好,感谢这两个链接。我自己有时会深入挖掘源代码,但在C部分有点丢失。很高兴也看到了 a[i:j] = a user2357112在那里处理的特殊情况。 - Stefan Pochmann
@StefanPochmann试试PyPy的来源,它更难。 :-) - Ashwini Chaudhary
我已经害怕它三次大喊“任意”了。 - Stefan Pochmann