13

The following reverses a list "in-place" and works in Python 2 and 3:

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

Why/how? Since reversed gives me an iterator and doesn't copy the list beforehand, and since [:]= replaces "in-place", I am surprised. And the following, also using reversed, breaks as expected:

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

Why doesn't the [:] = fail like that?

And yes, I do know mylist.reverse().

Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
  • There's also a special case for `l[a:b] = l`. – user2357112 Jun 02 '15 at 18:54
  • @user2357112 Oh wow, that's cool. Not sure I ever could've used that, but I probably would've subconsciously been too afraid to even think of it :-) – Stefan Pochmann Jun 02 '15 at 18:58
  • 1
    The first snippet is *not* executing an in-place algorithm (as in O(1) or constant space complexity) so it's time to start questioning the sources that say it is. http://en.wikipedia.org/wiki/In-place_algorithm – Shashank Jun 02 '15 at 20:06
  • Note the sentence in the wiki article: *An algorithm is sometimes, **informally**, called in-place as long as it overwrites its input with its output.* But the formal definition requires constant space complexity as well. So the confusion may be caused by misconceptions behind the phrase's true meaning. – Shashank Jun 02 '15 at 20:13
  • @Shashank Well I *did* put "in-place" in quotes :-P. Also, if the right side were a list, I think it actually would be in-place in that strict complexity sense ([seems to just copy the elements](https://hg.python.org/cpython/file/7556df35b913/Objects/listobject.c#l665)). But really I had a more relaxed definition in mind, not that algorithmic complexity kind but rather in the sense that the data is written into the old object rather than into a new one. For example, `list.sort()` is documented as *"Sort the items of the list in place."* and I don't think they mean O(1) extra space with that. – Stefan Pochmann Jun 02 '15 at 21:30
  • @Shashank And see my kind [winning the vote here](http://stackoverflow.com/questions/2779797/what-does-in-place-mean) :-P (the top two answers) – Stefan Pochmann Jun 02 '15 at 21:36

1 Answers1

14

CPython list slice assigment will convert the iterable to a list first by calling PySequence_Fast. Source: https://hg.python.org/cpython/file/7556df35b913/Objects/listobject.c#l611

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

Even PyPy does something similar:

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)

Here space.listview will call ObjSpace.unpackiterable to unpack the iterable which in turn returns a list.

Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
  • Great, and thanks for those two links. I sometimes digg into the source myself, though am a bit lost in the C parts. Nice to also see the `a[i:j] = a` special case mentioned by user2357112 treated there. – Stefan Pochmann Jun 02 '15 at 19:08