Профилирование stable_sort
это страница говорит, что всякий раз, когда не хватает памяти, stable_sort сводится к алгоритму на месте с временем выполнения O (n (log n) (log n)):
сложность
Если доступно достаточно дополнительной памяти, то линеарифмическое расстояние между первым и последним: до N * log2(N) сравнения элементов (где N — это расстояние), и до этого количества элементов перемещается.
В противном случае, полилинейный на этом расстоянии: выполняет до N * log22(N) сравнения элементов, и до этого много элементов обмена.
Я хочу профилировать его для другого алгоритма на месте с тем же временем выполнения, поэтому мой вопрос сводится к следующему: как я могу имитировать «нехватку памяти», чтобы более медленный алгоритм выполнялся в stable_sort?
Решение
cplusplus.com, как известно, плохо … глядя на описание cppreference.com Вот
Эта функция пытается выделить временный буфер, равный по размеру последовательности, которая должна быть отсортирована, обычно вызывая std :: get_teilitary_buffer. Если распределение не удается, выбирается менее эффективный алгоритм.
get_temporary_buffer является:
template< class T >
std::pair< T*, std::ptrdiff_t > get_temporary_buffer( std::ptrdiff_t count )
Таким образом, в то время как это будет технически недостаточно определенное поведение, чтобы специализировать его для вашего собственного класса в std namespace, вы, вероятно, не делаете этого для производственного кода, и на практике это очень вероятно, будет работать надежно и позволит вам перехватить запрос памяти и вернуть ошибку.
namespace std
{
template <>
std::pair<My_Class*, std::ptrdiff_t>
get_temporary_buffer(std::ptrdiff_t)
{ return {0, 0}; }
}
Другие решения