Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
13 / 13 / 7
Регистрация: 21.04.2013
Сообщений: 245
1

Сортировка vector и list

21.06.2014, 19:47. Показов 1724. Ответов 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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.06.2014, 19:47
Ответы с готовыми решениями:

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

vector и list
1) Правильно ли я понимаю, что при расширении вектора все предыдущие указатели портятся? ...

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

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

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

Спасибо!
0
31 / 31 / 19
Регистрация: 03.05.2011
Сообщений: 84
21.06.2014, 20:20 4
Зависит от компьютера и флагов оптимизации, видимо.
Но у меня, тем не менее, все как и должно быть:
Компиляция с флагом -O2 дает
1.033 и 16.462
а без него дает
6.653 и 22.111
0
13 / 13 / 7
Регистрация: 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
31 / 31 / 19
Регистрация: 03.05.2011
Сообщений: 84
21.06.2014, 20:52 6
andrejap, Core i7 3610QM
0
13 / 13 / 7
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.06.2014, 00:25

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

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

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

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


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

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

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