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

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

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

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

13.05.2012, 20:38. Просмотров 1673. Ответов 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 ; Затем я добавляю...

29
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
14.05.2012, 19:25 #16
Цитата Сообщение от diagon Посмотреть сообщение
inline на встраивание никак не влияет
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение. В GCC все мелкие функции в STL, да и не только STL, помечены как inline, не зря ведь. Просто по умолчанию, почему то, встраивание начинается работать только при O3, или явном задании флага. А так да, все inline просто игнорируются.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.05.2012, 19:29 #17
Цитата Сообщение от Toshkarik Посмотреть сообщение
Вот как раз такие функции компилятор и пытается в первую очередь встроить, а дальше все остальные мелкие, которые не помечены inline, уже встраивает на свое усмотрение.
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline. Причем для остальных функций он делает то же самое, т.е. встраивает функцию, если это выгодно, даже если она не помечена как inline.
С register и const ситуация чуть сложнее, но в общем случае они также не влияют на оптимизацию.
P.S. я это не сам придумал, можете у Саттера поподробнее прочитать =)
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
14.05.2012, 19:37 #18
Цитата Сообщение от diagon Посмотреть сообщение
Не совсем так, компилятор смотрит, выгодно ли инлайнить ту или иную функцию, и если не выгодно, то он ее не инлайнит, даже если она помечена как inline.
Я это и имел ввиду словом "пытается".

Не по теме:

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

0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
14.05.2012, 20:37 #19
Цитата Сообщение от Avazart Посмотреть сообщение
Ternsip, разберитесь сначало с одномерным вектором потому как то о чем вы пишите не должно быть
А мы что делаем? одномерный случай мы включаем в рассмотрение, охватить весь объём мы можем, пробелма в опыте и знаниях о контейнерах и др. массивов. Вообще, жалко, что нельзя постить в экспертах =(
0
DU
1483 / 1129 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
14.05.2012, 20:52 #20
да сперва одномерный случай и стоит рассмотреть.
вектор устроен примерно так:
struct Vector
{
int* ptr; //указатель на динамически выделенный массив.
};
разница между просто обращением по указателю и обращением через вектор может быть из-за одного косвенного обращения:
ptr[index] vs this->ptr[index]
В остальном от размера вектора не должно зависить. по крайней мере если с увеличением размера вектора и ростет время доступа к дальним элементам, то она так же должна рости и при обращении к элементу через простой динамический массив. В общем разница между вектором и динамически выделенным массивам должна быть из-за одного косвенного обращения. причем это значение постоянное и от размера вектора не зависит.
А вот скорость доступа к ячейке уже может начинать зависить, потому что в игру вступают всякие кеши процессора, и прочая низкоуровневая хренотень, детали которой я не знаю.
так же разница между доступом к статическому и динамическому массивам может быть из-за того, что они в разной памяти находятся. доступ к стеку вроде быстрее. хотя хз. в кногомерных массивах так же из-за переключения страниц памяти время доступа к ячейкам может становится неожиданно долгим.
1
Avazart
Нарушитель
Эксперт С++
7231 / 5403 / 291
Регистрация: 10.12.2010
Сообщений: 23,944
Записей в блоге: 17
14.05.2012, 23:49 #21
Да не как не должен зависить от размера ни скорость ни доступ к элементу так как элементы хранятся строго в одном месте, а значит видут себя так же как и массивы.

В коде я не чего не понял и нехочу, так как там сильно награмаждено.
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
14.05.2012, 23:59 #22
Согласен. Код не смотрел, но могу предположить, что вы накапливаете время доступа. У вектора безусловно скорость доступа к элементу ниже чем у простого массива, но как и сказали выше, она никак не должна зависеть от размера.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.05.2012, 08:27 #23
Цитата Сообщение от Toshkarik Посмотреть сообщение
У вектора безусловно скорость доступа к элементу ниже чем у простого массива
Ну почемууу?
Если опускаться до совсем низкого уровня, то массивы - это всего лишь абстракция, на самом деле есть только непрерывный кусок памяти и указатель на его начало.
Во всех трех случаях мы имеем указатель на первый элемент. Затем мы добавляем к этому указателю i * sizeof(...), чтобы получить адрес i-того элемента.
Затем мы просто считываем значение из этого адреса.

Грубо говоря, все 3 случая эквивалентны этому.
C++
1
2
int *arr; //указатель на начало массива
*(arr + i);//получаем i-тый элемент.
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
15.05.2012, 08:39 #24
Ну так везде и пишут, да и логично это. Вектор - шаблонный класс. При доступе к элементу вызывается функция перегрузки оператора. Всегда почему то верил людям и источникам, где это было написано, так как повода сомневаться в их компетентности не было. Везде писали, включая и этот форум, причем кто то из здешних, так сказать, профи - если важна скорость доступа - используйте массивы Си. Вектор же более удобен и высокоуровен. Если Вы думаете по другом, готов услышать Вашу точку зрения.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.05.2012, 08:51 #25
Цитата Сообщение от Toshkarik Посмотреть сообщение
Если Вы думаете по другом, готов услышать Вашу точку зрения.
Тут важно не то, что я думаю, а то, что есть на самом деле.
Провел небольшой эксперимент.
Первый код
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    std::vector< int > arr(5);
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}
В ассемблерном листинге есть следующий кусок
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    //1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    12(%ebx), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2
Второй код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    int *arr = new int [5];
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    scanf
    movl    12(%ebx), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
#APP
# 11 "11.cpp" 1
    //2
Третий код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    int arr[5];
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    //1
# 0 "" 2
#NO_APP
    leal    40(%esp), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    scanf
    movl    40(%esp), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
#APP
# 11 "11.cpp" 1
    //2
Как видно, в первом случае все заинлайнилось(есть только 2 call'a - printf и scanf).
И вообще, эти 3 листинга практически эквивалентны.
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
15.05.2012, 08:55 #26
Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.05.2012, 09:00 #27
Цитата Сообщение от Toshkarik Посмотреть сообщение
Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?
Сомневаюсь, что будет разница.
Компилятор - gcc 4.6.3
Компилировал/проверял так:
Bash
1
2
shadeware@ubunta:~$ g++ 11.cpp -O3 -S
shadeware@ubunta:~$ gedit 11.s
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
15.05.2012, 09:03 #28
Ну так c O2 и ниже думаю ситуация будет совсем другая. Я про это кстати страницу назад и говорил, что если включить встраивание функций, то будет совсем другой результат. Только вот O3 на практике почти никто не использует, разве что для тестов.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.05.2012, 11:45 #29
Вот такие результаты получаются.
-O0
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    //1
# 0 "" 2
#NO_APP
    movl    $3, 4(%esp)
    leal    28(%esp), %eax
    movl    %eax, (%esp)
    call    _ZNSt6vectorIiSaIiEEixEj
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    $3, 4(%esp)
    leal    28(%esp), %eax
    movl    %eax, (%esp)
    call    _ZNSt6vectorIiSaIiEEixEj
    movl    (%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    printf
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2
-O1
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    //1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    12(%ebx), %eax
    movl    %eax, 8(%esp)
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    call    __printf_chk
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2
Т.е. с -O0 встраивания нету, что логично, а вот с -O1 оно уже есть.
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
15.05.2012, 11:50 #30
Ага Не вектор
0
15.05.2012, 11:50
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2012, 11:50
Привет! Вот еще темы с ответами:

Структура и осуществление доступа к ее элементам - 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;...


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

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

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