Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
#1

Время доступа к элементам вектора. - C++

13.05.2012, 20:38. Просмотров 1625. Ответов 29
Метки нет (Все метки)

Суть проблемы в том, что я не могу объяснить такое расхождение во времени доступа к элементам динамического, статического массивов и вектора. Время доступа к элементам вектора больше, чем больше размерность. К одномерному в среднем на 50-100мс(1000000 элементов). К двумерному в среднем на 200мс.(1000x1000). К трехмерному (100х100х100) в среднем на 250мс.(это разница во времени между доступом к статич. и динамич. массивам и вектору) При этом учитывая, что скорость доступа к эл.статич. и динамич. массивов примерно равны.
Вот код, который я использовал для трехмерных структур:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<fstream>
#include<vector>
#include<time.h>
#pragma comment(linker, "/STACK:1000000000")
#define forn(i,n) for(int i=0;i<n;i++)
const int n=100;
using namespace std;
int main()
{
    setlocale(LC_ALL,"Russian");
    fstream f,g;
    f.open("out.txt",fstream::out);
    g.open("time.txt",fstream::app);
    clock_t clock();
    int aT1,aT2,dT1,dT2,vT1,vT2,x;
    vector<vector<vector<int>>> v(n,vector<vector<int>>(n,n));
    int aa[n][n][n];
    int ***dda=new int**[n];
    forn(i,n)
        dda[i]=new int*[n];
    forn(i,n)
        forn(p,n)
        dda[i][p]=new int[n];
    forn(i,n)
        forn(p,n)
            forn(j,n)
    {
        x=rand()%100+1;
        aa[i][p][j]=x;
        dda[i][p][j]=x;
        v[i][p][j]=x;
    }
    aT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<aa[i][p][j];
    aT2=clock();
    dT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<dda[i][p][j];
    dT2=clock();
    forn(i,n)
        delete[]dda[i];
    delete[]dda;
    vT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<v[i][p][j];
    vT2=clock();
    g<<aT2-aT1<<endl;
    g<<dT2-dT1<<endl;
    g<<vT2-vT1;
    g.close();
    g.open("time.txt",fstream::in);
    int k1=0,k2=0,k3=0;
    float t1=0,t2=0,t3=0;
    while(!g.eof())
    {
        g>>x;
        t1+=x;
        k1++;
        g>>x;
        t2+=x;
        k2++;
        g>>x;
        t3+=x;
        k3++;
    }
    g.close();
    g.open("time.txt",fstream::app);
    g<<endl;
    t1/=k1;
    t2/=k2;
    t3/=k3;
    cout<<aT2-aT1<<" это последнее приблизительное время доступа к элементам двумерного статического массива"<<endl;
    cout<<dT2-dT1<<" это последнее приблизительное время доступа к элементам двумерного динамического массива"<<endl;
    cout<<vT2-vT1<<" это последнее приблизительное время доступа к элементам двумерного вектора"<<endl<<endl;
    cout<<t1<<" это среднее время доступа к элементам статического массива"<<endl;
    cout<<t2<<" это среднее время доступа к элементам динамического массива"<<endl;
    cout<<t3<<" это среднее время доступа к элементам вектора"<<endl;
    system("PAUSE");
    return 0;
}
Кто знает чем это объясняется, напишите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 20:38     Время доступа к элементам вектора.
Посмотрите здесь:
C++ Скорость доступа к элементам вектора
Error C2039 при использовании методов доступа к элементам вектора C++
C++ Обращение к элементам вектора
C++ Обращение к элементам вектора
C++ Как получить доступ к элементам вектора
C++ Доступ к элементам вектора, который находится в map
C++ Структура и осуществление доступа к ее элементам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 21:00     Время доступа к элементам вектора. #2
Актуально.Самому интересно. Ждём профессионалов
Avazart
Эксперт С++
7121 / 5298 / 273
Регистрация: 10.12.2010
Сообщений: 23,444
Записей в блоге: 17
13.05.2012, 21:04     Время доступа к элементам вектора. #3
Время доступа к элементам вектора больше, чем больше размерность.
Этого по идее не должно быть в обыном векторе, в дугих многомерных случаях не знаю, сильно намудрили код
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
13.05.2012, 21:19     Время доступа к элементам вектора. #4
У меня данный код не компилируется. Ругается на объявление вектора:
C++
1
2
3
4
5
6
e:\programming\mingw\bin\../lib/gcc/x86_64-w64-mingw32/4.7.0/include/c++/bits/stl_vector.h:393:4:   required from 'std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = int; _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<int> >]'
main.cpp:38:75:   required from here
e:\programming\mingw\bin\../lib/gcc/x86_64-w64-mingw32/4.7.0/include/c++/bits/stl_vector.h:1155:4: error: no matching function for call to 'std::vector<std::vector<int> >::_M_fill_initialize(std::vector<std::vector<int> >::size_type, int&)'
e:\programming\mingw\bin\../lib/gcc/x86_64-w64-mingw32/4.7.0/include/c++/bits/stl_vector.h:1155:4: note: candidate is:
e:\programming\mingw\bin\../lib/gcc/x86_64-w64-mingw32/4.7.0/include/c++/bits/stl_vector.h:1197:7: note: void std::vector<_Tp, _Alloc>::_M_fill_initialize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]
e:\programming\mingw\bin\../lib/gcc/x86_64-w64-mingw32/4.7.0/include/c++/bits/stl_vector.h:1197:7: note:   no known conversion for argument 2 from 'int' to 'const value_type& {aka const std::vector<int>&}'
Добавлено через 3 минуты
Могу предположить, что компилировалось это дело без флага, включающего inline-функции. При до ступе к элементам вектора вызывается функция, которая и возвращает значение элемента. Правда я не совсем уверен, inline ли функция перегрузки [] или нет.
Avazart
Эксперт С++
7121 / 5298 / 273
Регистрация: 10.12.2010
Сообщений: 23,444
Записей в блоге: 17
13.05.2012, 21:29     Время доступа к элементам вектора. #5
Toshkarik, наверное пробелы между скобками забыл поставить
C++
1
vector<vector<vector<int> > > v(n,vector<vector<int> >(n,n));
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
13.05.2012, 21:33     Время доступа к элементам вектора. #6
Нет, их как раз я сразу перед компиляцией и расставил.

Добавлено через 3 минуты
На LWS так же.
PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
14.05.2012, 09:42  [ТС]     Время доступа к элементам вектора. #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<fstream>
#include<vector>
#include<time.h>
#pragma comment(linker, "/STACK:1000000000")
#define forn(i,n) for(int i=0;i<n;i++)
const int n=1000;
using namespace std;
int main()
{
    setlocale(LC_ALL,"Russian");
    fstream f,g;
    f.open("out.txt",fstream::out);
    g.open("time.txt",fstream::app);
    clock_t clock();
    srand ( time(NULL) );
    int aT1,aT2,dT1,dT2,vT1,vT2,x;
    vector<vector<int>> v(n,vector<int>(n));
    int aa[n][n];
    int **dda=new int*[n];
    forn(i,n)
        dda[i]=new int[n];
    forn(i,n)
        forn(p,n)
    {
        x=rand()%100+1;
        aa[i][p]=x;
        dda[i][p]=x;
        v[i][p]=x;
    }
    aT1=clock();
    forn(i,n)
        forn(p,n)
        f<<aa[i][p];
    aT2=clock();
    dT1=clock();
    forn(i,n)
        forn(p,n)
        f<<dda[i][p];
    dT2=clock();
    forn(i,n)
        delete[]dda[i];
    delete[]dda;
    vT1=clock();
    forn(i,n)
        forn(p,n)
        f<<v[i][p];
    vT2=clock();
    g<<aT2-aT1<<endl;
    g<<dT2-dT1<<endl;
    g<<vT2-vT1;
    g.close();
    g.open("time.txt",fstream::in);
    int k1=0,k2=0,k3=0;
    float t1=0,t2=0,t3=0;
    while(!g.eof())
    {
        g>>x;
        t1+=x;
        k1++;
        g>>x;
        t2+=x;
        k2++;
        g>>x;
        t3+=x;
        k3++;
    }
    g.close();
    g.open("time.txt",fstream::app);
    g<<endl;
    t1/=k1;
    t2/=k2;
    t3/=k3;
    cout<<aT2-aT1<<" это последнее приблизительное время доступа к элементам двумерного статического массива"<<endl;
    cout<<dT2-dT1<<" это последнее приблизительное время доступа к элементам двумерного динамического массива"<<endl;
    cout<<vT2-vT1<<" это последнее приблизительное время доступа к элементам двумерного вектора"<<endl<<endl;
    cout<<t1<<" это среднее время доступа к элементам статического массива"<<endl;
    cout<<t2<<" это среднее время доступа к элементам динамического массива"<<endl;
    cout<<t3<<" это среднее время доступа к элементам вектора"<<endl;
    system("PAUSE");
    return 0;
}
Вот тоже, только для двумерного случая.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 10:04     Время доступа к элементам вектора. #8
Попробуй откусить расширение стека и сделай массив поменьше, просто протестируй его побольше раз

Добавлено через 1 минуту
И засекай через #include "windows.h" int t=GetTickCount(); ...... time=GetTickCount()-t;
PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
14.05.2012, 10:17  [ТС]     Время доступа к элементам вектора. #9
Нет, дело не в этом, на тесте с размером в 50x50x50 разница ~50мс.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 10:50     Время доступа к элементам вектора. #10
Обращение к элементу одинаково во всех трех случаях(если компилятор более менее вменяемый, и не пихает вызов функции для каждого обращения).
Еще возможна ситуация, когда компилятор проверяет выход за границы массива, это тоже будет тормозить обращение.

Цитата Сообщение от Toshkarik Посмотреть сообщение
inline
В с++ это пустое ключевое слово, в подавляющем большинстве случаев оно никак не влияет на генерацию кода.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 11:19     Время доступа к элементам вектора. #11
PhotonDT, Выложи инфо компилятора
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
14.05.2012, 17:54     Время доступа к элементам вектора. #12
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 18:58     Время доступа к элементам вектора. #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
Ну, мы друг друга не поняли. Этот флаг заставляет функции встраиваться, не спорю. Однако ключевое слово inline на встраивание никак не влияет(большинство компиляторов его просто игнорирует), это я и имел в виду.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 19:12     Время доступа к элементам вектора. #14
Toshkarik,
diagon,
Спасибо, за inline etс для ускорения, пригодится. PhotonDT не до конца изложил суть проблемы...
Его цель -- написание курсовой и он сейчас занят исследованием скорости доступа к контейнерам, в частности к вектору.Но видимо из-за его компилятора случилось непредвиденное и ужасное, а противоречий в курсовой не должно быть =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2012, 19:19     Время доступа к элементам вектора.
Еще ссылки по теме:
C++ Использование #define для доступа к элементам класса
C++ Небольшая прога по методам доступа к элементам массива
C++ friend функции не имеют доступа к private элементам класса, почему?
C++ Нет доступа до вектора класса

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Avazart
Эксперт С++
7121 / 5298 / 273
Регистрация: 10.12.2010
Сообщений: 23,444
Записей в блоге: 17
14.05.2012, 19:19     Время доступа к элементам вектора. #15
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
Yandex
Объявления
14.05.2012, 19:19     Время доступа к элементам вектора.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru