¿Error en la PriorityQueue <T> interna de Microsoft?

81

En .NET Framework en PresentationCore.dll, hay una PriorityQueue<T>clase genérica cuyo código se puede encontrar aquí .

Escribí un programa corto para probar la clasificación y los resultados no fueron excelentes:

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

Resultados:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

Hay un error de clasificación y, si se aumenta el tamaño de la muestra, el número de errores de clasificación aumenta de forma algo proporcional.

¿Hice algo malo? Si no es así, ¿dónde se PriorityQueueencuentra exactamente el error en el código de la clase?

MathuSum Mut
fuente
3
Según los comentarios en el código fuente, Microsoft ha estado usando este código desde 2005-02-14. Me pregunto cómo un error como este pasó inadvertido durante más de 12 años.
Nat
9
@Nat porque el único lugar donde lo usa microsoft es aquí y una fuente que elige un tipo de letra de menor prioridad algunas veces es un error difícil de notar.
Scott Chamberlain

Respuestas:

83

El comportamiento se puede reproducir utilizando el vector de inicialización [0, 1, 2, 4, 5, 3]. El resultado es:

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

(podemos ver que 3 está colocado incorrectamente)

El Pushalgoritmo es correcto. Construye un min-heap de una manera sencilla:

  • Empiece desde abajo a la derecha
  • Si el valor es mayor que el nodo principal, insértelo y regrese
  • De lo contrario, coloque el padre en la posición inferior derecha, luego intente insertar el valor en el lugar del padre (y siga intercambiando el árbol hasta que se encuentre el lugar correcto)

El árbol resultante es:

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

El problema está en el Popmétodo. Comienza considerando el nodo superior como un "espacio" para llenar (ya que lo abrimos):

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

Para llenarlo, busca el hijo inmediato más bajo (en este caso: 1). Luego mueve el valor hacia arriba para llenar el espacio (y el niño ahora es el nuevo espacio):

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

Luego hace exactamente lo mismo con el nuevo espacio, por lo que el espacio se mueve hacia abajo nuevamente:

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

Cuando el espacio ha llegado al final, el algoritmo ... toma el valor del extremo inferior derecho del árbol y lo usa para llenar el espacio:

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

Ahora que la brecha está en el nodo de la parte inferior derecha, disminuye _countpara eliminar la brecha del árbol:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Y terminamos con ... Un montón roto.

Para ser perfectamente honesto, no entiendo qué estaba tratando de hacer el autor, así que no puedo arreglar el código existente. A lo sumo, puedo cambiarlo con una versión funcional (copiado descaradamente de 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);
    }
}

El problema principal con ese código es la implementación recursiva, que se romperá si el número de elementos es demasiado grande. En su lugar, recomiendo encarecidamente utilizar una biblioteca de terceros optimizada.


Editar: Creo que descubrí lo que falta. Después de tomar el nodo de la parte inferior derecha, el autor simplemente se olvidó de reequilibrar el montón:

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--;
}
Kevin Gosse
fuente
4
El 'error algorítmico' es que no debe mover un espacio hacia abajo, sino primero encoger el árbol y colocar el elemento inferior derecho en ese espacio. Luego repare el árbol en un ciclo iterativo simple.
Henk Holterman
5
Es un buen material para un informe de error, debería informarlo con un enlace a esta publicación (creo que el lugar correcto sería MS connect, ya que PresentationCore no está en GitHub).
Lucas Trzesniewski
4
@LucasTrzesniewski No estoy seguro del impacto en una aplicación del mundo real (ya que solo se usa para un código oscuro de selección de fuentes en WPF), pero supongo que no estaría de más informarlo
Kevin Gosse
20

La respuesta de Kevin Gosse identifica el problema. Aunque su reequilibrio del montón funcionará, no es necesario si soluciona el problema fundamental en el ciclo de eliminación original.

Como señaló, la idea es reemplazar el elemento en la parte superior del montón con el elemento más bajo, más a la derecha, y luego tamizarlo hacia la ubicación adecuada. Es una simple modificación del bucle original:

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

Tenga en cuenta también que el código tal como está escrito tiene una pérdida de memoria. Este fragmento de código:

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

No borra el valor de _heap[_count - 1]. Si el montón está almacenando tipos de referencia, las referencias permanecen en el montón y no se pueden recolectar como basura hasta que la memoria del montón sea como basura. No sé dónde se usa este montón, pero si es grande y tiene una vida útil significativa, podría causar un consumo excesivo de memoria. La respuesta es borrar el elemento después de copiarlo:

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

Mi código de reemplazo incorpora esa solución.

Jim Mischel
fuente
1
En un punto de referencia que probé (se puede encontrar en pastebin.com/Hgkcq3ex), esta versión es aproximadamente ~ 18% más lenta que la propuesta por Kevin Gosse (incluso si se elimina la línea clear to default () y el _count/2cálculo se eleva fuera el lazo).
MathuSum Mut
@MathuSumMut: proporcioné una versión optimizada. En lugar de colocar el artículo y cambiarlo continuamente, lo comparo con el artículo en su lugar. Eso reduce el número de escrituras, por lo que debería aumentar la velocidad. Otra posible optimización sería la de copiar _heap[_count]a un temporal, lo que reduciría el número de referencias a la matriz.
Jim Mischel
Desafortunadamente, probé esto y parece que también tiene un error. Establezca una cola de tipo int y utilice este comparador personalizado: Comparer<int>.Create((i1, i2) => -i1.CompareTo(i2))- es decir, para ordenarlo de mayor a menor (observe el signo negativo). Después de presionar en orden los números: 3, 1, 5, 0, 4, y luego pasar por la cola de todos, el orden de devolución fue: {5,4,1,3,0}, por lo que en su mayoría todavía están ordenados, pero el 1 y 3 están en orden incorrecto. Usar el método de Gosse anterior no tuvo este problema. Tenga en cuenta que NO tuve este problema en orden ascendente normal.
Nicholas Petersen
1
@NicholasPetersen: Interesante. Tendré que investigar eso. Gracias por la nota.
Jim Mischel
2
El error en el código de @ JimMischel: la comparación rightChild < _count-1debería ser rightChild < _count. Esto solo importa cuando se reduce el recuento de una potencia exacta de 2, y solo cuando el espacio se desplaza hasta el borde derecho del árbol. En la parte inferior, rightChild no se compara con su hermano izquierdo, y el elemento incorrecto puede promoverse, rompiendo el montón. Cuanto más grande sea el árbol, menos probable es que esto suceda; es más probable que aparezca cuando se reduce el recuento de 4 a 3, lo que explica la observación de Nicholas Petersen sobre los "últimos elementos de la pareja".
Sam Bent - MSFT
0

No reproducible en .NET Framework 4.8

Intentando reproducir este problema en 2020 con la implementación de .NET Framework 4.8 del PriorityQueue<T>enlace de la pregunta utilizando la siguiente XUnitprueba ...

public class PriorityQueueTests
{
    [Fact]
    public void PriorityQueueTest()
    {
        Random random = new Random();
        // Run 1 million tests:
        for (int i = 0; i < 1000000; i++)
        {
            // Initialize PriorityQueue with default size of 20 using default comparer.
            PriorityQueue<int> priorityQueue = new PriorityQueue<int>(20, Comparer<int>.Default);
            // Using 200 entries per priority queue ensures possible edge cases with duplicate entries...
            for (int j = 0; j < 200; j++)
            {
                // Populate queue with test data
                priorityQueue.Push(random.Next(0, 100));
            }
            int prev = -1;
            while (priorityQueue.Count > 0)
            {
                // Assert that previous element is less than or equal to current element...
                Assert.True(prev <= priorityQueue.Top);
                prev = priorityQueue.Top;
                // remove top element
                priorityQueue.Pop();
            }
        }
    }
}

... tiene éxito en los 1 millón de casos de prueba:

ingrese la descripción de la imagen aquí

Entonces parece que Microsoft solucionó el error en su implementación:

internal void Pop()
{
    Debug.Assert(_count != 0);
    if (!_isHeap)
    {
        Heapify();
    }

    if (_count > 0)
    {
        --_count;

        // discarding the root creates a gap at position 0.  We fill the
        // gap with the item x from the last position, after first sifting
        // the gap to a position where inserting x will maintain the
        // heap property.  This is done in two phases - SiftDown and SiftUp.
        //
        // The one-phase method found in many textbooks does 2 comparisons
        // per level, while this method does only 1.  The one-phase method
        // examines fewer levels than the two-phase method, but it does
        // more comparisons unless x ends up in the top 2/3 of the tree.
        // That accounts for only n^(2/3) items, and x is even more likely
        // to end up near the bottom since it came from the bottom in the
        // first place.  Overall, the two-phase method is noticeably better.

        T x = _heap[_count];        // lift item x out from the last position
        int index = SiftDown(0);    // sift the gap at the root down to the bottom
        SiftUp(index, ref x, 0);    // sift the gap up, and insert x in its rightful position
        _heap[_count] = default(T); // don't leak x
    }
}

Como el enlace en las preguntas solo apunta a la versión más reciente del código fuente de Microsoft (actualmente .NET Framework 4.8), es difícil decir qué se cambió exactamente en el código, pero lo más notable es que ahora hay un comentario explícito para no perder memoria, por lo que podemos suponga que la pérdida de memoria mencionada en la respuesta de @ JimMischel también se ha abordado, lo que se puede confirmar con las herramientas de diagnóstico de Visual Studio:

ingrese la descripción de la imagen aquí

Si hubiera una pérdida de memoria, veríamos algunos cambios aquí después de un par de millones de Pop()operaciones ...

Frederik Hoeft
fuente