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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
PhotonDT
 Аватар для PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
13.05.2012, 20:38     Время доступа к элементам вектора. #1
Суть проблемы в том, что я не могу объяснить такое расхождение во времени доступа к элементам динамического, статического массивов и вектора. Время доступа к элементам вектора больше, чем больше размерность. К одномерному в среднем на 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;
}
Кто знает чем это объясняется, напишите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 21:00     Время доступа к элементам вектора. #2
Актуально.Самому интересно. Ждём профессионалов
Avazart
 Аватар для Avazart
6893 / 5133 / 250
Регистрация: 10.12.2010
Сообщений: 22,560
Записей в блоге: 17
13.05.2012, 21:04     Время доступа к элементам вектора. #3
Время доступа к элементам вектора больше, чем больше размерность.
Этого по идее не должно быть в обыном векторе, в дугих многомерных случаях не знаю, сильно намудрили код
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для Avazart
6893 / 5133 / 250
Регистрация: 10.12.2010
Сообщений: 22,560
Записей в блоге: 17
13.05.2012, 21:29     Время доступа к элементам вектора. #5
Toshkarik, наверное пробелы между скобками забыл поставить
C++
1
vector<vector<vector<int> > > v(n,vector<vector<int> >(n,n));
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
13.05.2012, 21:33     Время доступа к элементам вектора. #6
Нет, их как раз я сразу перед компиляцией и расставил.

Добавлено через 3 минуты
На LWS так же.
PhotonDT
 Аватар для 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
 Аватар для 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
 Аватар для PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
14.05.2012, 10:17  [ТС]     Время доступа к элементам вектора. #9
Нет, дело не в этом, на тесте с размером в 50x50x50 разница ~50мс.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 10:50     Время доступа к элементам вектора. #10
Обращение к элементу одинаково во всех трех случаях(если компилятор более менее вменяемый, и не пихает вызов функции для каждого обращения).
Еще возможна ситуация, когда компилятор проверяет выход за границы массива, это тоже будет тормозить обращение.

Цитата Сообщение от Toshkarik Посмотреть сообщение
inline
В с++ это пустое ключевое слово, в подавляющем большинстве случаев оно никак не влияет на генерацию кода.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 11:19     Время доступа к элементам вектора. #11
PhotonDT, Выложи инфо компилятора
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
14.05.2012, 17:54     Время доступа к элементам вектора. #12
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 18:58     Время доступа к элементам вектора. #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
Ну, мы друг друга не поняли. Этот флаг заставляет функции встраиваться, не спорю. Однако ключевое слово inline на встраивание никак не влияет(большинство компиляторов его просто игнорирует), это я и имел в виду.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 19:12     Время доступа к элементам вектора. #14
Toshkarik,
diagon,
Спасибо, за inline etс для ускорения, пригодится. PhotonDT не до конца изложил суть проблемы...
Его цель -- написание курсовой и он сейчас занят исследованием скорости доступа к контейнерам, в частности к вектору.Но видимо из-за его компилятора случилось непредвиденное и ужасное, а противоречий в курсовой не должно быть =)
Avazart
 Аватар для Avazart
6893 / 5133 / 250
Регистрация: 10.12.2010
Сообщений: 22,560
Записей в блоге: 17
14.05.2012, 19:19     Время доступа к элементам вектора. #15
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
14.05.2012, 19:25     Время доступа к элементам вектора. #16
Цитата Сообщение от diagon Посмотреть сообщение
inline на встраивание никак не влияет
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение. В GCC все мелкие функции в STL, да и не только STL, помечены как inline, не зря ведь. Просто по умолчанию, почему то, встраивание начинается работать только при O3, или явном задании флага. А так да, все inline просто игнорируются.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 19:29     Время доступа к элементам вектора. #17
Цитата Сообщение от Toshkarik Посмотреть сообщение
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение.
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline. Причем для остальных функций он делает то же самое, т.е. встраивает функцию, если это выгодно, даже если она не помечена как inline.
С register и const ситуация чуть сложнее, но в общем случае они также не влияют на оптимизацию.
P.S. я это не сам придумал, можете у Саттера поподробнее прочитать =)
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
14.05.2012, 19:37     Время доступа к элементам вектора. #18
Цитата Сообщение от diagon Посмотреть сообщение
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline.
Я это и имел ввиду словом "пытается".

Не по теме:

Ну с const и register совсем отдельная история.

Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 20:37     Время доступа к элементам вектора. #19
Цитата Сообщение от Avazart Посмотреть сообщение
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
А мы что делаем? одномерный случай мы включаем в рассмотрение, охватить весь объём мы можем, пробелма в опыте и знаниях о контейнерах и др. массивов. Вообще, жалко, что нельзя постить в экспертах =(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2012, 20:52     Время доступа к элементам вектора.
Еще ссылки по теме:

C++ Как получить доступ к элементам вектора
C++ Использование #define для доступа к элементам класса

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

Или воспользуйтесь поиском по форуму:
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
14.05.2012, 20:52     Время доступа к элементам вектора. #20
да сперва одномерный случай и стоит рассмотреть.
вектор устроен примерно так:
struct Vector
{
int* ptr; //указатель на динамически выделенный массив.
};
разница между просто обращением по указателю и обращением через вектор может быть из-за одного косвенного обращения:
ptr[index] vs this->ptr[index]
В остальном от размера вектора не должно зависить. по крайней мере если с увеличением размера вектора и ростет время доступа к дальним элементам, то она так же должна рости и при обращении к элементу через простой динамический массив. В общем разница между вектором и динамически выделенным массивам должна быть из-за одного косвенного обращения. причем это значение постоянное и от размера вектора не зависит.
А вот скорость доступа к ячейке уже может начинать зависить, потому что в игру вступают всякие кеши процессора, и прочая низкоуровневая хренотень, детали которой я не знаю.
так же разница между доступом к статическому и динамическому массивам может быть из-за того, что они в разной памяти находятся. доступ к стеку вроде быстрее. хотя хз. в кногомерных массивах так же из-за переключения страниц памяти время доступа к ячейкам может становится неожиданно долгим.
Yandex
Объявления
14.05.2012, 20:52     Время доступа к элементам вектора.
Ответ Создать тему
Опции темы

Текущее время: 09:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru