Führen Sie ohne externe Speicher vor Ort zusammen

Question

Ich möchte zwei Arrays mit sortierten Werten in einen verschmelzen. Da beide Quellarrays als erfolgreiche Teile eines großen Arrays gespeichert werden, frage ich mich, ob Sie einen Weg kennen, um sie in den großen Speicher zu verschmelzen. Bedeutung in Place Merge.

Alle Methoden, die ich gefunden habe, brauchen einen externen Speicher. Sie benötigen häufig SQRT (N) -Temparrays. Gibt es einen effizienten Weg ohne sie?

Ich benutze C#. Andere Sprachen sind auch willkommen. Danke im Voraus!

Answer 1

AFAIK, das zwei (sogar sortierte) Arrays zusammenfasst, funktioniert nicht so, ohne die erforderliche Anzahl von Vergleiche und Elementenzahlen erheblich zu erhöhen. Sehen: Zusammenführen, sortieren. Es gibt jedoch blockierte Varianten, die in der Lage sind, eine Liste von Länge N zu sortieren, indem er ein temporäres Arrays von Lenght SQRT (n) verwendet - wie Sie geschrieben haben -, indem die Anzahl der Operationen immer noch erheblich niedrig bleibt. Nicht "nichts" und offensichtlich das Beste, was Sie bekommen können.

In praktischen Situationen und wenn Sie es sich leisten können, verwenden Sie ein temporäres Array besser, um Ihre Listen zusammenzuführen.

Answer 2

Wenn die Werte als erfolgreiche Teile eines größeren Arrays gespeichert werden, möchten Sie nur das Array sortieren und dann aufeinanderfolgende Werte entfernen, die gleich sind.

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

Bevor Sie zu dem Schluss kommen, dass dies zu langsam ist, implementieren Sie es und profilieren Sie es. Das sollte ungefähr zehn Minuten dauern.

Bearbeiten: Dies kann natürlich verbessert werden, indem eine andere Art und nicht die integrierte Sorte, z. B. Quicksort, Haufen oder SmoothSort, verwendet werden, je nachdem, was in der Praxis eine bessere Leistung erbringt. Beachten Sie, dass Hardware -Architekturprobleme bedeuten, dass die praktischen Leistungsvergleiche möglicherweise sehr gut von den Ergebnissen der Big O -Analyse unterscheiden.

Wirklich, Sie müssen es mit unterschiedlichen Sortieralgorithmen auf Ihrer tatsächlichen Hardware-/Betriebssystemplattform profilieren.

Notiz: Ich versuche nicht in dieser Antwort, eine akademische Antwort zu geben, ich versuche, eine praktische zu geben, in der Annahme, dass Sie versuchen, ein echtes Problem zu lösen.

Answer 3

Es ist sich nicht um den externen Speicher. SQRT (n) oder sogar größer sollten Ihre Leistung nicht schaden. Sie müssen nur sicherstellen, dass der Speicher gepoolt wird. Besonders für große Daten. Vor allem, um sie in Schleifen zu verschmelzen. Andernfalls wird der GC gestresst und frisst einen beträchtlichen Teil Ihrer CPU -Zeit- / Speicherbandbreite.