Annie Liao

Posted on Jun 13, 2020

JavaScript Shift Is JavaScript's .shift() Method a Performance Boost?

#discuss #javascript #algorithms

It's one thing to understand the concept of time/space complexity. It's another to apply the knowledge when solving algorithm puzzles. After reading the well-illustrated, beginner-friendly Grokking Algorithm, I thought I was fully prepared to tackle algorithm challenges using the big O notation.

I was wrong. This is what I often encounter during my HackerRank practices:

It is still challenging for me to come up with scalable solutions on the first try. Naturally, I would look up alternative solutions and try to emulate the solver's thought process.

Oftentimes my initial reaction would be "Wow, that's brilliant. Why didn't I think of that?"

But in this particular code challenge, I found a solution that looks similar to mine and is able to pass all test cases.

And that led me to learning runtime complexity of JavaScript array methods.

So, here's the challenge. It's a simple left rotation of an array:



Given an array (arr) and number of left rotations (d), 
returns the updated array.

For example:



rotateLeft([1, 2, 3, 4, 5], 4)
// elements in the array rotate 4 times:
// [2, 3, 4, 5, 1] -> [3, 4, 5, 1, 2] -> [4, 5, 1, 2, 3] -> [5, 1, 2, 3, 4] 
// returns [5, 1, 2, 3, 4]

Here's my initial solution, which passed 8 of the 10 test cases:



function rotateLeft(arr, d) {
    for (let i = 0; i < d; i++) {
    // 1. create a copy of arr starting at index 1, save to a variable (tempArr)
    // 2. push arr[0] to tempArr
    // 3. Now, tempArr has the updated order, so we reassign arr to tempArr
        let tempArr = arr.slice(1)
        tempArr.push(arr[0])
        arr = tempArr
    }
    return arr
}

And here's the solution I found that passed all test cases:



function rotateLeft(arr, d) {
    let tempArr = arr.slice()
    for (let i = 0; i < d; i++) {
        let firstItem = tempArr.shift()
        tempArr.push(firstItem)
    }
    return tempArr
}

In my solution, I created a new array via .slice() method in each iteration, while the other solution code only did it once outside the for loop.

I also found an explanation on Stack Overflow that compares runtime complexity of some array methods.

An engineer friend further explained that adding arrays together is an O(n + m) complexity: Arrays are fixed in size under the surface, so when you add them together, you are actually creating a new array big enough to hold them. And doing it for each iteration results in an O(n + m)^2 complexity.

Despite the two resources above, I am still baffled by the reason behind using .shift() that leads to an optimized solution.

Would anyone like to take a stab at explaining it?

Top comments (17)

Mike Talbot ⭐ • Jun 13 '20

Hey just to point out that shift itself is a bit of a pain doing it frequently - that's because a shift "might" have to move all of the elements in the array (it's not allocating fortunately) - it depends on the actual engine implementation - but it's likely.

push and pop are very fast operations because they only change the length of the array, unshift and shift have to move all of the items in the array (because the operate at the beginning). So depending on what you are doing it might be wise to reverse and array and operate at the end - really would have to be a lot of operations though.

In the case of a rotate you can use the fact that .splice returns the items it removes so rotateLeft to me looks like:

    function rotateLeft(array, n) {
      n = n % array.length
      return array.push(...array.splice(0, n))
    }

Effectively push on the end the items you removed from the front. The cost of this is an array the size of the items you removed. But no loop.

Annie Liao • Jun 14 '20

Thanks Mike for pointing out the potential costly operation of shift -- I read somewhere that also compared shift with push and pop, but your explanation makes more sense to me. And yes, using splice first and adding the specific items to the array via spread operator does look more efficient. Really appreciate your help! :)

Mike Talbot ⭐ • Jun 14 '20

Yeah we can do it without spread - but now it looks nicer in ES6 :)

    function rotateLeft(array, n) {
      n = n % array.length
      return array.push.apply(array, array.splice(0, n))
    }

lionel-rowe • Jul 8 '20 • Edited

It looks like you could get better perf (at least for long arrays) using Array#concat without the spread operator:

jsperf.com/concat-vs-spreader

Also remember that Array#push returns the ~~pushed item~~ new length of the array, not the array 😉

Mike Talbot ⭐ • Jul 8 '20

You're right, should have a , array at the end I guess or a separate line

hidden_dude • Jun 14 '20 • Edited

What's wrong with the obvious solution:


function rot(a) {
    let last = a[0]
    for (let i = 0; i < a.length; i++) {
        let next = (i+1) % a.length
        a[i] = a[next]
    }
   a[a.length-1] = last
   return a;
}

This is a straightforward O(n) solution.
Slice(), push() and all that are nice.. but won't a for loop do better in this case? (to avoid allocation issues)

Annie Liao • Jun 14 '20

Nothing wrong, it just wasn't on top of my head when I first approached the problem, especially applying the modulo operator, which was not an obvious/natural thought process for me. And somehow I didn't find that solution during my search. So thanks so much for sharing. Adding to my notes as we speak :)

SavagePixie • Jun 14 '20

Well, your proposed solution only shifts the elements one place, while the challenge was to create a function that shifts them an undetermined number of places.

hidden_dude • Jun 14 '20

just change:

let next = (i+1) % a.length

let next = (i+offset) % a.length

Where offset is the number of spaces you want to shift.

Shahnawaz Ansari • Jan 13 '22

Your algorithm works for only 1 place shift, even with the edit you provided.

Valeri • Jun 13 '20

Hello, Annie!
It is not objective to compare how slice is used between the two solutions.
In your solution, you are copying almost the whole array (n-1) in every iteration. In the 10/10 solution the array is copied so that there are no side effects on the input parameter.
The shift operation is operating on the array, not copying, so there is your performance difference.

Annie Liao • Jun 14 '20

Ah, I see. Thanks for the crisp explainer, Valeri!

Josh Cheek • Jun 14 '20

It's got to be that slice method, it's going to allocate a new array, and that's going to be really expensive. If you're allowed to modify the input, then you should be able to do it really fast by keeping track of two indexes, one to copy from and another to copy to. If performance is important, then it's probably wise to do it like this, as it's unclear how changing the size of the array will affect performance. As you noted, memory is allocated in chunks of a given size, so to change the size of the array, it may need to allocate new memory and copy it over. Could also vary across JS implementations, I'm not sure if the specification dictates this or not. Anyway, have a link to the problem? I want to try it now!

Annie Liao • Jun 15 '20

Thanks Josh! Sure, here's the leftRotate challenge on HackerRank.

Josh Cheek • Jun 17 '20

So I was a little bit wrong. Keeping track of two indexes doesn't work unless you also keep an array of the d items that will get overwritten. And then at that point, it's probably worse than arr.push(arr.shift()). However, because they verify the result by having you write it to a file, you can still optimize like I was thinking (basically, you don't have to rotate at all, you can just start printing the numbers from the offset, and then loop around to the beginning (I cleaned it up a bit, their template was really verbose which made it difficult to follow):

const fs  = require('fs')
const out = fs.createWriteStream(process.env.OUTPUT_PATH)

let input = '';
process.stdin.on('data', inputStdin => input += inputStdin)

process.stdin.on('end', function() {
    let [[n, d], a] = input.split('\n').map(str => str.split(' '))
    while(n--)
      out.write(`${a[d++%a.length]} `)
})

It's not immediately clear that this will be more performant, but looking at the docs, it seems like it will be. If it were actually doing multiple file writes, then that would be expensive, and it might be better to rotate the array and join it into a single string to be written. But the docs say it should buffer the writes, so this is probably similar to what I had in mind. That said, I'm not confident it will be faster without benchmarking, as joining the array may avoid the allocation of the string with the space on the end of it.

Annie Liao • Jun 17 '20

Interesting. I always skipped the file writes and jumped to the function instructed. Not sure if this is what the challenge intended, but it's cool to see we can change input like that, as I'm still a NodeJS newbie. Thanks for taking a deep dive into this, Josh.

Shahnawaz Ansari • Jan 13 '22 • Edited

For rotating an array of length n by k places, the trick is to

reverse the whole array first,
reverse the first n - k elements,
and then reverse the last k elements

function reverse(arr, start, end) {
    for (; start < end; start++, end--) {
        let temp = arr[start]
        arr[start] = arr[end]
        arr[end] = temp
    }
}

function rotateLeft(arr, k) {
    let n = arr.length
    reverse(arr, 0, n - 1)
    reverse(arr, 0, n - k - 1)
    reverse(arr, n - k, n - 1)
}

View full discussion (17 comments)

DEV Community

JavaScript Shift Is JavaScript's .shift() Method a Performance Boost?

Top comments (17)

Read next

Building a Kanban Board with Next.js,Vercel AI and Tolgee

Image Reveal Animation with HTML, CSS, and GSAP

Unlock Rich Landmark Data with the Landmark API: Features, Usage, and More

Simplifying String Validation in Go: Introducing validatorgo