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

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

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

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

13.05.2012, 20:38. Просмотров 1639. Ответов 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;
}
Кто знает чем это объясняется, напишите пожалуйста.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 20:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Время доступа к элементам вектора. (C++):

Скорость доступа к элементам вектора - C++
Всем привет! Использую вектор и интеерсует вопрос скорости выбора элементов из него. У вектора есть метод vector.at(int index),...

Error C2039 при использовании методов доступа к элементам вектора - C++
# include &lt;iostream&gt; # include &lt;string&gt; # include &lt;fstream&gt; # include &lt;vector&gt; using namespace std; class Load ...

Обращение к элементам вектора - C++
Вопрос вот в чем. Есть следующий код: #include &lt;vector&gt; #include &lt;iostream&gt; int main() { std::vector&lt;int&gt; a(10, 1); ...

Обращение к элементам вектора - C++
как обратиться к N=43 строке вектора нумерация с 0 vector&lt;int&gt; myVector;

Как получить доступ к элементам вектора - C++
Нашел вот такой код. А вот как получить доступ к элементам вектора? FILE *ToWrite = fopen(&quot;C:\\result.txt&quot;, &quot;w+&quot;); list&lt;string&gt;...

Доступ к элементам вектора, который находится в map - C++
День добрый! Нужно ваше экспертное мнение. Я создаю map: std::map&lt;unsigned, std::vector&lt;int&gt;&gt; test_1 ; Затем я добавляю...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 21:00 #2
Актуально.Самому интересно. Ждём профессионалов
1
Avazart
Эксперт С++
7191 / 5365 / 280
Регистрация: 10.12.2010
Сообщений: 23,674
Записей в блоге: 17
13.05.2012, 21:04 #3
Время доступа к элементам вектора больше, чем больше размерность.
Этого по идее не должно быть в обыном векторе, в дугих многомерных случаях не знаю, сильно намудрили код
0
Toshkarik
1141 / 858 / 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 ли функция перегрузки [] или нет.
0
Avazart
Эксперт С++
7191 / 5365 / 280
Регистрация: 10.12.2010
Сообщений: 23,674
Записей в блоге: 17
13.05.2012, 21:29 #5
Toshkarik, наверное пробелы между скобками забыл поставить
C++
1
vector<vector<vector<int> > > v(n,vector<vector<int> >(n,n));
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
13.05.2012, 21:33 #6
Нет, их как раз я сразу перед компиляцией и расставил.

Добавлено через 3 минуты
На LWS так же.
0
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;
}
Вот тоже, только для двумерного случая.
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 10:04 #8
Попробуй откусить расширение стека и сделай массив поменьше, просто протестируй его побольше раз

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

Цитата Сообщение от Toshkarik Посмотреть сообщение
inline
В с++ это пустое ключевое слово, в подавляющем большинстве случаев оно никак не влияет на генерацию кода.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 11:19 #11
PhotonDT, Выложи инфо компилятора
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
14.05.2012, 17:54 #12
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 18:58 #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
Ну, мы друг друга не поняли. Этот флаг заставляет функции встраиваться, не спорю. Однако ключевое слово inline на встраивание никак не влияет(большинство компиляторов его просто игнорирует), это я и имел в виду.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 19:12 #14
Toshkarik,
diagon,
Спасибо, за inline etс для ускорения, пригодится. PhotonDT не до конца изложил суть проблемы...
Его цель -- написание курсовой и он сейчас занят исследованием скорости доступа к контейнерам, в частности к вектору.Но видимо из-за его компилятора случилось непредвиденное и ужасное, а противоречий в курсовой не должно быть =)
0
Avazart
Эксперт С++
7191 / 5365 / 280
Регистрация: 10.12.2010
Сообщений: 23,674
Записей в блоге: 17
14.05.2012, 19:19 #15
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2012, 19:19
Привет! Вот еще темы с ответами:

Структура и осуществление доступа к ее элементам - C++
Получить программную реализацию задачи обработки таблицы дан- ных. Таблица должна представлять собой массив элементов соответствую- ...

Использование #define для доступа к элементам класса - C++
Добрый день. Имеется класс вида: class Test { int key; int smth; } И я хочу сделать #define чтобы быстро получать...

Небольшая прога по методам доступа к элементам массива - C++
Смысл такой, имеется трехмерный массив A. Данные считываются с файла(тут все верно). Хотелось бы обращаться к элементам данного массива по...

Напишите цикл for для доступа к элементам массива в обратном порядке - C++
Правильно ли? #include &lt;iostream&gt; using namespace std; int main() { int size; cout &lt;&lt; &quot;Enter number: &quot;; cin &gt;&gt;...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.05.2012, 19:19
Ответ Создать тему
Опции темы

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