Frage Fehler in der internen Prioritätsqueue von Microsoft?


In .NET Framework in PresentationCore.dll gibt es ein generisches PriorityQueue<T> Klasse, deren Code gefunden werden kann Hier.

Ich schrieb ein kurzes Programm, um die Sortierung zu testen, und die Ergebnisse waren nicht großartig:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using MS.Internal;

namespace ConsoleTest {
    public static class ConsoleTest {
        public static void Main() {
            PriorityQueue<int> values = new PriorityQueue<int>(6, Comparer<int>.Default);
            Random random = new Random(88);
            for (int i = 0; i < 6; i++)
                values.Push(random.Next(0, 10000000));
            int lastValue = int.MinValue;
            int temp;
            while (values.Count != 0) {
                temp = values.Top;
                values.Pop();
                if (temp >= lastValue)
                    lastValue = temp;
                else
                    Console.WriteLine("found sorting error");
                Console.WriteLine(temp);
            }
            Console.ReadLine();
        }
    }
}

Ergebnisse:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

Es gibt einen Sortierfehler, und wenn die Stichprobengröße erhöht wird, erhöht sich die Anzahl der Sortierfehler etwas proportional.

Habe ich etwas falsch gemacht? Wenn nicht, wo ist der Fehler im Code der PriorityQueue Klasse genau lokalisiert?


75
2018-05-27 20:44


Ursprung


Antworten:


Das Verhalten kann unter Verwendung des Initialisierungsvektors reproduziert werden [0, 1, 2, 4, 5, 3]. Das Ergebnis ist:

[0, 1, 2, 4, 3, 5]

(Wir können sehen, dass 3 falsch platziert ist)

Das Push Algorithmus ist korrekt. Es baut auf einfache Weise einen Min-Heap auf:

  • Beginnen Sie von unten rechts
  • Wenn der Wert größer als der Elternknoten ist, fügen Sie ihn ein und geben Sie zurück
  • Andernfalls setzen Sie das Elternelement in die untere rechte Position und versuchen Sie dann, den Wert an der übergeordneten Stelle einzufügen (und tauschen Sie den Baum solange aus, bis der richtige Ort gefunden wurde).

Der resultierende Baum ist:

                 0
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

Das Problem ist mit der Pop Methode. Es beginnt damit, dass wir den obersten Knoten als "Lücke" betrachten, um ihn zu füllen (seit wir ihn geknallt haben):

                 *
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

Um es zu füllen, sucht es nach dem niedrigsten unmittelbaren Kind (in diesem Fall: 1). Dann verschiebt es den Wert, um die Lücke zu füllen (und das Kind ist jetzt die neue Lücke):

                 1
               /   \
              /     \
             *       2
           /  \     /
          4    5   3

Es macht dann genau dasselbe mit der neuen Lücke, also bewegt sich die Lücke wieder nach unten:

                 1
               /   \
              /     \
             4       2
           /  \     /
          *    5   3

Wenn die Lücke den unteren Rand erreicht hat, nimmt der Algorithmus ... den ganz rechts unten stehenden Wert des Baums und verwendet ihn, um die Lücke zu füllen:

                 1
               /   \
              /     \
             4       2
           /  \     /
          3    5   *

Jetzt, da sich die Lücke am Knoten ganz rechts unten befindet, wird sie verringert _count um die Lücke vom Baum zu entfernen:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Und wir enden mit ... Ein gebrochener Haufen.

Um ganz ehrlich zu sein, verstehe ich nicht, was der Autor versucht hat, also kann ich den bestehenden Code nicht reparieren. Allenfalls kann ich es gegen eine funktionierende Version tauschen (schamlos kopiert von Wikipedia):

internal void Pop2()
{
    if (_count > 0)
    {
        _count--;
        _heap[0] = _heap[_count];

        Heapify(0);
    }
}

internal void Heapify(int i)
{
    int left = (2 * i) + 1;
    int right = left + 1;
    int smallest = i;

    if (left <= _count && _comparer.Compare(_heap[left], _heap[smallest]) < 0)
    {
        smallest = left;
    }

    if (right <= _count && _comparer.Compare(_heap[right], _heap[smallest]) < 0)
    {
        smallest = right;
    }

    if (smallest != i)
    {
        var pivot = _heap[i];
        _heap[i] = _heap[smallest];
        _heap[smallest] = pivot;

        Heapify(smallest);
    }
}

Hauptproblem mit diesem Code ist die rekursive Implementierung, die bricht, wenn die Anzahl der Elemente zu groß ist. Ich empfehle dringend, stattdessen eine optimierte Third Party Library zu verwenden.


Edit: Ich denke, ich habe herausgefunden, was fehlt. Nachdem Sie den Knoten ganz rechts genommen haben, hat der Autor gerade vergessen, den Heap neu zu verteilen:

internal void Pop()
{
    Debug.Assert(_count != 0);

    if (_count > 1)
    {
        // Loop invariants:
        //
        //  1.  parent is the index of a gap in the logical tree
        //  2.  leftChild is
        //      (a) the index of parent's left child if it has one, or
        //      (b) a value >= _count if parent is a leaf node
        //
        int parent = 0;
        int leftChild = HeapLeftChild(parent);

        while (leftChild < _count)
        {
            int rightChild = HeapRightFromLeft(leftChild);
            int bestChild =
                (rightChild < _count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0) ?
                    rightChild : leftChild;

            // Promote bestChild to fill the gap left by parent.
            _heap[parent] = _heap[bestChild];

            // Restore invariants, i.e., let parent point to the gap.
            parent = bestChild;
            leftChild = HeapLeftChild(parent);
        }

        // Fill the last gap by moving the last (i.e., bottom-rightmost) node.
        _heap[parent] = _heap[_count - 1];

        // FIX: Rebalance the heap
        int index = parent;
        var value = _heap[parent];

        while (index > 0)
        {
            int parentIndex = HeapParent(index);
            if (_comparer.Compare(value, _heap[parentIndex]) < 0)
            {
                // value is a better match than the parent node so exchange
                // places to preserve the "heap" property.
                var pivot = _heap[index];
                _heap[index] = _heap[parentIndex];
                _heap[parentIndex] = pivot;
                index = parentIndex;
            }
            else
            {
                // Heap is balanced
                break;
            }
        }
    }

    _count--;
}

77
2018-05-27 22:29



Kevin Gosses Antwort identifiziert das Problem. Obwohl das erneute Ausgleichen des Heapspeichers funktioniert, ist es nicht erforderlich, das grundlegende Problem in der ursprünglichen Entfernungsschleife zu beheben.

Wie er darauf hingewiesen hat, besteht die Idee darin, den Gegenstand oben auf dem Haufen durch den untersten, am weitesten rechts liegenden Gegenstand zu ersetzen und ihn dann an den richtigen Ort zu sieben. Es ist eine einfache Modifikation der ursprünglichen Schleife:

internal void Pop()
{
    Debug.Assert(_count != 0);

    if (_count > 0)
    {
        --_count;
        // Logically, we're moving the last item (lowest, right-most)
        // to the root and then sifting it down.
        int ix = 0;
        while (ix < _count/2)
        {
            // find the smallest child
            int smallestChild = HeapLeftChild(ix);
            int rightChild = HeapRightFromLeft(smallestChild);
            if (rightChild < _count-1 && _comparer.Compare(_heap[rightChild], _heap[smallestChild]) < 0)
            {
                smallestChild = rightChild;
            }

            // If the item is less than or equal to the smallest child item,
            // then we're done.
            if (_comparer.Compare(_heap[_count], _heap[smallestChild]) <= 0)
            {
                break;
            }

            // Otherwise, move the child up
            _heap[ix] = _heap[smallestChild];

            // and adjust the index
            ix = smallestChild;
        }
        // Place the item where it belongs
        _heap[ix] = _heap[_count];
        // and clear the position it used to occupy
        _heap[_count] = default(T);
    }
}

Beachten Sie auch, dass der geschriebene Code ein Speicherleck hat. Dieses bisschen Code:

        // Fill the last gap by moving the last (i.e., bottom-rightmost) node.
        _heap[parent] = _heap[_count - 1];

Löscht den Wert nicht von _heap[_count - 1]. Wenn der Heap Referenztypen speichert, bleiben die Verweise im Heap und können nicht mit Garbage Collection gesammelt werden, bis der Speicher für den Heap nicht mehr benötigt wird. Ich weiß nicht, wo dieser Heap verwendet wird, aber wenn er groß ist und über einen längeren Zeitraum lebt, kann dies zu übermäßigem Speicherverbrauch führen. Die Antwort ist, den Artikel nach dem Kopieren zu löschen:

_heap[_count - 1] = default(T);

Mein Ersatzcode enthält dieses Update.


16
2018-05-30 16:01