Улучшение производительности при рандомизации std :: list

Question

У меня есть std::list, который я в настоящее время рандомизировал, используя Shuffle Fisher-Yates (см. http://en.wikipedia.org/wiki/Fisher-Yates_shuffle). Подводя итог, мой код выполняет следующие шаги в этом списке:

1. Прокрутите каждый элемент list.
2. Поменяйте элемент со случайно выбранным элементом с текущей позиции вперед, включая его.

Поскольку списки не предоставляют случайный доступ, это означает, что я выполняю повторение по всему списку на шаге 1, и для каждого элемента, который я повторяю снова, в среднем более половины оставшихся элементов с этой точки дальше , Это серьезное узкое место в производительности моей программы, поэтому я хочу улучшить ее. По другим причинам мне нужно продолжать использовать list в качестве моего контейнера, но я рассматриваю возможность преобразования в vector в начале моей функции рандомизации, а затем обратно в list. Мои списки обычно содержат 300 - 400 элементов, поэтому я бы предположил, что стоимость конверсии между контейнерами будет стоить того, чтобы избежать чередования элементов последовательно.

Мой вопрос: это похоже на лучший способ оптимизации кода? Есть ли способ лучше?

Answer 1

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

vector<int> myVector(myList.size()); 
copy(myList.begin(), myList.end(), myVector.begin()); 
random_shuffle(myVector.begin(), myVector.end()); 
list<int> myListShuffled(myVector.begin(), myVector.end()); 

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

vector<int> myVector(myList.size()); 
int lastPos = 0; 
for(list<int>::iterator it = myList.begin(); it != myList.end(); it++, lastPos++) { 
    int insertPos = rand() % (lastPos + 1); 
    if (insertPos < lastPos) { 
     myVector[lastPos] = myVector[insertPos]; 
    } 

    myVector[insertPos] = *it; 
} 

list<int> myListShuffled(myVector.begin(), myVector.end()); 

Поскольку первая версия гораздо легче понять и гораздо менее подвержены ошибкам, это почти всегда предпочтительнее ... если, возможно, этот бит кода не критичен для вашей производительности (и вы подтвердили это с помощью измерения.)

EDIT: Кстати, поскольку вы смотрите статью Википедии, во втором примере кода используется «наивысший» вариант Fisher-Yates.