unire sul posto senza archiviazione esterna

Question

Voglio unire due array con valori ordinati in uno. Dal momento che entrambi gli array di origine sono conservati come parti successive di un ampio array, mi chiedo, se conosci un modo per fonderli nella grande memoria. Significa unire inplace.

Tutti i metodi che ho trovato, hanno bisogno di un po 'di memoria esterna. Spesso richiedono array di temperature SQRT (N). C'è un modo efficiente senza di essa?

Sto usando C#. Anche altre lingue benvenute. Grazie in anticipo!

Answer 1

Afaik, unendo due array (persino ordinati) non funziona a disposizione senza aumentare considerevolmente il numero necessario di confronti e mosse di elementi. Vedere: unisci il tipo. Tuttavia, esistono varianti bloccate, che sono in grado di ordinare un elenco di lunghezza n utilizzando un array temporaneo di linght sqrt (n) - come hai scritto - mantenendo comunque il numero di operazioni considerevolmente basso .. non è male - ma anche è male Non "niente" e ovviamente il meglio che puoi ottenere.

Per situazioni pratiche e se te lo puoi permettere, è meglio usare un array temporaneo per unire le tue liste.

Answer 2

Se i valori vengono memorizzati come parti successive di un array più grande, si desidera solo ordinare l'array, rimuovere i valori consecutivi che sono uguali.

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

Prima di concludere che questo sarà troppo lento, implementalo e profilo. Dovrebbero richiedere circa dieci minuti.

Modificare: Questo può ovviamente essere migliorato usando un tipo diverso anziché l'ordinamento incorporato, ad es. QuickSort, Heapsort o Smoothsort, a seconda di quale dà prestazioni migliori in pratica. Si noti che i problemi di architettura hardware significano che i confronti pratici delle prestazioni potrebbero benissimo essere molto diversi dai risultati dell'analisi Big O.

È davvero necessario profilare con diversi algoritmi di ordinamento sulla piattaforma hardware/sistema operativo reale.

Nota: Non sto tentando in questa risposta per dare una risposta accademica, sto cercando di darne una pratica, sul presupposto che stai cercando di risolvere un vero problema.

Answer 3

Non mi interessa l'archiviazione esterna. SQRT (N) o anche più grande non dovrebbe danneggiare le prestazioni. Dovrai solo assicurarti, lo stoccaggio è raggruppato. Soprattutto per dati di grandi dimensioni. Soprattutto per fonderli nei loop. Altrimenti, il GC verrà stressato e consumerà una parte considerevole della larghezza di banda del tempo / memoria della CPU.