如何使阵列旋转更加高效？

Question

如何使圆形阵列旋转更加高效？我在这个 线程 中读到了有关出色排序算法的内容，但它不适用于我需要什么，因为数组末尾有空格被排序到中间。

旋转功能需要同时适用于左旋转和右旋转。并非数组的每个空间都会被填充。

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;
}

Answer 1

我没有使用过它，所以我不能保证它能满足您所需的一切。但您可能想考虑简单地用 std::rotate 函数替换这个函数体。

它应该已经得到了很好的优化，并且不太可能在您的应用程序中引入错误。

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

如果您需要优化建议，我建议避免所有模运算。它们可能需要除法，这是您可以在处理器上执行的最昂贵的操作之一。它们是思考如何实现目标的便捷方法，但 CPU 的执行成本可能非常高。

如果使用两个循环，则可以删除模运算符：一个从中间到结束，另一个从开始到中间。

但如果可以的话，看看是否可以完全避免进行轮换。如果您小心的话，您也许能够消除无意义的全数组遍历/复制操作。请参阅我对 OP 的评论，了解如何实现这一目标。