6

What's the particular reason that some functions in Python operate "IN PLACE", like [].sort and [].reverse, while some others like [].append not?

Paolo
  • 20,112
  • 21
  • 72
  • 113
  • 7
    By what definition does `[].append` not work "in place" ? – Jochen Ritzel Mar 15 '11 at 20:47
  • Does `append` return a new copy of the list, leaving the old one unmodified? – Matt Ball Mar 15 '11 at 20:47
  • help([].sort) _explicitly_ states that sorting happens "in place", but help([].append) doesn't... – Paolo Mar 15 '11 at 20:50
  • @Matt Ball: Nope. It appends to the existing list and doesn't return anything. – Omnifarious Mar 15 '11 at 20:50
  • 4
    That's because sorting algorithms are frequently classified as "in-place" and "not-in-place," whereas `[].append` would obviously just modify the existing data structure, unless it's immutable. http://en.wikipedia.org/wiki/In-place_sorting – Matt Ball Mar 15 '11 at 20:52
  • 3
    @Guandalino: But both operate in place. Perhaps it's not spelled out in the documentation on `.append` because the non-in-place version would be called `concat` (and is in fact the `+` operator). –  Mar 15 '11 at 20:52
  • @Omnifarious: that's basically the point I was making (a rhetorical question). – Matt Ball Mar 15 '11 at 20:52
  • @Matt Ball: Your question doesn't make any sense then. All the functions you mention operator 'in place'. They do not create new copies of the data structure they operate on. – Omnifarious Mar 15 '11 at 20:54
  • @delnan: but isn't that only because `concat` takes both operands as arguments? If the function was `[].concat`, that would be in-place as well, right? – Matt Ball Mar 15 '11 at 20:54
  • @Mat Ball: The `+` operator as applied to lists creates a brand new list containing all the elements of the two lists being added. It does not operator `in place`. And yes, if it were a member function that didn't take two arguments, it would also operate `in place`. The name change would not change the semantics of `append`. – Omnifarious Mar 15 '11 at 20:55
  • http://en.wikipedia.org/wiki/In-place_algorithm – Jochen Ritzel Mar 15 '11 at 20:57
  • @Matt: Now that you mention it, I suppose one *might* call in-place appending `.concat`. Honestly, I'd never even consider using that name for a method that's operating in-place. `append` is tied to modification while `concat` can be both in-place and out-of-place... –  Mar 15 '11 at 21:00

2 Answers2

7

According to my Programming Python 4th edition:

By default, pop is equivalent to fetching, and then deleting, the last item at offset −1. With an argument, pop deletes and returns the item at that offset—list.pop(-1) is the same as list.pop(). For in-place change operations like append, insert, del, and pop, no new list is created in memory, so execution is quick (performance may further de- pend upon which end is the “top,” but this in turn depends on Python’s current list implementation, as well as measurement concepts we’ll explore later).

There is actually a whole section devoted to this, but this pretty much answers your question.

Martin Tournoij
  • 26,737
  • 24
  • 105
  • 146
1

"in-place" refers to a sorting algorithms use of only the memory needed to store the list of items plus some small constant. Append isn't a sorting algorithm and thus "in-place" is not meaningful, or at least wouldn't mean the same thing. You're confusing "in-place" in sorting and whether or not it returns a reference to a new object or a modified version of the same object.

Paolo
  • 20,112
  • 21
  • 72
  • 113
cmaynard
  • 2,852
  • 2
  • 24
  • 34
  • 4
    That's not how "in-place" is used when referring to sorting algorithms, or more generally, algorithms which rearrange arrays/lists. – Matt Ball Mar 15 '11 at 21:15
  • Thanks, but I linked to that article in my comment (on the question) half an hour ago. I'm talking about sorting algorithms such as [heapsort](http://en.wikipedia.org/wiki/Heapsort), which is in place, vs. typical implementations of [quicksort](http://en.wikipedia.org/wiki/Quicksort). – Matt Ball Mar 15 '11 at 21:29