Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.97/29: Рейтинг темы: голосов - 29, средняя оценка - 4.97
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84

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

21.07.2011, 16:56. Показов 6234. Ответов 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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
21.07.2011, 16:56
Ответы с готовыми решениями:

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

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

Скорость доступа к элементам массива различными способами
Народ, кто-нить исследовал тему, наиболее скоростного доступа к массивам и операции с элеменами и блоками? Может кто знает статьи? ...

11
 Аватар для oxotnik
1665 / 1134 / 80
Регистрация: 21.08.2008
Сообщений: 4,734
Записей в блоге: 1
21.07.2011, 16:58
Цитата Сообщение от snayperAlfa Посмотреть сообщение
ПО идее через итераторы доступ должен быть быстрее
с чего это вдруг?
0
Freelance
Эксперт С++
 Аватар для asics
2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
21.07.2011, 17:02
snayperAlfa, Почитай тему, уже обсуждалось.
0
 Аватар для Kastaneda
5232 / 3205 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
21.07.2011, 17:05
snayperAlfa, доступ к элементам вектора оператором [] еще быстрее. Потому, что он просто возвращает индексируемый элемент, и все. А ф-ция at() еще с исключения связанна (т.е. она может их "выбросить"), поэтому внутри нее работы больше.



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

Не по теме:

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

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

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

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

А за ассемблерный код спасибо! Теперь понятнее почему оно быстрее выполняется.
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
22.07.2011, 12:24
Угу. Именно на 500 элементах и нужно скорость доступа измерять.
И, раз на таком массиве удалось зафиксировать разницу, можно утверждать о запуске в дебаге. Что тоже очень способствует точности измерения.
Ещё порадовал push_back в коде измерения скорости доступа через at...
0
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
22.07.2011, 14:38  [ТС]
Цитата Сообщение от Deviaphan Посмотреть сообщение
Ещё порадовал push_back в коде измерения скорости доступа через at...
Поясни?
0
Freelance
Эксперт С++
 Аватар для asics
2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
22.07.2011, 14:48
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Поясни?
Если у вектора нет зарезервированого количества елементов, то при push_back(), он будет переносить все свою сущность в другой участок памаяти, что бы он смог взять в себя тот один, следовательно это тоже затраты во времени, которых можно было избежать.
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
22.07.2011, 15:27
Цитата Сообщение от xAtom Посмотреть сообщение
ведь система windows не является реального времени, вдруг когда ты первый раз запустил свой алгоритм в это время какая ни будь служба в система обрабатывала данные, а во второй раз она была в режиме ожидания wait, то есть даже тот же алгоритм будет всегда показывать разные временные показатели.
Если использовать для подсчета тики процессора, то пофигу сколько задача выполнялась по времени, считаются именно тики, выделенные под конкретный процесс. Во всяком случае в *nix системах, я думаю, что в windows ситуация такая же.
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
22.07.2011, 15:28
Цитата Сообщение от fasked Посмотреть сообщение
я думаю, что в windows ситуация такая же.
При использовании GetTickCount, такая же.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
22.07.2011, 15:28
Помогаю со студенческими работами здесь

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

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

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

Как получить доступ к элементам вектора
Нашел вот такой код. А вот как получить доступ к элементам вектора? FILE *ToWrite = fopen(&quot;C:\\result.txt&quot;, &quot;w+&quot;);...

Присвоение значений элементам двумерного вектора
Недавно добрие люди помогли мне со следующим кодом 1 код vector&lt;vector&lt;char&gt;&gt; vv; // ... for (auto row_it = vv.begin() + х;...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru