माइक्रोसॉफ्ट के आंतरिक प्राथमिकता Queue <T> में बग?

Question

प्रस्तुति Core.dll में .NET Framework में, एक सामान्य PriorityQueue<T> वर्ग है जिसका कोड here पाया जा सकता है।

मैं छंटाई परीक्षण करने के लिए एक छोटी कार्यक्रम में लिखा था, और परिणाम महान नहीं थे:

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

परिणाम:

2789658 
3411390 
4618917 
6996709 
found sorting error 
6381637 
9367782 

एक छँटाई त्रुटि हुई है, और नमूने का आकार है अगर बढ़ी, सॉर्टिंग त्रुटियों की संख्या कुछ हद तक आनुपातिक रूप से बढ़ जाती है।

क्या मैंने कुछ गलत किया है? यदि नहीं, PriorityQueue कक्षा के कोड में बग कहां स्थित है?

Answer 1

व्यवहार प्रारंभिक वेक्टर [0, 1, 2, 4, 5, 3] का उपयोग करके पुन: उत्पन्न किया जा सकता है। परिणाम है:

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

(हम देख सकते हैं कि 3 गलत तरीके से रखा जाता है)

Push एल्गोरिथ्म सही है।

अन्यथा नीचे दाईं

यदि मान अधिक है की तुलना में माता पिता के नोड तो डालें और वापसी से

• प्रारंभ, में बजाय माता पिता डाल: यह एक सरल तरीके से एक मिनट-ढेर बनाता है नीचे सही स्थिति है, तो माता-पिता के स्थान पर मूल्य डालने की कोशिश (और जब तक सही जगह मिल गई है पेड़ गमागमन रखने)

जिसके परिणामस्वरूप पेड़ है:

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

समस्या Pop विधि के साथ है। (इस मामले में: 1)

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

इसे भरने के लिए, यह सबसे कम तत्काल बच्चे की खोज करता है: यह एक "अंतर" को भरने के लिए के रूप में शीर्ष नोड पर विचार करके शुरू होता है (के बाद से हम इसे पॉप)। यह तो मान की खाई को भरने के लिए ले जाता है (और बच्चे अब नए खाई है):

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

यह तो नई अंतराल के साथ सटीक एक ही बात करता है, तो अंतर को फिर से नीचे ले जाता है:

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

जब खाई नीचे पहुँच गया है, एल्गोरिथ्म ... पेड़ के नीचे सबसे दायां मूल्य लेता है और यह का उपयोग करता है की खाई को भरने के लिए: अब

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

उस खाई को bottom- पर है सही नोड, यह 0 घटता हैपेड़ से खाई को दूर करने के:

    1 
      / \ 
      / \ 
      4  2 
     /\  
      3 5 

और हम साथ ... एक टूटे हुए ढेर खत्म।

पूरी तरह ईमानदार होने के लिए, मुझे समझ में नहीं आता कि लेखक क्या करने का प्रयास कर रहा था, इसलिए मैं मौजूदा कोड को ठीक नहीं कर सकता। अधिक से अधिक, मैं इसे एक काम संस्करण (बेशर्म 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); 
    } 
} 

कि कोड के साथ मुख्य मुद्दा पुनरावर्ती कार्यान्वयन है, जो अगर तत्वों की संख्या बहुत बड़ी है टूट जाएगा है। मैं दृढ़ता से एक अनुकूलित तृतीय पक्ष पुस्तकालय का उपयोग करने की सलाह देते हैं।

---

संपादित करें: मुझे लगता है कि मुझे पता चला कि क्या गुम है।

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

Answer 2

केविन Gosse के जवाब समस्या को दिखाता है: नीचे सबसे दायां नोड लेने के बाद, लेखक सिर्फ ढेर को संतुलित करने के लिए भूल गया था। यद्यपि ढेर का पुन: संतुलन काम करेगा, लेकिन यदि आप मूल हटाने लूप में मौलिक समस्या को ठीक करते हैं तो यह आवश्यक नहीं है।

जैसा कि उन्होंने बताया, विचार है कि आइटम को सबसे कम, दाएं-सबसे अधिक आइटम के साथ ढेर के शीर्ष पर प्रतिस्थापित करना है, और फिर उसे उचित स्थान पर ले जाना है। यह मूल लूप का एक साधारण संशोधन है:

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

ध्यान दें कि लिखित कोड में स्मृति रिसाव है। कोड का यह बिट:

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

_heap[_count - 1] से मान को साफ़ नहीं करता है। यदि ढेर संदर्भ प्रकारों को संग्रहीत कर रहा है, तो संदर्भ ढेर में रहते हैं और कचरा इकट्ठा नहीं किया जा सकता है जब तक ढेर के लिए स्मृति कचरा इकट्ठा नहीं किया जाता है। मुझे नहीं पता कि यह ढेर कहाँ उपयोग किया जाता है, लेकिन यदि यह बड़ा है और किसी भी महत्वपूर्ण समय के लिए रहता है, तो इससे अतिरिक्त स्मृति खपत हो सकती है। जवाब कॉपी करने के बाद आइटम को साफ़ करना है:

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

मेरा प्रतिस्थापन कोड उस फिक्स को शामिल करता है।