1

I'm learning python, how can I know if a command or method is an 'in place algorithm' ?

Does trying 'big' inputs and checking the runtime with the command a good enough indicator ?

For example, say I have a list lst with 100,000 elements. I checked the following two commands and both 'finished' in a moment: lst = lst[ : :-1] and lst.reverse(). So does that mean that both are in place ?

GinKin
  • 187
  • 7
  • Are you talking about their underlying implementation? – devnull Mar 17 '14 at 12:05
  • @devnull I don't understand the question. – GinKin Mar 17 '14 at 12:09
  • How do you plan to distinguish between O(1) extra space and O(A^(-1)(n)) where `A^(-1)` is the inverse of the Ackermann function? A^(-1)(n) will be at most 4 with *any* input you could possibly test, so by all means it's equal to O(1) in practical tests but it's *not* considered in-place. – Bakuriu Mar 17 '14 at 12:16
  • @Bakuriu Given what I've heard people say about the union find data structure, most would treat `O(A^(-1)n)` space as effectively constant space (well justified) and not quibble over calling it an in-place algorithm. –  Mar 17 '14 at 12:29
  • @delnan Well people also say that quicksort is in-place when it takes O(log(n)) space. My point is that if we use a rigorous definition of in-place it's simply impossible to accurately determine whether a given implementation of such an algorithm effectively takes constant space through experimentation. – Bakuriu Mar 17 '14 at 15:43
  • @Bakuriu That's just a specific application of the fact that experimentation can't establish asymptotic complexity, but yes. It just doesn't appear terribly useful or relevant, partly since the definition of in-place algorithm is a bit fuzzy. –  Mar 17 '14 at 15:53

5 Answers5

4

If a function is inplace, then it will modify the object which calls it. If it not, then it will return the result instead.

sorted(lst) # returns the sorted form of lst
lst.sort() # sorts lst

That's all there is to it. Don't try to relate it to running times or efficiency.

Jayanth Koushik
  • 9,476
  • 1
  • 44
  • 52
3

In-place operation usually return None in Python, so in your case lst.reverse() is an in-place operation as it returns None and modifies the list as well. While lst[::-1] returns a new list that you re-assigned to lst.

>>> lst  = range(1000)
>>> id(lst)
154457996
>>> lst = lst[::-1]
>>> id(lst)             #id changed.
160699852
>>> lst  = range(1000)
>>> id(lst)
160699340
>>> lst.reverse()
>>> id(lst)             #same id
160699340
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
  • Is it just me or is the definition of in-place algorithm kind of misleading? Some say it is an algorithm that doesnt use any auxillary data structures. Some methods in python like lst.sort() return None but the sort method may use auxillary data structures to perform the sort (i.e. merge sort) so by wikipedias definition it isnt in-place – vi_ral Apr 14 '20 at 23:53
3

To answer this question,we must fist know what is 'in place algorithm'?

By the wikipedia, an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

What's the relationship between 'Overwrite input' and 'in place algorithm':

1. If one overwrite it's input, isn't it must an in place algorithm?

No, for example, the quicksort always overwrite it's input, but it need O(log(n)) extra space to keep track of the recursive function calls.

2. If one is an in place algorithm, does it must overwrite its input?

No, for example, the algorithm that find the minimum number in an array, it's an in place algorithm, only require O(1) extra space, but it need not to overwrite its input.

So, there is no absolute relationship between them, the input is usually overwritten by a in place algorithm.

And how to know if a method in an in place algorithm?

Well, I think you must look at it's implementation, the source code, the same method may use the different algorithm, after all, methods or functions are not the same thing as algorithms.

BTW, there is an easy way to know if the input of an method is overwritten:

>>> lst = [1, 2, 3]
>>> id(lst)`
3070142764
>>> lst = lst[: : -1]
>>> id(lst)
3070142828
>>> lst.reverse()
>>> id(lst)
3070142828

After lst[: : -1], the id of lst has changed, so lst[: : -1] create a new list object, and after lst.reverse(), the id of lst isn't changed, so lst.reverse() overwritten its input.

Community
  • 1
  • 1
zbtong
  • 319
  • 1
  • 8
2

If you're using something like iPython you can ask the interpreter -

In [1]: x = [1, 2, 3]

In [2]: ? x.reverse
Type:       builtin_function_or_method
Base Class: <type 'builtin_function_or_method'>
String Form:<built-in method reverse of list object at 0x0362EB48>
Namespace:  Interactive
Docstring:  L.reverse() -- reverse *IN PLACE*

So the reverse method is in-place. In general, something like

In [3]: x = x[::-1]

won't be in-place, since a copy is created first, and then assigned to x. You know that this can't be in-place, since a similar assignment

In [4]: y = x[::-1]

certainly must create an additional copy of x.

Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
0

Off the top of my head, I would think looking at the memory consumption while running the program would be a better indicator. As I understand "in-place", it means that no (or little) additional space is needed to run the algorithm. http://en.wikipedia.org/wiki/In-place_algorithm.

For your particular examples, I would think that the fast running time is most likely due to the list implementation used. My first guess would be that lists are implemented using doubly linked lists. This in turn then of course means that reverse will be performed in-place.

If you want to be sure though, I think you need to jump head first into the code implementing the algorithm in question.

Rikke Bendlin Gammelmark
  • 940
  • 1
  • 8
  • 10
  • In interpreted languages memory consumption need not be correlated with the space complexity of an algorithm. For example a python list uses more memory then the memory necessary to hold its memory, in order to reduce the cost of following `append`s. If you don't take this into consideration you'll probably find different results when profiling memory usage with respect to what you'd expect from the algorithm space analysis. – Bakuriu Mar 17 '14 at 12:14
  • @Bakuriu Over-allocation for dynamic arrays has absolutely nothing to do with being interpreted or with the object model, it's as language agnostic as data structure decisions get (its rationale is formulated in the RAM model of computation). But you're right that there are many pitfalls with measuring memory consumption. –  Mar 17 '14 at 12:18
  • And as for this answer: `list` is not a doubly linked list. Thankfully, it's a dynamic array. Reversing one is fast indeed, but it's not constant time. –  Mar 17 '14 at 12:20
  • @delnan I probably misused "interpreted" there, but I meant any kind of language that provides sufficiently high-level operations. For example not C because in C you explicitly allocate a precise amount of memory and as such, given a C program is easier to understand how much memory a given algorithm should use, which isn't as easy with a python program for example. – Bakuriu Mar 17 '14 at 15:40
  • @Bakuriu Memory management is more explicit, but can still mostly be hidden inside libraries. Consider code like `PyListObject *L = PyList_New(0); PyList_Append(L, x);` –  Mar 17 '14 at 15:51