Название говорит само за себя....
Какой-либо выбор контейнера влияет на скорость стандартного алгоритма std:: sort? Например, если я использую список, алгоритм сортировки просто переключает указатели node или он переключает все данные в узлах?
Какой контейнер STL лучше всего подходит для std:: sort? (Это даже имеет значение?)
Ответ 1
Я не думаю, что std::sort работает в списках, поскольку для него требуется итератор с произвольным доступом, который не предоставляется list<>. Обратите внимание, что list<> предоставляет метод sort, но полностью отделяется от std::sort.
Выбор контейнера имеет значение. STL std::sort полагается на итераторы, чтобы абстрагироваться от того, как контейнер хранит данные. Он просто использует итераторы, которые вы предоставляете для перемещения элементов вокруг. Чем быстрее эти итераторы работают с точки зрения доступа и назначения элемента, тем быстрее будет работать std::sort.
Ответ 2
Выбор действительно имеет значение, но предсказать, какой контейнер будет наиболее эффективным, очень сложно. Лучшим подходом является использование контейнера, который проще всего работать с вашим приложением (возможно, std::vector), проверьте, правильно ли выполняется сортировка с этим контейнером, и если это так. Если нет, выполните профилирование производительности по вашей проблеме сортировки и выберите другой контейнер на основе данных профиля.
Будучи экс-преподавателем и экс-тренером, я иногда чувствую личную ответственность за общую идею о том, что связанный список обладает мистическими свойствами, повышающими производительность. Возьмите его у того, кто знает: единственная причина, по которой связанный список появляется во многих текстовых книгах и учебниках, заключается в том, что для людей, которые написали эти книги и учебные пособия, было понятно, что у них есть структура данных, которая может иллюстрировать указатели, управление динамической памятью, рекурсию, поиск и сортировка всего в одном - это не имеет ничего общего с эффективностью.
Ответ 3
std::list определенно не является хорошим (допустимым) выбором для std::sort(), потому что для std::sort() требуются итераторы с произвольным доступом. std::map и друзья тоже не хороши, потому что позиция элемента не может быть принудительно; то есть позиция элемента на карте не может быть принудительно введена пользователем с вставкой в конкретную позицию или своп. Среди стандартных контейнеров мы доходим до std::vector и std::deque.
std::sort() подобен другим стандартным алгоритмам, поскольку он действует только путем замены значений элементов вокруг (*t = *s). Поэтому даже если список будет магически поддерживать O (1) доступ, ссылки не будут реорганизованы, а их значения будут заменены.
Поскольку std::sort() не изменяет размер контейнера, он не должен влиять на производительность во время выполнения, если вы используете std::vector или std::deque. Примитивные массивы также должны быстро сортироваться, возможно, даже быстрее, чем стандартные контейнеры, но я не ожидаю, что разница в скорости будет достаточно значительной, чтобы оправдать их использование.
Ответ 4
Это зависит от типа элемента.
Если вы просто храните указатели (или POD), тогда вектор будет самым быстрым. Если вы храните объекты, сортировка списка будет быстрее, поскольку она будет заменять узлы, а не физические элементы.
Ответ 5
Алгоритм сортировки ничего не знает о вашем контейнере. Все, что он знает, это итераторы с произвольным доступом. Таким образом, вы можете сортировать вещи, которые даже не находятся в контейнере STL. Итак, как быстро это будет зависеть от итераторов, которые вы ему даете, и как быстро это происходит, чтобы разыменовать и скопировать то, на что они указывают.
std:: sort не будет работать в std:: list, поскольку для сортировки требуются итераторы произвольного доступа. Вы должны использовать один из типов функций std:: list member для этого случая. Эти функции-члены будут эффективно заменять указатели связанных списков вместо копирования элементов.
Ответ 6
Vector.
Всегда используйте вектор по умолчанию. Он имеет минимальные накладные расходы и быстрый доступ к любому другому контейнеру (среди других преимуществ, таких как совместимость с C и итераторы с произвольным доступом).
Теперь спросите себя - что еще вы делаете с контейнером? Вам нужны надежные гарантии исключения? Список, набор и карта, вероятно, будут лучшими параметрами (хотя все они имеют свои собственные процедуры сортировки). Вам нужно регулярно добавлять элементы к передней части контейнера? Рассмотрим deque. Необходимо ли всегда сортировать контейнер? Набор и карта, вероятно, будут лучше подходят.
Наконец, определите, что именно "лучше" для вас, а затем выберите наиболее подходящий контейнер и определите, как он выполняется для ваших нужд.
Ответ 7
Это, безусловно, имеет значение, просто потому, что разные контейнеры имеют разные шаблоны доступа к памяти и т.д., которые могут играть определенную роль.
Однако std::sort не работает на std::list<>::iterators, поскольку это не RandomAccessIterators. Более того, хотя было бы возможно реализовать специализацию для std::list<>, которая перетасовывала указатели узлов, вероятно, имела бы странные и неожиданные семантические последствия - например. если у вас есть итератор внутри отсортированного диапазона в векторе, его значение изменится после сортировки, что не соответствует истине с этой специализацией.
Ответ 8
std:: sort требует итераторов с произвольным доступом, поэтому ваши единственные варианты использования - векторные или deque. Он поменяет значения, и в векторе предположений, вероятно, будет выполняться несколько быстрее, чем deque, потому что он обычно имеет более простую базовую структуру данных. Разница, вероятно, очень незначительна, хотя.
Если вы используете std:: list, существует специализация (std:: list:: sort), которая должна менять указатели, а не значения. Однако, поскольку это не произвольный доступ, он будет использовать mergesort вместо quicksort, что, вероятно, будет означать, что сам алгоритм немного медленнее.
В любом случае, я думаю, что ответ обычно является вектором. Если у вас есть большие классы для каждого элемента, поэтому копирование служебных данных доминирует над процессом сортировки, список может побить его. Или, альтернативно, вы можете хранить указатели на них в векторе и снабжать пользовательский предикат, чтобы отсортировать их соответствующим образом.
Ответ 9
Я полностью согласен с утверждениями, которые ребята разместили выше. Но каков наилучший способ узнать что-то новое? Привет!!!! конечно, не читая текст и не изучая наизусть, но... ПРИМЕРЫ: D Как недавно я погрузился в контейнеры, указанные в STL, вот код быстрого теста, который не требует пояснений, я надеюсь:
#include <iostream>
#include <vector>
#include <deque>
#include <array>
#include <list>
#include <iterator>
#include <cstdlib>
#include <algorithm>
#include "Timer.h"
constexpr int SIZE = 1005000;
using namespace std;
void test();
int main(){
cout<<"array allocates "<<static_cast<double>(SIZE)/(1024*1024)<<" MB\n";
test();
return 0;
}
void test(){
int values[SIZE];
int size = 0;
//init values to sort:
do{
values[size++] = rand() % 100000;
}while(size < SIZE);
//feed array with values:
array<int, SIZE> container_1;
for(int i = 0; i < SIZE; i++)
container_1.at(i) = values[i];
//feed vector with values
vector<int> container_2(begin(values), end(values));
list<int> container_3(begin(values), end(values));
deque<int> container_4(begin(values), end(values));
//meassure sorting time for containers
{
Timer t1("sort array");
sort(container_1.begin(), container_1.end());
}
{
Timer t2("sort vector");
sort(container_2.begin(), container_2.end());
}
{
Timer t3("sort list");
container_3.sort();
}
{
Timer t4("sort deque");
sort(container_4.begin(), container_4.end());
}
}
И код для таймера:
#include <chrono>
#include <string>
#include <iostream>
using namespace std;
class Timer{
public:
Timer(string name = "unnamed") : mName(name){ mStart = chrono::system_clock::now();}
~Timer(){cout<<"action "<<mName<<" took: "<<
chrono::duration_cast<chrono::milliseconds>(
chrono::system_clock::now() - mStart).count()<<"ms"<<endl;}
private:
chrono::system_clock::time_point mStart;
string mName;
};
Вот результат, когда оптимизация не используется (g++ --std = С++ 11 file.cpp -o a.out):
массив выделяет 0,958443 МБ
массив сортировки действий занял: 183ms
действие сортировка вектора взял: 316ms
список сортировки действий занял: 725ms
action sort deque взял: 436ms
и с оптимизацией (g++ -O3 --std = С++ 11 file.cpp -o a.out):
массив выделяет 0,958443 МБ
массив сортировки действий занял: 55ms
действие сортировка вектора взял: 57ms
список сортировки действий занял: 264ms
action sort deque взял: 67ms
Обратите внимание, что хотя вектор и массив имеют аналогичную сортировку по времени для этого случая, размер массива ограничен, поскольку он должен быть инициализирован в стеке (по умолчанию, не используя собственные распределители и т.д.).
Таким образом, это зависит также от использования оптимизации для компилятора, если нет, мы можем видеть заметную разницу.