Pertanyaan Bug di internal PriorityQueue Microsoft ?


Di dalam .NET Framework in PresentationCore.dll, ada generik PriorityQueue<T> kelas yang kode-nya dapat ditemukan sini.

Saya menulis program singkat untuk menguji penyortiran, dan hasilnya tidak bagus:

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

Hasil:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

Ada kesalahan pengurutan, dan jika ukuran sampel meningkat, jumlah kesalahan pengurutan meningkat agak proporsional.

Apakah saya telah melakukan kesalahan? Jika tidak, di mana bug dalam kode PriorityQueue kelas yang terletak persis?


75
2018-05-27 20:44


asal


Jawaban:


Perilaku dapat direproduksi menggunakan vektor inisialisasi [0, 1, 2, 4, 5, 3]. Hasilnya adalah:

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

(kita dapat melihat bahwa 3 salah ditempatkan)

Itu Push Algoritma benar. Ini membangun tumpukan-menit dengan cara yang langsung:

  • Mulai dari kanan bawah
  • Jika nilainya lebih besar dari simpul induk maka masukkan dan kembalikan
  • Jika tidak, letakkan orang tua di posisi kanan bawah, lalu coba masukkan nilai di tempat induk (dan terus menukar pohon sampai tempat yang tepat telah ditemukan)

Pohon yang dihasilkan adalah:

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

Masalahnya adalah dengan Pop metode. Ini dimulai dengan mempertimbangkan simpul teratas sebagai "celah" untuk diisi (karena kita memunculkannya):

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

Untuk mengisinya, ia mencari anak terendah terdekat (dalam hal ini: 1). Kemudian menggerakkan nilai ke atas untuk mengisi celah (dan anak sekarang adalah celah baru):

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

Kemudian melakukan hal yang sama persis dengan jeda baru, sehingga jeda itu bergerak turun lagi:

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

Ketika celah telah mencapai dasar, algoritme ... mengambil nilai paling bawah dari pohon dan menggunakannya untuk mengisi celah:

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

Sekarang celah tersebut berada di node paling bawah paling bawah, itu berkurang _count untuk menghapus celah dari pohon:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Dan kita berakhir dengan ... Tumpukan rusak.

Sejujurnya, saya tidak mengerti apa yang penulis coba lakukan, jadi saya tidak bisa memperbaiki kode yang ada. Paling banter, saya bisa menukarnya dengan versi kerja (tanpa malu-malu disalin dari 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);
    }
}

Masalah utama dengan kode itu adalah implementasi rekursif, yang akan rusak jika jumlah elemen terlalu besar. Saya sangat menyarankan menggunakan pustaka thirdparty yang dioptimalkan.


Edit: Saya pikir saya menemukan apa yang hilang. Setelah mengambil node paling bawah, penulis hanya lupa untuk menyeimbangkan kembali heap:

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



Jawaban Kevin Gosse mengidentifikasi masalahnya. Meskipun penyeimbangan ulang dari heap akan bekerja, itu tidak perlu jika Anda memperbaiki masalah mendasar di loop penghapusan asli.

Seperti yang dia tunjukkan, idenya adalah mengganti item di bagian atas tumpukan dengan barang paling kanan terendah, dan kemudian menyaringnya ke lokasi yang tepat. Ini adalah modifikasi sederhana dari loop asli:

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

Perhatikan juga bahwa kode seperti yang tertulis memiliki kebocoran memori. Ini sedikit kode:

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

Tidak menghapus nilai dari _heap[_count - 1]. Jika heap menyimpan tipe referensi, referensi tetap berada di tumpukan dan tidak dapat dikumpulkan menjadi sampah sampai memori untuk timbunan sampah dikumpulkan. Saya tidak tahu di mana tumpukan ini digunakan, tetapi jika besar dan hidup untuk waktu yang lama, itu dapat menyebabkan konsumsi memori berlebih. Jawabannya adalah untuk menghapus item setelah disalin:

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

Kode pengganti saya menggabungkan perbaikan itu.


16
2018-05-30 16:01