fusionarse en el lugar sin almacenamiento externo

Question

Quiero fusionar dos matrices con valores ordenados en uno. Dado que ambas matrices de origen se almacenan como partes sucesivas de una gran matriz, me pregunto, si conoce una forma de fusionarlas en el gran almacenamiento. Significado fusionar en el lugar.

Todos los métodos que encontré necesitan algo de almacenamiento externo. A menudo requieren matrices de temperatura SQRT (N). ¿Hay una manera eficiente sin él?

Estoy usando C#. Otros idiomas también son bienvenidos. ¡Gracias por adelantado!

Answer 1

AFAIK, fusionar dos matrices (incluso ordenadas) no funciona en el lugar sin aumentar considerablemente el número necesario de comparaciones y movimientos de elementos. Ver: fusionar. Sin embargo, existen variantes bloqueadas, que pueden ordenar una lista de longitud n utilizando una matrices temporal de longitud sqrt (n), como escribió, al mantener el número de operaciones considerablemente bajo ... no es malo, pero también es también No "nada" y obviamente lo mejor que puedes obtener.

Para situaciones prácticas y si puede pagarlo, es mejor que use una matriz temporal para fusionar sus listas.

Answer 2

Si los valores se almacenan como partes posteriores de una matriz más grande, solo desea ordenar la matriz, luego eliminar los valores consecutivos que son iguales.

void  SortAndDedupe(Array<T> a)
{
    // Do an efficient in-place sort
    a.Sort();
    // Now deduplicate
    int lwm = 0; // low water mark
    int hwm = 1; // High water mark
    while(hwm < a.length)
    {
        // If the lwm and hwm elements are the same, it is a duplicate entry.
        if(a[lwm] == a[hwm])
        {
            hwm++;
        }else{
            // Not a duplicate entry - move the lwm up
            // and copy down the hwm element over the gap.
            lwm++;
            if(lwm < hwm){
                a[lwm] = a[hwm];
            }
            hwm++;
        }
    }
    // New length is lwm
    // number of elements removed is (hwm-lwm-1)
}

Antes de concluir que esto será demasiado lento, implementarlo y perfilarlo. Eso debería tomar unos diez minutos.

Editar: Por supuesto, esto se puede mejorar utilizando un tipo diferente en lugar del tipo incorporado, por ejemplo, Quicksort, HeApsort o Smooth Stors, dependiendo de que brinde un mejor rendimiento en la práctica. Tenga en cuenta que los problemas de arquitectura de hardware significan que las comparaciones prácticas de rendimiento pueden ser muy diferentes de los resultados del análisis Big O.

Realmente necesita perfilarlo con algoritmos de tipo de diferentes en su plataforma de hardware/sistema operativo real.

Nota: No estoy intentando en esta respuesta para dar una respuesta académica, estoy tratando de dar una práctica, por supuesto que está tratando de resolver un problema real.

Answer 3

No me importa el almacenamiento externo. SQRT (N) o incluso más grande no debe dañar su rendimiento. Solo tendrá que asegurarse de que el almacenamiento esté agrupado. Especialmente para grandes datos. Especialmente por fusionarlos en bucles. De lo contrario, el GC se estresará y comerá una parte considerable de su tiempo de banda de tiempo / memoria de CPU.