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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
#1

Скорость доступа к элементам вектора - C++

21.07.2011, 16:56. Просмотров 1753. Ответов 11
Метки нет (Все метки)

Всем привет!

Использую вектор и интеерсует вопрос скорости выбора элементов из него. У вектора есть метод vector.at(int index), который вернет мне элемент по заданному индексу. Также к вектору можно добраться через итераторы. ПО идее через итераторы доступ должен быть быстрее, но на практике выходит что доступ через vector.at(int index) быстрее минимум в 3 раза на векторе в 512 элементов. Почему так? Кто виноват и как еще ускорить доступ к элементам вектора?


Вот кусок кода.
Время измеряется в другом месте программы

C++
1
2
3
4
5
6
7
       INT64 time1, time2;
 
    time1 = rdtsc();
    vector_3 = CharIntBitConverter::VectBitsToVectChar(vector_2);
    time2 = rdtsc();
 
    std::cout<<(time2-time1)<<"\n";
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
/*
                //Работает в 2 раза медленее
                for(std::vector<boost::uint8_t>::const_iterator it = input.begin(); it != input.end(); it++){               
                    temp1.push_back(*it);
                    j++;
 
                    if (j == 8) {
                        j = 0;
                        //vect_10.push_back(CharIntBitConverter::BitsToChar(temp1));
                        BitsToChar(temp1,temp_byte);
                        vect_10.push_back(temp_byte);
 
                        temp1.clear();
                    }
                }
                */
 
 
                //Лучший вариант
                for(boost::uint32_t i = 0; i < input.size(); i++){
                    temp1.push_back(input.at(i));
                    j++;
 
                    if (j == 8) {
                        j = 0;
                        BitsToChar(temp1,temp_byte);
                        vect_10.push_back(temp_byte);
                        temp1.clear();
                    }
                }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2011, 16:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Скорость доступа к элементам вектора (C++):

Время доступа к элементам вектора. - C++
Суть проблемы в том, что я не могу объяснить такое расхождение во времени доступа к элементам динамического, статического массивов и...

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++
как обратиться к N=43 строке вектора нумерация с 0 vector&lt;int&gt; myVector;

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

Как получить доступ к элементам вектора - 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 ; Затем я добавляю...

11
oxotnik
1591 / 1068 / 33
Регистрация: 21.08.2008
Сообщений: 4,545
Записей в блоге: 1
21.07.2011, 16:58 #2
Цитата Сообщение от snayperAlfa Посмотреть сообщение
ПО идее через итераторы доступ должен быть быстрее
с чего это вдруг?
0
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
21.07.2011, 17:02 #3
snayperAlfa, Почитай тему, уже обсуждалось.
0
Kastaneda
Jesus loves me
Эксперт С++
4688 / 2892 / 236
Регистрация: 12.12.2009
Сообщений: 7,353
Записей в блоге: 2
Завершенные тесты: 1
21.07.2011, 17:05 #4
snayperAlfa, доступ к элементам вектора оператором [] еще быстрее. Потому, что он просто возвращает индексируемый элемент, и все. А ф-ция at() еще с исключения связанна (т.е. она может их "выбросить"), поэтому внутри нее работы больше.



Добавлено через 2 минуты

Не по теме:

Цитата Сообщение от asics Посмотреть сообщение
Почитай тему, уже обсуждалось.
Хм... надо в ассемблерном коде покапаться.

0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
21.07.2011, 18:40  [ТС] #5
О, спасибо. Сейчас почитаю.

Добавлено через 1 час 11 минут
Из той темы выходит что итераторы и vector.at(int) по скорости равнозначны.
0
xAtom
915 / 740 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
22.07.2011, 10:36 #6
Итератор вектора в основном используется последовательно со смещением адресов, а получение данных по-индексу массива это получается без смещения указателя
vector[index], у себя тестировал скорость была пропорциональной что с доступ со смещением что без смещения один фиг пачка инструкций одинаковая.
Kastaneda, правильно сказал что at(index) использует проверки, скорость ниже будет чем у [].

Вот пример привёл.
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
#include <windows.h>
#include <iostream>
#include <vector>
using namespace std;
 
 
int main(void) {
 
   vector<long> vec, tmp;
   vector<long>::const_iterator iter;
 
   for(long l = 1e+6; l--; vec.push_back(1e+5 * ((long)rand() % 10)) );
 
 
   DWORD  start = GetTickCount();
 
   /*
   for(iter = vec.begin(); iter != vec.end(); *iter++)
        tmp.push_back(*iter);
   */
 
 
   for(long i = 0L; i < vec.size(); i++)
        tmp.push_back( vec[i] );
 
   tmp.clear();
   cout << "elapsed = " <<  GetTickCount() - start << '\n';
 
 
 
   int index = 5;  // получим шестой элемент
 
   iter = vec.begin();
 
   // вот доступ к элементу без cмещения как vector[index]
   cout <<  *((iter) + index)  << '\n';
 
   // доступ со смещением указателя как работают обычно с итераторами
   iter += index;
   cout << *iter  << '\n';
 
 
   //  перефразируем всё в ASM
   long a, b;
 
   iter = vec.begin();
   __asm {
          mov  esi, iter
          mov  edx, dword ptr index
 
          //доступ без смещения указателя
          mov  ebx, [esi+edx*4]
          mov  dword ptr a, ebx
 
          // доступ со смещением указателя
          mov  eax, 4
          mul   edx
          add   esi, eax
          mov  ebx, [esi]
          mov  dword ptr  b, ebx
   };
 
   cout << "a = " << a << "\nb = " << b << '\n';
 
   cin.get();
   return 0;
}
snayperAlfa, на последок ты когда тестируешь какие-нибудь алгоритмы сравнивая скорость между ними запускай их не один раз а хоть 20-100 раз только после этого нужно сравнивать скорость, ведь система windows не является реального времени, вдруг когда ты первый раз запустил свой алгоритм в это время какая ни будь служба в система обрабатывала данные, а во второй раз она была в режиме ожидания wait, то есть даже тот же алгоритм будет всегда показывать разные временные показатели.
1
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
22.07.2011, 12:05  [ТС] #7
Я примерно по 10 раз запускал тестирование скорости.

C++
1
GetTickCount()
- это WinApiшная функция или за ней скрывается
C++
1
rdtsc()
?

А за ассемблерный код спасибо! Теперь понятнее почему оно быстрее выполняется.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
22.07.2011, 12:24 #8
Угу. Именно на 500 элементах и нужно скорость доступа измерять.
И, раз на таком массиве удалось зафиксировать разницу, можно утверждать о запуске в дебаге. Что тоже очень способствует точности измерения.
Ещё порадовал push_back в коде измерения скорости доступа через at...
0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
22.07.2011, 14:38  [ТС] #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
Ещё порадовал push_back в коде измерения скорости доступа через at...
Поясни?
0
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
22.07.2011, 14:48 #10
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Поясни?
Если у вектора нет зарезервированого количества елементов, то при push_back(), он будет переносить все свою сущность в другой участок памаяти, что бы он смог взять в себя тот один, следовательно это тоже затраты во времени, которых можно было избежать.
0
fasked
Эксперт С++
4948 / 2528 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
22.07.2011, 15:27 #11
Цитата Сообщение от xAtom Посмотреть сообщение
ведь система windows не является реального времени, вдруг когда ты первый раз запустил свой алгоритм в это время какая ни будь служба в система обрабатывала данные, а во второй раз она была в режиме ожидания wait, то есть даже тот же алгоритм будет всегда показывать разные временные показатели.
Если использовать для подсчета тики процессора, то пофигу сколько задача выполнялась по времени, считаются именно тики, выделенные под конкретный процесс. Во всяком случае в *nix системах, я думаю, что в windows ситуация такая же.
1
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
22.07.2011, 15:28 #12
Цитата Сообщение от fasked Посмотреть сообщение
я думаю, что в windows ситуация такая же.
При использовании GetTickCount, такая же.
0
22.07.2011, 15:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.07.2011, 15:28
Привет! Вот еще темы с ответами:

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

Использование #define для доступа к элементам класса - C++
Добрый день. Имеется класс вида: class Test { int key; int smth; } И я хочу сделать #define чтобы быстро получать...

Небольшая прога по методам доступа к элементам массива - C++
Смысл такой, имеется трехмерный массив A. Данные считываются с файла(тут все верно). Хотелось бы обращаться к элементам данного массива по...

Скорость перебор вектора - C++
Вектор можно перебирать двумя способами, первый - через итератор for (it=pairs.begin();it!=pairs.end();++it){ printf(&quot;%i\n&quot;,...


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

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

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