Discussion on: Is JavaScript's .shift() Method a Performance Boost?

View post

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.