Array.rotate! can be faster

Learning Resources
1

For my use case the time difference adds up.

I noticed that this is slower: val += ary[0]; ary.rotate!(1)

than this: inc = ary.shift; val += inc; ary << inc

I looked at the code for rotate! and it does allot of buffer copying.

2

Ah, yes. It seems that if you rotate by 1 then you just need space for a single item. Right now self[...] is used which creates a duplicate array.

1 Like
3

In fact it seems you can implement rotate without allocating any memory at all! At least looking at Ruby’s source code. Ruby is amazing, so many cool algorithms!

So for example if you want to rotate by 2 places this:

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

then you first rotate (always in-place) the entire thing:

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

then you rotate the first 4 elements:

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

then you rotate the last 2 elements:

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

Done! No memory allocations at all. And it seems this is applicable for any n.

I’ll try to send a PR later.

2 Likes
4

Hmm… so rotating like that in place, at least for big arrays, seems to be slower, though you avoid allocating memory.

1 Like
5

@jzakia This may or may not be helpful, depending on what you are actually trying to accomplish, but if you do a lot of rotating perhaps a Deque would be a better fit than an array?