std :: stable_sort: как выбрать алгоритм оптимизации памяти вместо алгоритма оптимизации времени?
Я хочу использовать std::stable_sort, Сложность алгоритма определяется как
O (N · log ^ 2 (N)), где N = std :: distance (first, last) применения cmp. Если доступна дополнительная память, то сложность O (N · log (N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort
В моем приложении память критична, поэтому я бы предпочел std::stable_sort использовать оптимизированный для памяти O (N · log ^ 2 (N))
алгоритм, а не оптимизированный по времени алгоритм O (N · log (N)).
Я понимаю, что оптимизированная по времени версия будет выбрана только в том случае, если она безопасна
сделать это (память доступна). Тем не менее, я ставлю цель протестировать свое приложение, и поэтому, поскольку память имеет решающее значение, хочу сравнить алгоритм с минимальным потреблением памяти. Поскольку моя система в настоящее время имеет достаточно памяти, чтобы выделить
буфер, он автоматически выберет версию O (N · log ^ 2 (N)) std::stable_sort, Поэтому я хотел бы заявить std::stable_sort в
возьмите оптимизированную для памяти версию. Это возможно?
Появляется политика выполнения
чтобы быть параметром, который может изменить алгоритм, однако, кажется,
только изменить степень параллелизма.
http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t
Хотя выбираю либо
параллельная или последовательная версия может фактически выбирать O (N · log (N)) или
O (N · log ^ 2 (N)) версий соответственно, это нигде не указано на веб-странице.
Интересно, есть ли у кого-нибудь опыт в утверждении этого выбора? Если так
смогут ли они дать какой-либо совет?
Решение
Вы можете заглянуть в свои заголовки и посмотреть, какая функция вызывается, если дополнительный буфер не доступен. Для меня на gcc это
std::__inplace_stable_sort(__first, __last, __comp);
Это, конечно, не соответствует стандартам. __Inplace_stable_sort является вспомогательной функцией и не предназначен для непосредственного использования.
Вызов std :: stable_sort для этой функции является результатом следующего кода
typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __last);
if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
_DistanceType(__buf.size()), __comp);
Другие решения
К сожалению, нет стандартного способа сказать stable_sort сделать сортировку на месте. В C ++ 14 единственные варианты у нас есть
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
В C ++ 17 добавлены версии, которые разрешают политику выполнения, как вы указали, но также не влияют на решение. Если мы посмотрим на требование сложности в [stable.sort], то получим
сложность: Это самое большее
N log²(N)(гдеN == last - first) сравнения; если достаточно дополнительной памяти доступно, этоN log(N).
Поэтому необходимо использовать больше памяти, если она доступна.
Вам либо придется написать свой собственный, и вы можете увидеть Худший случай O (NперN) O (NlnN) на месте стабильной сортировки? об этом или найдите библиотеку, которая предоставляет функцию для вас.