How Can I Make My Array Rotation More Efficient?

Question

How can I make my circular array rotation more efficient? I read in this thread about an excellent sorting algorithm, but it won't work for what I need because there are spaces at the end of the array that get sorted into the middle.

The rotation function needs to work for both left and right rotation. Not every space of the array will be filled.

void Quack::rotate(int r)
{
    if(r > 0) //if r is positive, rotate left
    {
        for(int i = 0; i < r; i++)
            items[(qBack + i) % qCapacity] = items[(qFront + i) % qCapacity];
            //move items in array
    }
    else if(r < 0) //if r is negative, rotate right
    {
        for(int i = 0; i < (r * -1); i++)
            items[(qFront - i - 1) % qCapacity] =
                items[(qBack - i - 1) % qCapacity];
            //move items in array
    }
    //if r = 0, nothing happens

    //rotate front and back by r
    qFront = (qFront + r) % qCapacity;
    qBack = (qBack + r) % qCapacity;
}

Not that this necessarily helps you (depends on the higher level problem you are trying to solve), but you could "rotate" an array by keeping a start offset, and just adjust the loops in your algorithms. Make them start reading at that offset, read to the end, then continue reading from the beginning again, until that offset. — Merlyn Morgan-Graham
– Merlyn Morgan-Graham, Commented Oct 30, 2011 at 1:21
There's a nice version of rotate done as three reverses: reverse the left bit, then the right bit, then the whole array. But this may or may not be faster. — Alan Stokes
– Alan Stokes, Commented Oct 30, 2011 at 20:25

Merlyn Morgan-Graham · Accepted Answer · 2011-10-30 01:29:30Z

1

I haven't used it, so I can't promise it will do everything you need. But you might want to look into simply replacing this function body with the std::rotate function.

It should already be well optimized, and will be much less likely to introduce bugs into your application.

http://www.sgi.com/tech/stl/rotate.html

If you want suggestions for optimization though, I recommend avoiding all modulo operations. They may require a divide, which is one of the most expensive operations you can perform on your processor. They are a convenient way to think about how to accomplish your goal, but could be very costly for your CPU to execute.

You can remove your modulo operators if you use two loops: one from the middle to the end, and the other from the beginning to the middle.

But if you can, see if you can avoid doing the rotation altogether. If you are careful you might be able to eliminate pointless full-array traversal/copy operations. See my comment on the OP for how to accomplish this.

edited Oct 30, 2011 at 1:29

answered Oct 30, 2011 at 1:23

Merlyn Morgan-Graham

59.4k16 gold badges131 silver badges189 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

TheBuzzSaw Over a year ago

That does not sound correct. I know that floating point division is a fairly expensive operation, but integer division (and modulus in particular) are fairly light calculations.

Merlyn Morgan-Graham Over a year ago

@TheBuzzSaw: Compared to just breaking up the loops correctly (which costs nothing to the processor)? No, they aren't light. If this is actually the bottleneck in the application (which is the only reason to optimize it), then this is exactly the type of optimization you'd want to make.

TheBuzzSaw Over a year ago

I was referring only to the modulus operator. I agree that breaking it up is faster regardless. I Googled around a bit. Processors have modulus-specific optimizations (ARM in particular). Just something to keep in mind.

Merlyn Morgan-Graham Over a year ago

@TheBuzzSaw: Good point, though he didn't specify which arch. Do you have a better optimization opportunity for him than "don't rotate at all, use the standard routine, or at least get rid of the modulo"? All of those I guarantee will make it at least marginally faster.

Collectives™ on Stack Overflow

How Can I Make My Array Rotation More Efficient?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related