list pop and insert are very slow in python

Question

I am working on a leetcode question 189. Rotate Array.

Problem statement: Given an array, rotate the array to the right by k steps, where k is non-negative. Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]

Following is my code. My understanding is that the time complexity is O(k), but it ends up being very low. Could you please shine some light on this and educate me?

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        while k:
            nums.insert(0,nums.pop())
            k -= 1

You might want to consider a different approach that doesn't modify the array on each step, but think about how you could reindex the array to be shifted like that. — AKX, Oct 29 '21 at 20:39
What do you mean by very slow? there isn't a lot here to cause real performance issues — Sayse, Oct 29 '21 at 20:39
Either way - lists in CPython are implemented as simple arrays of pointers, so a pop is simple, but an insert at 0 requires shifting everything to the right and setting the first entry. — AKX, Oct 29 '21 at 20:40
List is not ideal for this `insert(0)` (to the head) ops. Better to think other way for handling bigger list. — Daniel Hao, Oct 29 '21 at 20:41
@Sayse, my code took 3144 ms, other solutions take about 100 ms. — Albert G Lieu, Oct 29 '21 at 20:41
Of course, `.insert(0, x)` is *linear time*. So your algorithm will be O(K*N), where `K` is the magnitude of `k`, and N is the length of `nums`. i.e. it's polynomial time, when it can be done in linear time — juanpa.arrivillaga, Oct 29 '21 at 20:43
@AlbertGLieu *of course*. How could it not? But yeah, this is a fundamental performance characteristic here. — juanpa.arrivillaga, Oct 29 '21 at 20:45
@juanpa.arrivillaga, I don't understand how python implemented list, originally I thought it used a linked list kind of thing, think insert and pop only take O(1). I need to look up to make sure. But I am very likely to be wrong. Thank you very much. — Albert G Lieu, Oct 29 '21 at 20:48
@AlbertGLieu no, absolutely not. A linked list would be *disasterous* for typical use-cases, it is implemented as an Array List, this is why access is constant time, i.e. `mylist[0]` takes the same time as `mylist[10_000]` Typically, the only places you'd see a linked list as a default implementation is in a functional programming language, i.e. a "cons list". — juanpa.arrivillaga, Oct 29 '21 at 20:48
Does this answer your question? [Fastest algorithm for circle shift N sized array for M position](https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position) — sahasrara62, Oct 29 '21 at 21:24
@AlbertGLieu https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position/32698823#32698823 if you want to have better approach and solve the problem as it is asked ( basically idea is circular shift ) — sahasrara62, Oct 29 '21 at 21:26

Dani Mesejo · Accepted Answer · 2021-10-29T20:48:07.500

2

One approach is to use a deque rotate, as below

from collections import deque
from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        dnums = deque(nums)
        dnums.rotate(k)
        nums[:] = dnums


nums = [1,2,3,4,5,6,7]
Solution().rotate(nums, 3)
print(nums)

Output

[5, 6, 7, 1, 2, 3, 4]

From the documentation (emphasis mine):

Rotate the deque n steps to the right. If n is negative, rotate to the left. When the deque is not empty, rotating one step to the right is equivalent to d.appendleft(d.pop()), and rotating one step to the left is equivalent to d.append(d.popleft()).

The problem with inserting at the beginning of a list is that it is O(n), you have to shift all the elements. In a deque inserting at the beginning (appendleft) is O(1).

For more details about the time complexity of deque and list, see here

edited Oct 29 '21 at 20:48

answered Oct 29 '21 at 20:42

Dani Mesejo

61,499
6
49
76

2

That's one option, but I'm pretty sure there's a simple `nums[:] = [nums[(i + shift % ...` sort of approach to this too :-) – AKX Oct 29 '21 at 20:43
thanks Dani for the solution, I mainly want to understand why my code is so slow compared to others. Do you happen to know why. – Albert G Lieu Oct 29 '21 at 20:43
2

But that's no faster than the pop/append solution. – Tim Roberts Oct 29 '21 at 20:44
@TimRoberts why do you say? – juanpa.arrivillaga Oct 29 '21 at 20:45
1

@juanpa.arrivillaga The computational requirements are the same Allocate memory, copy the elements, add the new one. One is implicit, one is explicit, but the time should be the same. – Tim Roberts Oct 29 '21 at 20:54
@TimRoberts no, no it isn't. The problem is that in the OP's solution, you copy the entire underlying buffer *for each of the k iterations*. In the above, the copy is done once, up front, then the re-arranging is handled by an efficient, internal algorithim that is only O(K), so this algorith will only be O(N), whereas the OP's will be O(N*K). EDIT: perhaps what's missing is that deque is implemented a a linked list (sorta, actually, it's more of a "rope", since it's a doubly-linked list of array blocks) – juanpa.arrivillaga Oct 29 '21 at 20:58
@TimRoberts a form of this question is asked earlier in SO [fastest curclar shift](https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position/), which was also given as a hint in question in leetcode – sahasrara62 Oct 29 '21 at 21:28
1

You're right, I overlooked the "one at a time" vs "many at a time" difference in my quick glance. – Tim Roberts Oct 29 '21 at 21:35

score 2 · Answer 2 · answered Oct 29 '21 at 20:44

2

Deque is great DS for this. Alternatively, you can try this: This got accepted and ranked 88% in Python category. (about the same speed as deque)

[Note] the length of list is 10^5. It asks for in-place ops.

 def rotate(self, nums: List[int], k: int) -> None:
     """
     Do not return anything, modify nums in-place instead.
     """
     z = len(nums)
     k = k % z
        
     nums[:] = nums[z-k:] +nums[:z-k]

answered Oct 29 '21 at 20:44

Daniel Hao

4,922
3
10
23

Simple and pythonic. This is very informative. – William Zebrowski Oct 30 '21 at 21:37

score 0 · Answer 3 · answered Oct 29 '21 at 20:55

0

FYI, in the case you use numpy

import numpy as np

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3

print(np.roll(nums, k).tolist())

# Output:
[5, 6, 7, 1, 2, 3, 4]

answered Oct 29 '21 at 20:55

Corralien

109,409
8
28
52

sadly using numpy is not recommended in Leetcode – sahasrara62 Oct 29 '21 at 21:00

list pop and insert are very slow in python

3 Answers3