如何让阵列旋转更高效？

如何让我的圆形阵列旋转更高效？我在这thread中读到了一个很好的排序算法，但它不适用于我所需要的，因为在数组末尾有空格排列到中间。如何让阵列旋转更高效？

旋转功能需要适用于左旋和右旋。并非阵列中的每个空间都将被填充。

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

来源

2011-10-30 snazzy

这不一定能帮助你（取决于你试图解决的更高级别的问题），但是你可以通过保持一个起始偏移量来“旋转”一个数组，并且只需调整算法中的循环。让他们开始读取该偏移量，读到最后，然后再次从头开始读取，直到该偏移量。 –

有一个不错的版本的旋转完成三个反转：颠倒左边的位，然后右边的位，然后整个阵列。但这可能会或可能不会更快。 –

我没有使用它，所以我不能保证它会做你需要的一切。但是你可能想要简单地用std::rotate函数替换这个函数体。

它应该已经被很好地优化了，并且将很少可能在应用程序中引入错误。

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

如果你想为优化建议虽然，我建议避免所有的模运算。他们可能需要划分，这是您可以在处理器上执行的最昂贵的操作之一。它们是考虑如何实现您的目标的一种便捷方式，但可能会让您的CPU执行起来非常昂贵。

如果你使用两个循环，你可以删除你的模运算符：一个从中间到另一个，另一个从头到中。

但是，如果可以的话，看看你是否可以避免完全旋转。如果你小心，你可能会消除无意义的全数组遍历/复制操作。请参阅我对OP的评论，了解如何完成此操作。

来源

2011-10-30 01:23:59

这听起来不正确。我知道浮点除法是一个相当昂贵的操作，但整数除法（特别是模量）是相当轻的计算。 – TheBuzzSaw

@TheBuzzSaw：相比刚刚分解正确的循环（这对处理器没有任何损失）？不，他们并不轻。如果这实际上是应用程序中的瓶颈（这是优化它的唯一原因），那么这正是您想要进行的优化类型。 –

我只是指模运算符。我同意分解速度更快。我谷歌搜索了一下。处理器具有模数特定的优化（特别是ARM）。只是要记住。 – TheBuzzSaw

如何让阵列旋转更高效？

回答

相关问题