recursive - mergesort c++ codigo

`std:: list<>:: sort()`-¿por qué el cambio repentino a la estrategia de arriba hacia abajo?

Question

Recuerdo que desde el principio de los tiempos, el enfoque más popular para implementar std::list<>::sort() fue el clásico algoritmo Merge Sort implementado de abajo hacia arriba (ver también Qué hace que la implementación gcc std :: list sort tan rápido?

Recuerdo haber visto a alguien referirse acertadamente a esta estrategia como enfoque de "encadenamiento de cebolla".

Al menos así es en la implementación de GCC de la biblioteca estándar C ++ (ver, por ejemplo, here ). Y así es como estaba en el antiguo STL de Dimkumware en la versión MSVC de la biblioteca estándar, así como en todas las versiones de MSVC hasta VS2013.

Sin embargo, la biblioteca estándar suministrada con VS2015 de repente ya no sigue esta estrategia de clasificación. La biblioteca incluida con VS2015 utiliza una implementación recursiva bastante sencilla de ordenamiento de combinación de arriba hacia abajo . Esto me parece extraño, ya que el enfoque de arriba hacia abajo requiere acceso al punto medio de la lista para dividirlo por la mitad. Dado que std::list<> no admite acceso aleatorio, la única forma de encontrar ese punto medio es iterar literalmente a través de la mitad de la lista. Además, al principio es necesario conocer el número total de elementos en la lista (que no era necesariamente una operación O (1) antes de C ++ 11).

Sin embargo, std::list<>::sort() en VS2015 hace exactamente eso. Aquí hay un extracto de esa implementación que localiza el punto medio y realiza llamadas recursivas

...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...

Como puede ver, simplemente usan std::next con indiferencia para recorrer la primera mitad de la lista y llegar al iterador _Mid .

¿Cuál podría ser la razón detrás de este cambio, me pregunto? Todo lo que veo es una ineficiencia aparentemente obvia de llamadas repetitivas a std::next en cada nivel de recursión. La lógica ingenua dice que esto es más lento . Si están dispuestos a pagar este tipo de precio, probablemente esperan obtener algo a cambio. ¿Qué están obteniendo entonces? No veo de inmediato que este algoritmo tenga un mejor comportamiento de caché (en comparación con el enfoque ascendente original). No veo de inmediato que se comporte mejor en secuencias ordenadas previamente.

De acuerdo, dado que C ++ 11 std::list<> es básicamente necesario para almacenar su recuento de elementos, lo que hace que lo anterior sea un poco más eficiente, ya que siempre sabemos de antemano el recuento de elementos. Pero eso todavía no parece ser suficiente para justificar la exploración secuencial en cada nivel de recursión.

(Es cierto que no he intentado correr las implementaciones entre sí. Quizás haya algunas sorpresas allí).

Answer 1

@sbi le preguntó a Stephan T. Lavavej, mantenedor de la biblioteca estándar de MSVC, quien respondió :

Lo hice para evitar la asignación de memoria y los asignadores de construcción predeterminados.

A esto agregaré "seguridad de excepción básica gratuita".

Para elaborar: la implementación anterior a VS2015 presenta varios defectos:

• _Myt _Templist, _Binlist[_MAXBINS]; crea un grupo de list intermedias s ( _Myt es simplemente un typedef para la instanciación actual de la list ; una ortografía menos confusa para eso es, bueno, list ) para mantener los nodos durante la clasificación, pero estas list están construidas por defecto, lo que conduce a una multitud de problemas:
  1. Si el asignador utilizado no es construible por defecto (y no existe el requisito de que los asignadores sean construibles por defecto), esto simplemente no se compilará, porque el constructor predeterminado de la list intentará construir su asignador por defecto.
  2. Si el asignador utilizado tiene estado, entonces un asignador construido por defecto puede no ser igual a this->get_allocator() , lo que significa que los splice y merge posteriores son un comportamiento técnicamente indefinido y pueden interrumpir las compilaciones de depuración. ("Técnicamente", porque todos los nodos se fusionan de nuevo al final, por lo que en realidad no se desasigna con el asignador incorrecto si la función se completa con éxito).
  3. La list de Dinkumware utiliza un nodo centinela asignado dinámicamente, lo que significa que lo anterior realizará asignaciones dinámicas _MAXBINS + 1 . Dudo que muchas personas esperen que la sort potencialmente arroje bad_alloc . Si el asignador tiene estado, entonces estos nodos centinela pueden incluso no asignarse desde el lugar correcto (ver # 2).
• El código no es una excepción segura. En particular, se permite lanzar la comparación, y si se lanza mientras hay elementos en la list intermedia s, esos elementos simplemente se destruyen con la list s durante el desenrollado de la pila. Los usuarios de sort no esperan que la lista se sort si sort produce una excepción, por supuesto, pero probablemente tampoco esperen que falten los elementos.
  • Esto interactúa muy mal con el n. ° 2 anterior, porque ahora no es solo un comportamiento técnico indefinido: el destructor de esas list intermedias se desasignará y destruirá los nodos empalmados en ellos con el asignador incorrecto.

¿Son esos defectos reparables? Probablemente. # 1 y # 2 se pueden arreglar pasando get_allocator() al constructor de la list s:

 _Myt _Templist(get_allocator());
 _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), 
                             _Myt(get_allocator()),  /* ... repeat _MAXBINS times */ };

El problema de seguridad de la excepción se puede solucionar rodeando el bucle con un try-catch que divide todos los nodos de la list intermedia de nuevo en *this sin tener en cuenta el orden si se lanza una excepción.

La fijación # 3 es más difícil, porque eso significa no usar la list como titular de los nodos, lo que probablemente requiere una cantidad decente de refactorización, pero es factible.

La pregunta es: ¿vale la pena saltar a través de todos estos aros para mejorar el rendimiento de un contenedor que ha reducido el rendimiento por diseño? Después de todo, alguien a quien realmente le importa el rendimiento probablemente no usará la list en primer lugar.

Answer 2

Primera actualización : VS2015 introdujo asignadores no predeterminados, construibles y con estado, lo que presenta un problema al usar listas locales como se hizo con el enfoque ascendente anterior. Pude manejar este problema usando punteros de nodo en lugar de listas (ver más abajo) para un enfoque de abajo hacia arriba.

Segunda actualización : si bien el cambio de listas a iteradores era una forma de resolver el problema con los asignadores y el manejo de excepciones, no era necesario cambiar de arriba a abajo, ya que de abajo hacia arriba se puede implementar usando iteradores. Creé un tipo de fusión de abajo hacia arriba con iteradores, y esencialmente la misma lógica de fusión / empalme utilizada en el enfoque de arriba hacia abajo VS2015. Está al final de esta respuesta.

En el comentario de @ sbi, le preguntó al autor del enfoque de arriba hacia abajo, Stephan T. Lavavej, por qué se hizo el cambio. La respuesta de Stephan fue "evitar la asignación de memoria y los asignadores de construcción predeterminados". El nuevo enfoque de arriba hacia abajo es más lento que el antiguo enfoque de abajo hacia arriba, pero solo usa iteradores (almacenados recursivamente en la pila), no usa ninguna lista local y evita problemas relacionados con los asignadores no predeterminados construibles o con estado. La operación de fusión usa splice () con iteradores para "mover" nodos dentro de una lista, lo que proporciona seguridad de excepción (suponiendo que splice () no puede fallar). La respuesta de @ TC entra en detalles sobre esto. Segunda actualización : sin embargo, un enfoque ascendente también se puede basar en iteradores y esencialmente en la misma lógica de fusión (código de ejemplo al final de esta respuesta). Una vez que se determinó la lógica de fusión, no estoy seguro de por qué no se investigó un enfoque ascendente basado en iteradores y la fusión basada en empalme.

En cuanto al rendimiento, si hay suficiente memoria, generalmente sería más rápido mover la lista a una matriz o vector, ordenar y luego mover la matriz o el vector ordenado nuevamente a la lista.

Puedo reproducir el problema (el tipo antiguo no se compila, el nuevo funciona) basado en una demostración de @IgorTandetnik:

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor

    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}

    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

Noté este cambio en julio de 2016 y envié un correo electrónico a PJ Plauger sobre este cambio el 1 de agosto de 2016. Un fragmento de su respuesta:

Curiosamente, nuestro registro de cambios no refleja este cambio. Eso probablemente signifique que fue "sugerido" por uno de nuestros clientes más grandes y que yo recibí la revisión del código. Todo lo que sé ahora es que el cambio se produjo alrededor del otoño de 2015. Cuando revisé el código, lo primero que me llamó la atención fue la línea:

    iterator _Mid = _STD next(_First, _Size / 2);

que, por supuesto, puede llevar mucho tiempo para una lista grande.

El código se ve un poco más elegante que lo que escribí a principios de 1995 (!), Pero definitivamente tiene una complejidad de tiempo peor. Esa versión fue modelada según el enfoque de Stepanov, Lee y Musser en el STL original. Raramente se descubre que están equivocados en su elección de algoritmos.

Ahora estoy volviendo a nuestra última versión buena conocida del código original.

No sé si la reversión de PJ Plauger al código original se ocupó del nuevo problema del asignador, o si Microsoft interactúa con Dinkumware o cómo lo hace.

Para una comparación de los métodos de arriba hacia abajo y de abajo hacia arriba, creé una lista vinculada con 4 millones de elementos, cada uno de los cuales consta de un entero sin signo de 64 bits, suponiendo que terminaría con una lista doblemente vinculada de nodos ordenados casi secuencialmente (aunque sería asignado dinámicamente), los llenó con números aleatorios, luego los ordenó. Los nodos no se mueven, solo se cambia el enlace, pero ahora al atravesar la lista se accede a los nodos en orden aleatorio. Luego llené esos nodos ordenados aleatoriamente con otro conjunto de números aleatorios y los ordené nuevamente. Comparé el enfoque de arriba hacia abajo de 2015 con el enfoque de abajo hacia arriba modificado para que coincida con los otros cambios realizados para 2015 (sort () ahora llama a sort () con una función de comparación de predicados, en lugar de tener dos funciones separadas). Estos son los resultados. actualización : agregué una versión basada en puntero de nodo y también tomé nota del tiempo para simplemente crear un vector de la lista, ordenar el vector y copiarlo.

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

Para los nodos secuenciales, la versión anterior es solo un poco más rápida, pero para los nodos aleatorios, la versión anterior es un 30% más rápida, y la versión del puntero del nodo un 35% más rápido, y crea un vector de la lista, ordena el vector y luego vuelve a copiar es 69% más rápido

A continuación se muestra el primer código de reemplazo para std :: list :: sort () que usé para comparar el método anterior de abajo hacia arriba con el método de matriz pequeña (_BinList []) versus el enfoque de arriba hacia abajo de VS2015. Quería que la comparación fuera justa, así que modifiqué un copia de <lista>.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don''t go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller''s list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

Hice algunos cambios menores. El código original realizó un seguimiento del bin máximo real en una variable llamada _Maxbin, pero la sobrecarga en la fusión final es lo suficientemente pequeña como para eliminar el código asociado con _Maxbin. Durante la construcción de la matriz, el bucle interno del código original se fusionó en un elemento _Binlist [], seguido de un intercambio en _Templist, que parecía inútil. Cambié el bucle interno para fusionarme en _Templist, solo intercambiando una vez que se encuentra un elemento _Binlist [] vacío.

A continuación se muestra un reemplazo basado en puntero de nodo para std :: list :: sort () que utilicé para otra comparación. Esto elimina los problemas relacionados con la asignación. Si es posible y se produce una excepción de comparación, todos los nodos en la lista de matriz y temporal (pNode) tendrían que agregarse nuevamente a la lista original, o posiblemente una excepción de comparación podría tratarse como una comparación menor.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }

Como alternativa al nuevo VS2015 std :: list :: sort (), puede usar esta versión independiente.

template <typename T>
void listsort(std::list <T> &dll)
{
    const size_t NUMLISTS = 32;
    std::list <T> al[NUMLISTS]; // array of lists
    std::list <T> tl;           // temp list
    while (!dll.empty()){
        // t1 = next element from dll
        tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin()));
        // merge element into array
        size_t i;
        for (i = 0; i < NUMLISTS && !al[i].empty(); i++){
            tl.merge(al[i], std::less<T>());
        }
        if(i == NUMLISTS)       // don''t go past end of array
            i -= 1;
        al[i].swap(tl);         // update array list, empty tl
    }
    // merge array back into original list
    for(size_t i = 0; i < NUMLISTS; i++)
        dll.merge(al[i], std::less<T>());
}

o use el algoritmo gcc similar.

Actualización n. ° 2: desde entonces, he escrito una ordenación de fusión de abajo hacia arriba utilizando una pequeña matriz de iteradores, y esencialmente la misma fusión basada en iterador a través de la función de empalme de VS2015 std :: list :: sort, que debería eliminar el asignador y los problemas de excepción abordado por std :: list :: sort de VS2015. Código de ejemplo a continuación. La llamada a splice () en Merge () es un poco complicada, el último iterador se incrementa después de la llamada real a splice, debido a la forma en que se implementa el incremento de post iterador en std :: list, compensando el empalme. El orden natural de la operación de matriz evita la corrupción de los iteradores de las operaciones de fusión / empalme. Cada iterador en la matriz apunta al comienzo de una sublista ordenada. El final de cada sublista ordenada será el comienzo de una sublista ordenada en la siguiente entrada no vacía anterior en la matriz, o si al principio de la matriz, en una variable.

// iterator array size
#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    std::list<T>::iterator ai[ASZ];     // array of iterators
    std::list<T>::iterator li;          // left   iterator
    std::list<T>::iterator ri;          // right  iterator
    std::list<T>::iterator ei;          // end    iterator
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array
    for (ei = ll.begin(); ei != ll.end();) {
        ri = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            ri = Merge(ll, ai[i], ri, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = ri;
    }
    // merge array into single list
    ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    ri = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        li = ai[i++];
        ri = Merge(ll, li, ri, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator ri,
                             typename std::list<T>::iterator ei)
{
    std::list<T>::iterator ni;
    (*ri < *li) ? ni = ri : ni = li;
    while(1){
        if(*ri < *li){
            ll.splice(li, ll, ri++);
            if(ri == ei)
                return ni;
        } else {
            if(++li == ri)
                return ni;
        }
    }
}

Código de reemplazo para std :: list :: sort () de VS2015 (agrega una función interna _Merge):

    template<class _Pr2>
        iterator _Merge(_Pr2& _Pred, iterator li, iterator ri, iterator ei)
        {
        iterator ni;
        _DEBUG_LT_PRED(_Pred, *ri, *li) ? ni = ri : ni = li;
        while(1)
            {
            if(_DEBUG_LT_PRED(_Pred, *ri, *li))
                {
                splice(li, *this, ri++);
                if(ri == ei)
                    return ni;
                }
            else
                {
                if(++li == ri)
                    return ni;
                }
            }
        }

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {
        if (size() < 2)                 // if size < 2 nothing to do
            return;
        const size_t _ASZ = 32;         // array size
        iterator ai[_ASZ];              // array of iterators
        iterator li;                    // left  iterator
        iterator ri;                    // right iterator
        iterator ei = end();            // end iterator
        size_t i;
        for(i = 0; i < _ASZ; i++)       // "clear array"
            ai[i] = ei;
        // merge nodes into array
        for(ei = begin(); ei != end();)
            {
            ri = ei++;
            for (i = 0; (i < _ASZ) && ai[i] != end(); i++)
                {
                ri = _Merge(_Pred, ai[i], ri, ei);
                ai[i] = end();
                }
            if(i == _ASZ)
                i--;
            ai[i] = ri;
            }
        // merge array into single list
        ei = end();                              
        for(i = 0; (i < _ASZ) && ai[i] == ei; i++);
        ri = ai[i++];
        while(1)
            {
            for( ; (i < _ASZ) && ai[i] == ei; i++);
            if (i == _ASZ)
                break;
            li = ai[i++];
            ri = _Merge(_Pred, li, ri, ei);
            }
        }

Código de reemplazo para std :: list :: sort () de VS2019 (agrega una función interna _Merge y usa la convención de nomenclatura de plantilla VS):

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of iterators to runs
        iterator _Mi;                   // middle   iterator
        iterator _Li;                   // last     iterator
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array runs into single run
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }