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

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

Войти
Регистрация
Восстановить пароль
 
andrejap
13 / 13 / 1
Регистрация: 21.04.2013
Сообщений: 245
#1

Сортировка vector и list - C++

21.06.2014, 19:47. Просмотров 813. Ответов 6
Метки нет (Все метки)

Здравствуйте.
vector<int> функцией STL медленнее сортируется, чем list<int> собственным методом.

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
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <list>
//#include <iterator>
 
int main( )
{
    //1
    std::srand(std::time(0));
    const long vals = 20000000;
    std::vector<int> vi0(vals);
    for (auto x : vi0) x = std::rand() % 1000;
    
    //2
    std::vector<int> vi(vi0);
    std::list<int> li(vi0.cbegin(), vi0.cend());
    
    //3
    std::clock_t clocks = clock();
    std::sort(vi.begin(), vi.end());
    std::clock_t clocke = clock();
    std::cout << (double)(clocke - clocks)/CLOCKS_PER_SEC << std::endl;
    
    clocks = clock();
    li.sort();
    clocke = clock();
    std::cout << (double)(clocke - clocks)/CLOCKS_PER_SEC << std::endl;
    
    return 0;
}
Ну и результат:
9.53 - для сортировки vector-а;
8.46 - list.

Разве не наоборот должно быть?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2014, 19:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка vector и list (C++):

Сортировка vector<vector<int>> - C++
Всем привет, подскажите может есть вариант по-оптимальнее ? #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; int...

vector и list - C++
1) Правильно ли я понимаю, что при расширении вектора все предыдущие указатели портятся? vector&lt;int&gt; a; a.push_back(10); int *ptr...

Контейнеры Vector и List (C++) - C++
Уважаемые форумчане! Помогите, пожалуйста, реализовать вручную классы Vector и List с основными их методами, дабы получить аналогию...

STL vector,list - C++
У меня 2 вопроса: 1) можете рассказать,как подробно работает reverse_iterator?Создал вектор,хочу его распечатать в обратном порядке...

vector, list, deque - C++
Пытаюсь разобраться, куда лучше какой контейнер применять, под какие задачи. Первый вопрос по списку: Сказано, что список удаляет любой...

Шаблоны, vector, list - C++
Создать класс Beta таким образом , чтобы при уничтожении последнего объекта на экран выдавалось сообщение о наибольшее количество объектов...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Tulosba
:)
Эксперт С++
4395 / 3238 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
21.06.2014, 20:12 #2
Цитата Сообщение от andrejap Посмотреть сообщение
C++
1
for (auto x : vi0) x = std::rand() % 1000;
Здесь не изменяется содержимое контейнера. Надо хотя бы auto&.
Цитата Сообщение от andrejap Посмотреть сообщение
Ну и результат:
Какой компилятор? Какой режим сборки?
1
andrejap
13 / 13 / 1
Регистрация: 21.04.2013
Сообщений: 245
21.06.2014, 20:16  [ТС] #3
Tulosba, как поставил ссылку, теперь все стало на свои места:
10.05 - vector
52.05 - list

Спасибо!
0
tehnar5
31 / 31 / 12
Регистрация: 03.05.2011
Сообщений: 84
21.06.2014, 20:20 #4
Зависит от компьютера и флагов оптимизации, видимо.
Но у меня, тем не менее, все как и должно быть:
Компиляция с флагом -O2 дает
1.033 и 16.462
а без него дает
6.653 и 22.111
0
andrejap
13 / 13 / 1
Регистрация: 21.04.2013
Сообщений: 245
21.06.2014, 20:26  [ТС] #5
tehnar5, ого, что это у Вас за процессор?
Хех, а вот сейчас запустил на с -O2 на g++:
1.29
46.23

И clang++ с -O2 так же показывает:
1.26
46.02

У меня Core i5 430M.
0
tehnar5
31 / 31 / 12
Регистрация: 03.05.2011
Сообщений: 84
21.06.2014, 20:52 #6
andrejap, Core i7 3610QM
0
andrejap
13 / 13 / 1
Регистрация: 21.04.2013
Сообщений: 245
22.06.2014, 00:25  [ТС] #7
Возник вопрос:
насколько влияют на производительность операции, такие как li.clear() и vi.clear() ?
Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
    //4
    clocks = clock();
    li.clear();
    li = std::list<int>(vi0.cbegin(), vi0.cend());
    vi.clear();
    vi = std::vector<int>(li.cbegin(), li.cend());
    std::sort(vi.begin(), vi.end());
    li.clear(); //REALLY WE NEED THIS?
    li = std::list<int>(vi0.cbegin(), vi0.cend());
    clocke = clock();
    std::cout << "Sorting list by using vector:\n";
    std::cout << ( double ) ( clocke - clocks ) / CLOCKS_PER_SEC << std::endl;

Не по теме:

Этот метод еще демонстрирует время сортировки list-а посредством его копирования во vector, сортировкой там и копированием обратно в list.
Sorting vector:
3.41
Sorting list:
60.89
Sorting list by using vector:
41.45
p.s. упс, в предыдущих примерах я установил li как forward_list.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2014, 00:25
Привет! Вот еще темы с ответами:

Контейнеры Vector,List - C++
Как в массиве списков переместить из первой ячейки все элементы которые делятся на 2 в другую ячейку?

Удаление vector, list, string - C++
Привет! Такая задача. В программе я описал класс Class1. Класс содержит поля стандартных типов, а также поле std::string и...

Разница между list и vector - C++
Подскажите пожалуйста в чем различие между листами и векторами? Сколько не пытался не смог найти реальной разницы между ними. В чем разница...

Разница между list и vector? - C++
Разница между list и vector?


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.06.2014, 00:25
Ответ Создать тему
Опции темы

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