Как сделать вращение массива более эффективным? - PullRequest
Новая
       5

Как сделать вращение массива более эффективным?

1 голос
/ 30 октября 2011

Как я могу сделать вращение моего кругового массива более эффективным?В этом потоке я читал об отличном алгоритме сортировки, но он не сработает для того, что мне нужно, потому что в конце массива есть пробелы, отсортированные по середине.

Функция вращения должна работать как для левого, так и для правого вращения.Не все пробелы в массиве будут заполнены. 

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

1 Ответ

1 голос
/ 30 октября 2011

Я не использовал его, поэтому не могу обещать, что он сделает все, что вам нужно.Но вы, возможно, захотите просто заменить тело этой функции на функцию std::rotate.

Она должна быть уже хорошо оптимизирована и с гораздо меньшей вероятностью будет содержать ошибки в вашем приложении.

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

Если вам нужны предложения по оптимизации, я рекомендую избегать всех операций по модулю.Они могут потребовать разделения, что является одной из самых дорогих операций, которые вы можете выполнять на вашем процессоре.Это удобный способ подумать о том, как достичь своей цели, но он может быть очень дорогим для выполнения вашего ЦП.

Вы можете удалить свои операторы по модулю, если используете два цикла: один от середины до концаи другой от начала до середины.

Но если вы можете, посмотрите, сможете ли вы вообще избежать вращения.Если вы будете осторожны, вы сможете устранить бессмысленные операции обхода / копирования полного массива.См. Мой комментарий к ОП, чтобы узнать, как этого добиться.

...