Vector vs Deque Время вставки

Я прочитал хороший эксперимент, сравнивающий, в частности, производительность вызова insert() как на vector, так и на контейнере deque. Результатом этого конкретного эксперимента (эксперимент 4) было то, что deque значительно превосходит эту операцию.Vector vs Deque Время вставки

Я выполнил свой собственный тест, используя короткую функцию сортировки, которую я написал, что я должен отметить, используя оператор [] вместе с другими функциями-членами и обнаружил совершенно разные результаты. Например, для вставки 100 000 элементов vector занял 24,88 секунды, а deque заняло 374,35 секунды.

Как я могу это объяснить? Я предполагаю, что это имеет какое-то отношение к моей функции сортировки, но мне нужны подробности!

Я использую g ++ 4.6 без оптимизации.

Вот программа:

#include <iostream> 
#include <vector> 
#include <deque> 
#include <cstdlib> 
#include <ctime> 

using namespace std; 

size_t InsertionIndex(vector<double>& vec, double toInsert) { 
    for (size_t i = 0; i < vec.size(); ++i) 
    if (toInsert < vec[i]) 
     return i; 
    return vec.size(); // return last index+1 if toInsert is largest yet                   
} 

size_t InsertionIndex(deque<double>& deq, double toInsert) { 
    for (size_t i = 0; i < deq.size(); ++i) 
    if (toInsert < deq[i]) 
     return i; 
    return deq.size(); // return last index+1 if toInsert is largest yet                   
} 

int main() { 
    vector<double> vec; 
    deque<double> deq; 

    size_t N = 100000; 

    clock_t tic = clock(); 
    for(int i = 0; i < N; ++i) { 
    double val = rand(); 
     vec.insert(vec.begin() + InsertionIndex(vec, val), val); 
    //  deq.insert(deq.begin() + InsertionIndex(deq, val), val);                   
    } 

    float total = (float)(clock() - tic)/CLOCKS_PER_SEC; 
    cout << total << endl; 
}

источник

2014-02-04 bcf

Сообщите нам.: 1) Какой компилятор вы используете и 2) Проверяете ли вы оптимизированную сборку или нет. – PaulMcKenzie

Просто добавил, что я использую g ++ без оптимизации, но я не уверен, как узнать, какую версию g ++ я использую. – bcf

g ++ -dumpversion – Brian

Особый случай, когда deque может быть намного быстрее, чем vector когда вы вставив в перед контейнера. В вашем случае вы вставляете в случайные местоположения, что фактически даст преимущество vector.

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

источник

2014-02-04 02:20:45

Хорошо, спасибо за это. Моя команда компилятора была просто 'g ++ filename.cpp'. Нужно ли добавлять что-нибудь, чтобы отключить отладку и какую оптимизацию использовать? Например. -O2? – bcf

@bcf: для gcc реализация по умолчанию не использует проверенные итераторы, поэтому достаточно нападать на оптимизатор up (-O2 или -O3). Но важная часть сравнения - это то, что Марк упоминает в первом абзаце. Преимущество deque - это вставки и удаления в * front * (что, кстати, упоминается в статье, которую вы связали) –

Ваш код выполняет сортировку вставки, которая является O (n^2). Итерация по deque происходит медленнее, чем итерация по vector.

Я подозреваю причину вы не видите тот же результат, посланная ссылка потому, что во время выполнения вашей программы преобладают петли в InsertionIndex не вызов deque::insert (или vector::insert

источник

2014-02-04 02:54:16 MarkB

Vector vs Deque Время вставки

ответ

Смежные вопросы