2 Frage: Fehler in Microsofts interner PriorityQueue <T>?

Frage erstellt am Sun, May 28, 2017 12:00 AM

In .NET Framework in PresentationCore.dll gibt es eine generische PriorityQueue<T>-Klasse, deren Code hier .

Ich habe ein kurzes Programm geschrieben, 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 liegt ein Sortierfehler vor, und wenn die Stichprobengröße erhöht wird, nimmt die Anzahl der Sortierfehler proportional zu.

Habe ich etwas falsch gemacht? Wenn nicht, wo befindet sich der Fehler im Code der PriorityQueue-Klasse genau?

    
76
  1. Gemäß den Kommentaren im Quellcode verwendet Microsoft diesen Code seit dem 14.02.2005. Ich frage mich, wie ein Fehler wie dieser über 12 Jahre lang entgangen ist.
    2017-05-28 00: 39: 30Z
  2. @ Nat, da Microsoft es nur verwendet ist hier und eine Schriftart, die manchmal eine Schriftart mit niedrigerer Priorität auswählt, ist ein schwerer Fehler.
    2017-05-28 00: 51: 26Z
2 Antworten                              2                         

Das Verhalten kann mit dem Initialisierungsvektor [0, 1, 2, 4, 5, 3] reproduziert werden. Das Ergebnis ist:

  

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

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

Der Push-Algorithmus ist korrekt. Es wird auf einfache Weise ein Min-Heap erstellt:

  • Beginnen Sie unten rechts
  • Wenn der Wert größer als der übergeordnete Knoten ist, fügen Sie ihn ein und geben Sie
  • zurück
  • Setzen Sie andernfalls das übergeordnete Element in die untere rechte Position und versuchen Sie dann, den Wert an der übergeordneten Stelle einzufügen (und tauschen Sie den Baum weiter aus, bis die richtige Stelle gefunden wurde).

Der resultierende Baum ist:

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

Das Problem liegt bei der Pop-Methode. Es beginnt damit, den oberen Knoten als eine "Lücke" zu betrachten, die zu füllen ist (da wir ihn geöffnet haben):

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

Um es zu füllen, sucht es nach dem untersten unmittelbaren Kind (in diesem Fall: 1). Dann wird der Wert nach oben verschoben, um die Lücke zu füllen (und das Kind ist jetzt die neue Lücke):

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

Dann macht es genau dasselbe mit der neuen Lücke, sodass sich die Lücke wieder verringert:

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

Wenn die Lücke den Grund erreicht hat, nimmt der Algorithmus ... den Wert ganz rechts unten im Baum und füllt damit die Lücke:

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

Jetzt, da sich die Lücke ganz unten rechts befindet, wird _count dekrementiert, um die Lücke aus dem Baum zu entfernen:

 
                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Und am Ende haben wir ... einen kaputten Haufen.

Um ganz ehrlich zu sein, verstehe ich nicht, was der Autor versucht hat, daher kann ich den vorhandenen Code nicht reparieren. Ich kann es höchstens mit einer funktionierenden Version tauschen (schamlos kopiert aus 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);
    }
}

Das Hauptproblem bei diesem Code ist die rekursive Implementierung, die bei einer zu großen Anzahl von Elementen fehlschlägt. Ich empfehle dringend, stattdessen eine optimierte Drittanbieter-Bibliothek zu verwenden.


Bearbeiten: Ich glaube, ich habe herausgefunden, was fehlt. Nachdem der Autor den Knoten ganz unten rechts ausgewählt hatte, vergaß er nur, den Heap neu auszugleichen:

 
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
2017-05-27 23: 23: 44Z
  1. Der "algorithmische Fehler" besteht darin, dass Sie keine Lücke nach unten verschieben, sondern zuerst den Baum verkleinern und das Element unten rechts in diese Lücke einfügen sollten. Reparieren Sie dann den Baum in einer einfachen iterativen Schleife.
    2017-05-28 08: 38: 05Z
  2. Das ist gutes Material für einen Fehlerbericht. Sie sollten es mit einem Link zu diesem Beitrag melden (ich denke, der richtige Ort wäre MS Connect , da PresentationCore nicht auf GitHub ist.
    2017-05-28 12: 48: 32Z
  3. @ LucasTrzesniewski Ich bin mir nicht sicher, wie sich dies auf eine reale Anwendung auswirkt (da es nur für einen unklaren Schriftartauswahlcode in WPF verwendet wird), aber ich schätze es konnte nicht schaden, es zu melden
    2017-05-28 13: 57: 26Z

Die Antwort von Kevin Gosse identifiziert das Problem. Obwohl das erneute Ausgleichen des Heaps funktioniert, ist es nicht erforderlich, dass Sie das grundlegende Problem in der ursprünglichen Entfernungsschleife beheben.

Wie er betonte, besteht die Idee darin, das Element oben auf dem Haufen durch das niedrigste Element ganz rechts zu ersetzen und es dann an die richtige Position zu verschieben. Es ist eine einfache Modifikation der Originalschleife:

 
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 einen Speicherverlust aufweist. Dieses Codebit:

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

Löscht den Wert von _heap[_count - 1] nicht. Wenn im Heap Verweistypen gespeichert werden, verbleiben die Verweise im Heap und können erst dann mit Garbage Collected gespeichert werden, wenn der Speicher für den Heap Garbage Collected ist. Ich weiß nicht, wo dieser Heap verwendet wird, aber wenn er groß ist und über einen längeren Zeitraum läuft, kann er zu einem übermäßigen Speicherverbrauch führen. Die Antwort besteht darin, das Objekt zu löschen, nachdem es kopiert wurde:

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

In meinem Ersatzcode ist dieses Update enthalten.

    
17
2017-12-07 23: 54: 52Z
  1. In einem von mir getesteten Benchmark (zu finden unter pastebin.com/Hgkcq3ex) ist diese Version ungefähr ~ 18% langsamer als die von Kevin Gosse vorgeschlagene (auch wenn Die Clear to Default () -Linie wird entfernt und die _count/2-Berechnung wird außerhalb der Schleife verschoben.
    2017-05-30 21: 43: 41Z
  2. @ MathuSumMut: Ich habe eine optimierte Version bereitgestellt. Anstatt den Gegenstand zu platzieren und ständig zu tauschen, vergleiche ich ihn einfach mit dem an Ort und Stelle befindlichen Gegenstand. Das reduziert die Anzahl der Schreibvorgänge und sollte die Geschwindigkeit erhöhen. Eine weitere mögliche Optimierung besteht darin, _heap[_count] in eine temporäre Datei zu kopieren, wodurch die Anzahl der Array-Verweise verringert wird.
    2017-05-30 22: 53: 49Z
  3. Leider habe ich das ausprobiert und es scheint auch einen Fehler zu geben. Stellen Sie eine Warteschlange vom Typ int ein und verwenden Sie den folgenden benutzerdefinierten Vergleich: Comparer<int>.Create((i1, i2) => -i1.CompareTo(i2)) - nämlich, damit die Sortierung vom größten zum kleinsten Wert erfolgt (beachten Sie das negative Vorzeichen). Nach dem Drücken der Nummern 3, 1, 5, 0, 4 und dem anschließenden Löschen aller Nummern lautete die Rückgabereihenfolge: {5,4,1,3,0}, also meistens noch sortiert, aber die 1 und 3 sind in falscher Reihenfolge. Bei Verwendung der obigen Methode von Gosse trat dieses Problem nicht auf. Beachten Sie, dass ich dieses Problem NICHT in aufsteigender Reihenfolge hatte.
    2017-12-08 08: 38: 45Z
  4. @ NicholasPetersen: Interessant. Ich muss das untersuchen. Vielen Dank für den Hinweis.
    2017-12-08 10: 18: 48Z
  5. Der Fehler in @ JimMischels Code: Der Vergleich rightChild < _count-1 sollte rightChild < _count sein. Dies ist nur dann von Bedeutung, wenn die Anzahl von einer exakten Potenz von 2 verringert wird und nur dann, wenn die Lücke bis zum rechten Rand des Baums reicht. Ganz unten wird das rechte Kind nicht mit seinem linken Geschwister verglichen, und das falsche Element kann befördert werden und den Haufen zerbrechen. Je größer der Baum, desto unwahrscheinlicher ist dies. Es ist am wahrscheinlichsten, dass es auftaucht, wenn die Anzahl von 4 auf 3 verringert wird, was Nicholas Petersens Beobachtung zu den "letzten paar Gegenständen" erklärt.
    2017-12-18 20: 37: 30Z
Quelle platziert Hier
Andere Fragen