Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time complexity of swapping elements in a python list

What is the Time complexity of swapping elements in a python list if I do the following

Case1: (Idiomatic way) Swaping two elements in a list

>>> a = [1, 2, 3, 4, 5]
>>> a[1], a[3] = a[3], a[1]  # Pythonic Swap --> x, y = y, x

>>> print(a)
[1, 4, 3, 2, 5]

Question1: What is the time complexity of the swap step? And what does python internally do.


Case2: (Very Inefficient way) Swaping two elements in a list

>>> a = [1, 2, 3, 4, 5]
>>> temp1, temp2 = a[1], a[3]
>>> del a[1]  # a = [1, 3, 4, 5]
>>> a.insert(1, temp2)  # a = [1, 4, 3, 4, 5]
>>> del a[3]  # a = [1, 4, 3, 5]
>>> a.insert(3, temp1)  # a = [1, 4, 3, 2, 5]
>>> print(a)
[1, 4, 3, 2, 5]

If I do it this way, Whenever I insert or delete at any index all the memory addresses present right to that index need to be moved/copied one step right or left respectively. So it takes O(K) where K is the number of addresses present right to the index where we inserted or deleted. Correct me if I am wrong.


Some Profiling

If the list is very small the run time complexity doesn't matter much which ever approach (Case1 or Case2) I use. But what if the list is very big like a = [i for i in range(0,1000000)] then what is the efficient way to swap two elements in a list. Here I did some basic profiling on the above two cases with a million record list swapping index 100 and 54321 and here is the result. Surprisingly both cases have almost the same performance.

a = [i for i in range(0,1000000)]

Case1 Profiling

$ time python3 case1_script.py

real    0m0.129s
user    0m0.088s
sys     0m0.041s

$ python3 -m cProfile case1_script.py

3 function calls in 0.060 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.047    0.047    0.060    0.060 list_ele_swap_profile.py:1(<module>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    1    0.013    0.013    0.013    0.013 {range}

Case2 Profiling

$ time python3 case2_script.py

real    0m0.132s
user    0m0.090s
sys     0m0.042s

$ python3 -m cProfile case2_script.py

5 function calls in 0.115 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.048    0.048    0.115    0.115 list_ele_swap_profile.py:1(<module>)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     2    0.001    0.001    0.001    0.001 {method 'insert' of 'list' objects}
     1    0.066    0.066    0.066    0.066 {range}

Question2: what is the efficient way to swap two elements in a list if the list is very big like above.

Question3: While thinking about this problem I have one more doubt, So if the deletion of an arbitrary element (let say middle index element) from the list requires copying/moving of the memory addresses then how is the deletion of an element from the list is O(1).


PS: I don't think this is a duplicate question, I have gone through the following questions but none of them have what I am looking for. I am interested in knowing the time/space complexity for the above operations. Thanks.

  • Fastest way to swap elements in Python list
  • Swapping elements in lists in python
  • Swapping numbers in lists
  • How does swapping of members in the python tuples (a,b)=(b,a) work internally?
  • Is there a standardized method to swap two variables in Python?
like image 503
ravi Avatar asked Jun 10 '15 01:06

ravi


People also ask

What is the time complexity of a swap in Python?

Time and Space complexity We are using array Destructuring to swap numbers, so Time complexity is O(1).

Can you swap elements in a list Python?

To swap two list elements x and y by value, get the index of their first occurrences using the list. index(x) and list. index(y) methods and assign the result to variables i and j , respectively. Then apply the multiple assignment expression lst[i], lst[j] = lst[j], lst[i] to swap the elements.

What is the time complexity of list in Python?

The average time complexity of the in operator for lists is O(n) . It becomes slower when there are many elements. The execution time varies greatly depending on the position of the value to look for. It takes the longest time when its value is at the end or does not exist.

What is the time complexity of pop from a list in Python?

pop(k) has a time complexity of O(k). Be cautious when use a python list as a Queue structure. Use deque instead.


1 Answers

The answer depends on your implementation of python. I'm assuming you are interested in the default CPython implementation. From now one, i say "python" instead of "cpython".

A list in python is more or less for your purpose like an array in C.

deleting an element in it requires shifting all elements above it, and the same goes for insertion, so that these two operations are O(i) where i is the number of items after the item you deleted/inserted. Your first answer is O(1), so way better.

Your profiling was wrong, because this size of array is actually quite small, and your timing also takes into account the time to build the array. Try the following experiment: build an array of size 100000 once, and try 100000 times to swap two elements in it. You will see that the first code is at least 100 times faster than the second one (that's the figures i obtained on my computer), and it is of course the good way to swap elements in a python list.

like image 102
Emmanuel Jeandel Avatar answered Nov 09 '22 15:11

Emmanuel Jeandel