Форум программистов, компьютерный форум 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;
}
Кто знает чем это объясняется, напишите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,584
Записей в блоге: 17
14.05.2012, 23:49     Время доступа к элементам вектора. #21
Да не как не должен зависить от размера ни скорость ни доступ к элементу так как элементы хранятся строго в одном месте, а значит видут себя так же как и массивы.

В коде я не чего не понял и нехочу, так как там сильно награмаждено.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
14.05.2012, 23:59     Время доступа к элементам вектора. #22
Согласен. Код не смотрел, но могу предположить, что вы накапливаете время доступа. У вектора безусловно скорость доступа к элементу ниже чем у простого массива, но как и сказали выше, она никак не должна зависеть от размера.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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-тый элемент.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.05.2012, 08:39     Время доступа к элементам вектора. #24
Ну так везде и пишут, да и логично это. Вектор - шаблонный класс. При доступе к элементу вызывается функция перегрузки оператора. Всегда почему то верил людям и источникам, где это было написано, так как повода сомневаться в их компетентности не было. Везде писали, включая и этот форум, причем кто то из здешних, так сказать, профи - если важна скорость доступа - используйте массивы Си. Вектор же более удобен и высокоуровен. Если Вы думаете по другом, готов услышать Вашу точку зрения.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 листинга практически эквивалентны.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.05.2012, 08:55     Время доступа к элементам вектора. #26
Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.05.2012, 09:03     Время доступа к элементам вектора. #28
Ну так c O2 и ниже думаю ситуация будет совсем другая. Я про это кстати страницу назад и говорил, что если включить встраивание функций, то будет совсем другой результат. Только вот O3 на практике почти никто не использует, разве что для тестов.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 оно уже есть.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2012, 11:50     Время доступа к элементам вектора.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
15.05.2012, 11:50     Время доступа к элементам вектора. #30
Ага Не вектор
Yandex
Объявления
15.05.2012, 11:50     Время доступа к элементам вектора.
Ответ Создать тему
Опции темы

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