Std:: stable_sort: Как выбрать алгоритм с оптимизацией по времени с оптимизацией по времени?

Я хочу использовать std::stable_sort. Сложность алгоритма определяется как

O (N · log ^ 2 (N)), где N = std:: расстояние (первое, последнее) приложения 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 используйте оптимизированную для памяти версию. Возможно ли это?

Появится политика выполнения быть параметром, который может модифицировать алгоритм, однако он появляется чтобы изменить размер parallelism. http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

Хотя выбор параллельная или последовательная версия может фактически выбирать O (N · log (N)) или O (N · log ^ 2 (N)) соответственно, это не указано нигде на веб-странице.

Интересно, есть ли у кого-нибудь опыт в утверждении этого выбора. Если так смогут ли они предоставить какие-либо советы?

Ответ 1

Вы можете просмотреть заголовки и посмотреть, какая функция вызывается, если дополнительный буфер недоступен. Для меня на 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);

Ответ 2

К сожалению, нет стандартного способа сказать stable_sort выполнить сортировку по месту. В С++ 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);

С++ 17 добавлены версии, которые позволяют вам выполнять политику выполнения, но это не повлияет на решение. Если мы посмотрим на требование сложности в [stable.sort], получим

Сложность: она делает не более N log²(N) (где N == last - first) сравнения; если доступно достаточно дополнительной памяти, это N log(N).

Таким образом, он имеет право использовать больше памяти, если он доступен.

Вам либо придется написать свой собственный, и вы можете увидеть Худший случай O (nlnn) O (nln⁡n) на месте стабильного сортировки? или найдите библиотеку, которая предоставляет вам эту функцию.