Случайное замедление при введении элементов в случайном порядке в векторы

Question

EDIT: Я исправил вставку. Как Blastfurnace любезно упомянул, что вставка недействительна итераторами. Мне нужен цикл. Я считаю, что сравнивать производительность (см. Мой комментарий к ответу Blastfurnance). Мой код обновлен. У меня есть полностью аналогичный код для списка, просто с замененным списком. Однако с кодом я считаю, что список работает лучше, чем вектор, как для малых, так и для больших типов данных и даже для линейного поиска (если я удалю вставку). Согласно http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs и другим сайтам, которых не должно быть. Какие-нибудь подсказки, как это может быть?

Я беру курс по программированию математического программного обеспечения (экзамен в понедельник), и для этого я хотел бы представить график, который сравнивает производительность между случайной вставкой элементов в вектор и список. Однако, когда я тестирую код, я получаю случайное замедление. Например, у меня могло бы быть 2 итерации, когда вставлять 10 элементов случайным образом в вектор размером 500 занимает 0.01 секунды, а затем 3 одинаковых итерации, каждая из которых занимает примерно 12 секунд. Это мой код:

void AddRandomPlaceVector(vector<FillSize> &myContainer, int place) { 
    int i = 0; 

    vector<FillSize>::iterator iter = myContainer.begin(); 

    while (iter != myContainer.end()) 
    { 
     if (i == place) 
     { 
      FillSize myFill; 
      iter = myContainer.insert(iter, myFill); 
     } 
     else 
      ++iter; 

     ++i; 
    } 

    //cout << i << endl; 
} 

double testVector(int containerSize, int iterRand) 
{ 
    cout << endl; 
    cout << "Size: " << containerSize << endl << "Random inserts: " << iterRand << endl; 

    vector<FillSize> myContainer(containerSize); 
    boost::timer::auto_cpu_timer tid; 

    for (int i = 0; i != iterRand; i++) 
    { 
     double randNumber = (int)(myContainer.size()*((double)rand()/RAND_MAX)); 
     AddRandomPlaceVector(myContainer, randNumber); 
    } 

    double wallTime = tid.elapsed().wall/1e9; 

    cout << "New size: " << myContainer.size(); 

    return wallTime; 
} 

int main() 
{ 
    int testSize = 500; 
    int measurementIters = 20; 
    int numRand = 1000; 
    int repetionIters = 100; 


    ofstream tidOutput1_sum("VectorTid_8bit_sum.txt"); 
    ofstream tidOutput2_sum("ListTid_8bit_sum.txt"); 

    for (int i = 0; i != measurementIters; i++) 
    { 
     double time = 0; 

     for (int j = 0; j != repetionIters; j++) { 
      time += testVector((i+1)*testSize, numRand); 
     } 

     std::ostringstream strs; 
     strs << double(time/repetionIters); 
     tidOutput1_sum << ((i+1)*testSize) << "," << strs.str() << endl; 
    } 

    for (int i = 0; i != measurementIters; i++) 
    { 
     double time = 0; 

     for (int j = 0; j != repetionIters; j++) { 
      time += testList((i+1)*testSize, numRand); 
     } 

     std::ostringstream strs; 
     strs << double(time/repetionIters); 
     tidOutput2_sum << ((i+1)*testSize) << "," << strs.str() << endl; 
    } 
    return 0; 
} 

struct FillSize 
{ 
    double fill1; 
}; 

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

Я протестировал этот код на двух компьютерах сейчас, оба имеют одинаковые проблемы. Как это может быть? И можете ли вы помочь мне с исправлением, чтобы я мог его нарисовать и представить в понедельник? Возможно, добавление нескольких секунд ожидания между каждой итерацией поможет?

С наилучшими пожеланиями, Бьярке

Answer 1

Ваша AddRandomPlaceVector функция имеет серьезный недостаток. Использование insert() будет invalidate iterators, поэтому цикл for является неверным кодом.

Если вы знаете желаемую точку вставки, нет никаких причин для итерации по vector.

void AddRandomPlaceVector(vector<FillSize> &myContainer, int place) 
{ 
    FillSize myFill; 
    myContainer.insert(myContainer.begin() + place, myFill); 
}