Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.53/19: Рейтинг темы: голосов - 19, средняя оценка - 4.53
1 / 1 / 0
Регистрация: 11.05.2012
Сообщений: 5
1

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

13.05.2012, 20:38. Показов 3893. Ответов 29
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Суть проблемы в том, что я не могу объяснить такое расхождение во времени доступа к элементам динамического, статического массивов и вектора. Время доступа к элементам вектора больше, чем больше размерность. К одномерному в среднем на 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2012, 20:38
Ответы с готовыми решениями:

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

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

Время доступа к элементам
Подскажите, как определить время доступа к эл-там массива двумерного и одномерного. Задача:...

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

29
Эксперт С++
8385 / 6147 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
14.05.2012, 23:49 21
Author24 — интернет-сервис помощи студентам
Да не как не должен зависить от размера ни скорость ни доступ к элементу так как элементы хранятся строго в одном месте, а значит видут себя так же как и массивы.

В коде я не чего не понял и нехочу, так как там сильно награмаждено.
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
14.05.2012, 23:59 22
Согласен. Код не смотрел, но могу предположить, что вы накапливаете время доступа. У вектора безусловно скорость доступа к элементу ниже чем у простого массива, но как и сказали выше, она никак не должна зависеть от размера.
0
Higher
1953 / 1219 / 120
Регистрация: 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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
15.05.2012, 08:39 24
Ну так везде и пишут, да и логично это. Вектор - шаблонный класс. При доступе к элементу вызывается функция перегрузки оператора. Всегда почему то верил людям и источникам, где это было написано, так как повода сомневаться в их компетентности не было. Везде писали, включая и этот форум, причем кто то из здешних, так сказать, профи - если важна скорость доступа - используйте массивы Си. Вектор же более удобен и высокоуровен. Если Вы думаете по другом, готов услышать Вашу точку зрения.
0
Higher
1953 / 1219 / 120
Регистрация: 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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
15.05.2012, 08:55 26
Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?
0
Higher
1953 / 1219 / 120
Регистрация: 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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
15.05.2012, 09:03 28
Ну так c O2 и ниже думаю ситуация будет совсем другая. Я про это кстати страницу назад и говорил, что если включить встраивание функций, то будет совсем другой результат. Только вот O3 на практике почти никто не использует, разве что для тестов.
0
Higher
1953 / 1219 / 120
Регистрация: 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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
15.05.2012, 11:50 30
Ага Не вектор
0
15.05.2012, 11:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.05.2012, 11:50
Помогаю со студенческими работами здесь

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

QVector доступ к элементам вектора
Здравствуйте. Имеется контернер типа QVector&lt;QVector&lt;QPair&lt;float,float&gt;&gt;&gt; Количество векторов ...

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

Как оптимизировать обращение к элементам вектора?
Добрый день. Подскажите, пожалуйста, где я не прав. Есть класс, в нем координаты и другие...

Присвоение значений элементам двумерного вектора
Недавно добрие люди помогли мне со следующим кодом 1 код vector&lt;vector&lt;char&gt;&gt; vv; // ......

Ограничение доступа к элементам UI
Здравствуйте уважаемые android разработчики. Будьте так добры помочь ламеру в доработки приложения....


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru