CODEWITHSUNDEEP
pythonarraysalgorithmslice
jeremy radcliff
jeremy radcliff

Reputation: 1109

Why is slicing much faster than "manual" assignment?

I was working on an array rotation algorithm, where you rotate an array left by d steps of rotation.

I figured that slicing was a high level abstraction that would be much slower in reality than manually assigning each value in the array to a new location in the rotated array.

It turns out slicing is almost 40 times faster. Why is that?

Here is the code for comparison:

def rot_left_manual(a, d):
    a_length = len(a)
    rot_arr = [0] * a_length
    for i in range(a_length):
        rot_arr[(i-d) % a_length] = a[i]
    return rot_arr


def rot_left_slice(a, d):
    i = d % len(a)
    b = a[i:]
    b += (a[:i])
    return b

I'm using %timeit in Jupyter notebooks to time function speed

Upvotes: 0

Views: 677

Answers (1)

tdelaney
tdelaney

Reputation: 77337

Python's binary operations are relatively expensive. Looking at rot_arr[(i-d) % a_length] = a[i] for every execution of the loop

  • load rot_arr, i, d, a_length and a
  • call i.__sub__() and create intermediate object
  • call intermed.__mod__() and create intermediate object
  • call rot_arr.__setitem__, decrementing and potentially freeing existing obj

With slicing, almost all of the work is done in the list's slice method (implemented in C) which can optimize most of the moves with many fewer calculations and avoiding the expense of looking up or creating all of those python objects.

Upvotes: 1

Related Questions