c++ - pseudocodigo - ordenamiento por intercambio

std:: stable_sort: ¿Cómo elegir el algoritmo optimizado para la memoria sobre el algoritmo optimizado en el tiempo?

Question

Deseo hacer uso de std::stable_sort . La complejidad del algoritmo se establece como

O (N · log ^ 2 (N)), donde N = std :: distancia (primera, última) aplicaciones de cmp. Si hay memoria adicional disponible, entonces la complejidad es O (N · log (N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort

En mi aplicación, la memoria es crítica, por lo tanto, preferiría que std::stable_sort utilizara el algoritmo optimizado de memoria O (N · log ^ 2 (N)), en lugar del O optimizado en tiempo (N · log (N) ) Algoritmo. Entiendo que la versión optimizada en el tiempo solo se elegirá si es seguro hacerlo (memoria disponible). Sin embargo, mi objetivo es comparar mi aplicación, y por lo tanto, como la memoria es crítica, quiero comparar el algoritmo cuando el consumo de memoria es más bajo. Como mi sistema actualmente tiene suficiente memoria para asignar el búfer, elegirá automáticamente la versión O (N · log ^ 2 (N)) de std::stable_sort . Por lo tanto, me gustaría afirmar a std::stable_sort para tomar la versión optimizada para la memoria. es posible?

La política de ejecución parece ser un parámetro que puede modificar el algoritmo, sin embargo, parece que solo altera la extensión del paralelismo. http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

Aunque la elección de la versión paralela o secuencial puede ser elegir las versiones O (N · log (N)) o O (N · log ^ 2 (N)) respectivamente, esto no se indica en ninguna parte de la página web.

Me pregunto si alguien tiene alguna experiencia en afirmar esta elección. De ser así, ¿podrían brindar algún consejo?

Answer 1

Lamentablemente, no existe una forma estándar de decirle a stable_sort que realice el ordenamiento in situ. En C ++ 14, las únicas opciones que tenemos

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 agregó versiones que permiten la política de ejecución como usted señala, pero eso tampoco afectará la decisión. Si miramos el requisito de complejidad en [stable.sort] obtenemos

Complejidad : Hace como máximo N log²(N) (donde N == last - first ) comparaciones; si hay suficiente memoria extra disponible, es N log(N).

Por lo tanto, está obligado a usar más memoria si está disponible.

¿Vas a tener que escribir el tuyo propio y puedes ver el peor caso O ( n ln n ) O ( n ln⁡ n ) en lugar estable? sobre eso o encuentre una biblioteca que proporcione la función para usted.

Answer 2

Puede ver sus encabezados y ver qué función se llama si el búfer adicional no está disponible. Para mí en gcc es

    std::__inplace_stable_sort(__first, __last, __comp);

Por supuesto, esto no cumple con los estándares. __inplace_stable_sort es una función auxiliar y no está destinada a ser utilizada directamente.

La llamada de std :: stable_sort a esta función es el resultado del siguiente código

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);