How To Know If A Command Or Method Is An 'in Place Algorithm'?

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 ?

Solution 1:

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.

Solution 2:

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

Solution 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.

Solution 4:

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.

Solution 5:

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.