Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > vector vs deque

Автор: kokorins 22.8.2008, 15:50

Добрый день.
Необходима следующая реализация:

Код


vector<double> val(5)//Длина в принципе фиксированная
while(очень много раз)
{
    for (int i=val.size()-1; i>0; --i) //сдвигаем элементы на один
    {
        val[i]=val[i-1];
    }
    val[0]=somefunc(val);
    someuse(val);
}

Подумалось, что можно заменить данный код следующим:

Код


deque<double> dal(5)//Длина в принципе фиксированная
while(очень много раз)
{
    dal.pop_back();
    dal.push_front(somefunc(dal));;
    someuse(val);
}

если само добавление в начало отрабатывает быстро, то очень долгим оказывается работа [] в deque. Поэтому последний код оказался значительно хуже. В разы хуже.
Далее появилась версия использовать следующий подход:

Код


vector<double> val(5)//Длина в принципе фиксированная
while(очень много раз)
{
    copy(val.rbegin()+1,val.rend(),val.rbegin());
    val[0]=somefunc(val);
    someuse(val);
}

Который оказался хуже первого варианта где-то в 2 раза.
Может кто-нибудь подскажет, почему deque, который по идее должен работать быстрее,так как не требует копирования всех элементов и который имеет констаннтное время доступа по [] требует значительно больше времени.
Заранее благодарен.

Автор: bsa 22.8.2008, 15:58

А кто тебе гарантировал, что время исполнения operator[] у deque будет таким же, как и у vector? В документации сказано, что оно константно.
Я бы тебе рекомендовал использовать queue... Очередь больше подходит для твоих целей.

Автор: kokorins 22.8.2008, 16:31

Цитата

А кто тебе гарантировал, что время исполнения operator[] у deque будет таким же, как и у vector? В документации сказано, что оно константно.

Никто. Собственно в этой константе и хочется разобраться. У меня по прикидке разница в десятки раз по скорости.

Цитата

Я бы тебе рекомендовал использовать queue... Очередь больше подходит для твоих целей.

Не подходит, нужен random access к элементам.

В качестве примера, вот такой вот бессмысленный код:

Код


#include <ctime>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
void assignSome(double val, double&a)
{
    a=val;
}
int main() {
    long length = 10000000;
    vector<double> val(5);
    deque<double> dal(5);
    double a;
    clock_t start=clock();
    for (long iter = 0; iter<length; ++iter) {
        for (int i=val.size()-1; i>0; --i) {
            val[i]=val[i-1];
        }
        val[0]=0;
        for (size_t i=0; i<val.size(); ++i) {
            assignSome(val[i],a);
        }
    }
    std::cout<<"vector:"<<clock()-start<<endl;
    start=clock();
    for (long iter = 0; iter<length; ++iter) {
        copy(val.rbegin()+1,val.rend(),val.rbegin());
        val[0]=0;
        for (size_t i=0; i<val.size(); ++i) {
            assignSome(val[i],a);
        }
    }
    std::cout<<"vector2:"<<clock()-start<<endl;
    start = clock();
    for (long iter = 0; iter<length; ++iter) {
        dal.pop_back();
        dal.push_front(0);
        for (size_t i=0; i<dal.size(); ++i) {
            assignSome(dal[i],a);
        }
    }
    std::cout<<"deque:"<<clock()-start<<endl;
    return 0;
}

На выходе получается следующее
vector:93
vector2:235
deque:672

Почему vector2 и deque ведут себя настолько плохо?

Автор: Lazin 22.8.2008, 19:38

Цитата(kokorins @ 22.8.2008, 15:50

)

ожет кто-нибудь подскажет, почему deque, который по идее должен работать быстрее,так как не требует копирования всех элементов и который имеет констаннтное время доступа по [] требует значительно больше времени.

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

Добавлено @ 19:44
вот здесь

Цитата(kokorins @ 22.8.2008, 16:31

)

Код


        for (size_t i=0; i<dal.size(); ++i) {
            assignSome(dal[i],a);
        }

случайный доступ совсем не нужен, можно использовать банальный std::copy, какой алгоритм нужно реализовать?

Автор: maxim1000 23.8.2008, 10:31

ну если уж использовать вектор, то сдвигать никакого смысла нету
раз количество элементов константно, то можно просто представить вектор в виде циклического буфера, доступ, к которому будет в виде val[(i+shift)%val.size()], тогда операция pop_back/push_front будет простым перезаписыванием элемента и увеличением shift

Автор: Ln78 23.8.2008, 11:22

Иногда, когда требуется отдавать куда-то именно последовательность чисел, можно воспользоваться модификацией варианта, описанного maxim1000: выделить памяти, например, в 2 раза больше, чем нужно, и новое число - дописывание в конец, а когда дойдём до конца - перезапись. Т.е. здесь перезапись для массива из N элементов делается в N раз реже. Оформляется это в виде класса, инкапсулирующего все тонкости реализации.