Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.80/10: Рейтинг темы: голосов - 10, средняя оценка - 4.80
PhotonDT
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
1

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

13.05.2012, 20:38. Просмотров 1810. Ответов 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
Ответы с готовыми решениями:

Скорость доступа к элементам вектора
Всем привет! Использую вектор и интеерсует вопрос скорости выбора элементов...

Error C2039 при использовании методов доступа к элементам вектора
# include &lt;iostream&gt; # include &lt;string&gt; # include &lt;fstream&gt; # include...

Обращение к элементам вектора
Вопрос вот в чем. Есть следующий код: #include &lt;vector&gt; #include &lt;iostream&gt;...

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

Присвоение значений элементам двумерного вектора
Недавно добрие люди помогли мне со следующим кодом 1 код ...

29
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 21:00 2
Актуально.Самому интересно. Ждём профессионалов
1
Avazart
Эксперт С++
7725 / 5634 / 549
Регистрация: 10.12.2010
Сообщений: 25,412
Записей в блоге: 17
13.05.2012, 21:04 3
Время доступа к элементам вектора больше, чем больше размерность.
Этого по идее не должно быть в обыном векторе, в дугих многомерных случаях не знаю, сильно намудрили код
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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
Эксперт С++
7725 / 5634 / 549
Регистрация: 10.12.2010
Сообщений: 25,412
Записей в блоге: 17
13.05.2012, 21:29 5
Toshkarik, наверное пробелы между скобками забыл поставить
C++
1
vector<vector<vector<int> > > v(n,vector<vector<int> >(n,n));
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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
664 / 192 / 29
Регистрация: 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
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 10:50 10
Обращение к элементу одинаково во всех трех случаях(если компилятор более менее вменяемый, и не пихает вызов функции для каждого обращения).
Еще возможна ситуация, когда компилятор проверяет выход за границы массива, это тоже будет тормозить обращение.

Цитата Сообщение от Toshkarik Посмотреть сообщение
inline
В с++ это пустое ключевое слово, в подавляющем большинстве случаев оно никак не влияет на генерацию кода.
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 11:19 11
PhotonDT, Выложи инфо компилятора
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
14.05.2012, 17:54 12
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 18:58 13
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, полностью не согласен. В GCC, например, при опции оптимизации O3 или флаге -finline-functions, все inline функции, включая STL, начинают встраиваться. Вот как пример. В студии, насколько я помню, тоже была опция, что то вроде "Увеличение производительности за счет увеличения генерируемого кода".
Ну, мы друг друга не поняли. Этот флаг заставляет функции встраиваться, не спорю. Однако ключевое слово inline на встраивание никак не влияет(большинство компиляторов его просто игнорирует), это я и имел в виду.
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 19:12 14
Toshkarik,
diagon,
Спасибо, за inline etс для ускорения, пригодится. PhotonDT не до конца изложил суть проблемы...
Его цель -- написание курсовой и он сейчас занят исследованием скорости доступа к контейнерам, в частности к вектору.Но видимо из-за его компилятора случилось непредвиденное и ужасное, а противоречий в курсовой не должно быть =)
0
Avazart
Эксперт С++
7725 / 5634 / 549
Регистрация: 10.12.2010
Сообщений: 25,412
Записей в блоге: 17
14.05.2012, 19:19 15
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
14.05.2012, 19:25 16
Цитата Сообщение от diagon Посмотреть сообщение
inline на встраивание никак не влияет
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение. В GCC все мелкие функции в STL, да и не только STL, помечены как inline, не зря ведь. Просто по умолчанию, почему то, встраивание начинается работать только при O3, или явном задании флага. А так да, все inline просто игнорируются.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 19:29 17
Цитата Сообщение от Toshkarik Посмотреть сообщение
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение.
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline. Причем для остальных функций он делает то же самое, т.е. встраивает функцию, если это выгодно, даже если она не помечена как inline.
С register и const ситуация чуть сложнее, но в общем случае они также не влияют на оптимизацию.
P.S. я это не сам придумал, можете у Саттера поподробнее прочитать =)
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
14.05.2012, 19:37 18
Цитата Сообщение от diagon Посмотреть сообщение
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline.
Я это и имел ввиду словом "пытается".

Не по теме:

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

0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 20:37 19
Цитата Сообщение от Avazart Посмотреть сообщение
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
А мы что делаем? одномерный случай мы включаем в рассмотрение, охватить весь объём мы можем, пробелма в опыте и знаниях о контейнерах и др. массивов. Вообще, жалко, что нельзя постить в экспертах =(
0
DU
1487 / 1133 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
14.05.2012, 20:52 20
да сперва одномерный случай и стоит рассмотреть.
вектор устроен примерно так:
struct Vector
{
int* ptr; //указатель на динамически выделенный массив.
};
разница между просто обращением по указателю и обращением через вектор может быть из-за одного косвенного обращения:
ptr[index] vs this->ptr[index]
В остальном от размера вектора не должно зависить. по крайней мере если с увеличением размера вектора и ростет время доступа к дальним элементам, то она так же должна рости и при обращении к элементу через простой динамический массив. В общем разница между вектором и динамически выделенным массивам должна быть из-за одного косвенного обращения. причем это значение постоянное и от размера вектора не зависит.
А вот скорость доступа к ячейке уже может начинать зависить, потому что в игру вступают всякие кеши процессора, и прочая низкоуровневая хренотень, детали которой я не знаю.
так же разница между доступом к статическому и динамическому массивам может быть из-за того, что они в разной памяти находятся. доступ к стеку вроде быстрее. хотя хз. в кногомерных массивах так же из-за переключения страниц памяти время доступа к ячейкам может становится неожиданно долгим.
1
14.05.2012, 20:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2012, 20:52

Как получить доступ к элементам вектора
Нашел вот такой код. А вот как получить доступ к элементам вектора? FILE...

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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