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

Скорость перебор элементов vector'a и list'a - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 5.00
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
27.04.2011, 00:00     Скорость перебор элементов vector'a и list'a #1
Видел на форумах пишут что поиск по несортированному вектору быстрее, чем по листу. Логично предположить что все элементы вектора находятся в едином куске памяти и всегда известно где начинается каждый элемент. В листе же элементы разбросаны и каждый содержет указатель на предыдущий и следующий элемент. Т.е. в векторе всегда указатель перемещается на константную величину, а в листе нужно эту величину ещё прочитать.
Но мне так кажется что если реализовать поиск методом ручного перебора итераторами
C++
1
for (it=vect.begin();it!=vect.end();++it){}
То вектор и лист одинакового размера перебирутся за равное время???
Есть ещё спец. функции - binary_search - ищет по сортированному вектору половинчатым перебором и find - перебирает весь вектор.
Объясните пожалуйста, будет ли выигрыш в скорости при поиске по несортирпованному вектору, вместо листа, если они перебираются последовательно вручную итераторами?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2011, 00:00     Скорость перебор элементов vector'a и list'a
Посмотрите здесь:

C++ STL vector,list
C++ Разница между list и vector
C++ vector, list, deque
C++ vector и list
C++ Контейнеры Vector и List (C++)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
27.04.2011, 01:21     Скорость перебор элементов vector'a и list'a #2
Union, Откуда?
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
27.04.2011, 01:23     Скорость перебор элементов vector'a и list'a #3
Наглядный пример:
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
#include <iostream>
#include <list>
#include <vector>
#include <time.h>
 
using namespace std;
 
void for_list(int n)
{
    list<int> a(n);
    for(list<int>::iterator i=a.begin();i!=a.end();i++)
    {
 
    }
}
 
void for_vector(int n)
{
    vector<int> a(n);
    for(vector<int>::iterator i=a.begin();i!=a.end();i++)
    {
 
    }
}
 
double f_time(void f(int n),int n)
{
    clock_t start_time = clock();
    f(n);
    return double(clock()-start_time)/1000;
}
    
int main()
{
    int n;
    cin >> n;
    cout << "for list - " << f_time(for_list,n) << endl;
    cout << "for vector - " << f_time(for_vector,n) << endl;
    cin.get();
    cin.get();
    return 0;
}
...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
27.04.2011, 01:26     Скорость перебор элементов vector'a и list'a #4
Практически одно время.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <list>
#include <ctime>
#include <iostream>
 
int main()
{
    std::vector<int> vec(1000000);
    std::list<int> lst(1000000);
    clock_t vec_start = clock();
    for(std::vector<int>::iterator iter = vec.begin();
        iter != vec.end(); ++iter)
        ;
    clock_t vec_fin = clock();
    std::cout<<"Vector: "<< (static_cast<double>(vec_fin - vec_start)) / CLOCKS_PER_SEC <<'\n';
    clock_t list_start = clock();
    for(std::list<int>::iterator iter = lst.begin();
        iter != lst.end();
        ++iter)
        ;
    clock_t list_fin = clock();
    std::cout<<"List: "<< (static_cast<double>(list_fin - list_start)) / CLOCKS_PER_SEC;
}
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
27.04.2011, 01:56     Скорость перебор элементов vector'a и list'a #5
Вообще то факт, что в векторе элементы располагаются последовательно, должен зарешать... что называется cash-friendly... И пустые циклы это не очень то хорошо...

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
#include <vector>
#include <list>
#include <ctime>
#include <iostream>
 
void foo(int *a) {
    ++(*a);
}
 
int main()
{
        std::vector<int> vec(100000000);
        std::list<int>   lst(100000000);
        
    clock_t vec_start = clock();
        for(std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
        foo(&(*iter));
 
        clock_t vec_fin = clock();
        std::cout<<"Vector: "<< (static_cast<double>(vec_fin - vec_start)) / CLOCKS_PER_SEC << '\n';
        
    clock_t list_start = clock();
        for(std::list<int>::iterator iter = lst.begin(); iter != lst.end(); ++iter)
                foo(&(*iter));
 
        clock_t list_fin = clock();
        std::cout<<"List: "<< (static_cast<double>(list_fin - list_start)) / CLOCKS_PER_SEC << '\n';
}
Код
> g++ -O2 vector.cpp -o vector
> ./vector
Vector: 0.3
List: 2.21
Ну а статический массив стабильно выдает 0
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
27.04.2011, 03:51     Скорость перебор элементов vector'a и list'a #6
У меня тоже вектор зарешал(как и должно быть).
При 100000 элементов список проходил за 13 секунд, а вектор за 0.2 Разница существенная.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,136
Записей в блоге: 26
27.04.2011, 08:12     Скорость перебор элементов vector'a и list'a #7
Цитата Сообщение от Overmind024 Посмотреть сообщение
При 100000 элементов список проходил за 13 секунд, а вектор за 0.2 Разница существенная
Если у тебя в тесте пустой цикл, то эти данные вообще ни о чём не говорят. Если хочется сделать максимально просто, то заведи глобальную переменную с квалификатором volatile и в цикле её инкрементируй. ТОгда более-менее реальные результаты получишь
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2011, 10:02     Скорость перебор элементов vector'a и list'a
Еще ссылки по теме:

Сортировка vector и list C++
C++ Контейнеры Vector,List
Шаблоны, vector, list C++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.04.2011, 10:02     Скорость перебор элементов vector'a и list'a #8
Цитата Сообщение от Union Посмотреть сообщение
будет ли выигрыш в скорости при поиске по не сортированному
. Если элементы не отсортированы, то двоичным искать нельзя.
Yandex
Объявления
27.04.2011, 10:02     Скорость перебор элементов vector'a и list'a
Ответ Создать тему
Опции темы

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