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

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

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

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

21.07.2011, 16:56. Просмотров 1666. Ответов 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();
                    }
                }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2011, 16:56     Скорость доступа к элементам вектора
Посмотрите здесь:
C++ Время доступа к элементам вектора.
Error C2039 при использовании методов доступа к элементам вектора C++
C++ Обращение к элементам вектора
C++ Обращение к элементам вектора
C++ Как получить доступ к элементам вектора
C++ Доступ к элементам вектора, который находится в map
C++ Структура и осуществление доступа к ее элементам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
oxotnik
1589 / 1066 / 33
Регистрация: 21.08.2008
Сообщений: 4,545
Записей в блоге: 1
21.07.2011, 16:58     Скорость доступа к элементам вектора #2
Цитата Сообщение от snayperAlfa Посмотреть сообщение
ПО идее через итераторы доступ должен быть быстрее
с чего это вдруг?
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
21.07.2011, 17:02     Скорость доступа к элементам вектора #3
snayperAlfa, Почитай тему, уже обсуждалось.
Kastaneda
Форумчанин
Эксперт С++
4511 / 2853 / 227
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 1
Завершенные тесты: 1
21.07.2011, 17:05     Скорость доступа к элементам вектора #4
snayperAlfa, доступ к элементам вектора оператором [] еще быстрее. Потому, что он просто возвращает индексируемый элемент, и все. А ф-ция at() еще с исключения связанна (т.е. она может их "выбросить"), поэтому внутри нее работы больше.



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

Не по теме:

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

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

Добавлено через 1 час 11 минут
Из той темы выходит что итераторы и vector.at(int) по скорости равнозначны.
xAtom
914 / 739 / 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, то есть даже тот же алгоритм будет всегда показывать разные временные показатели.
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
22.07.2011, 12:05  [ТС]     Скорость доступа к элементам вектора #7
Я примерно по 10 раз запускал тестирование скорости.

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

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

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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
22.07.2011, 15:28     Скорость доступа к элементам вектора #12
Цитата Сообщение от fasked Посмотреть сообщение
я думаю, что в windows ситуация такая же.
При использовании GetTickCount, такая же.
Yandex
Объявления
22.07.2011, 15:28     Скорость доступа к элементам вектора
Ответ Создать тему
Опции темы

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