Microsoft 内部 PriorityQueue<T> 中的错误？
Bug in Microsoft's internal PriorityQueue<T>?
在 PresentationCore.dll 中的 .NET Framework 中，有一个泛型 PriorityQueue<T> class，其代码可以在 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 class 代码中的 bug 到底在哪里？
可以使用初始化向量 [0, 1, 2, 4, 5, 3] 重现该行为。结果是：
[0, 1, 2, 4, 3, 5]
(可以看出3放错了)
Push算法正确。它以直接的方式构建 min-heap：
- 从右下角开始
- 如果值大于 parent 节点则插入它并且 return
- 否则，将 parent 放在右下角的位置，然后尝试在 parent 位置插入值（并不断交换树直到找到正确的位置）
生成的树是：
0
/ \
/ \
1 2
/ \ /
4 5 3
问题出在 Pop 方法上。它首先将顶部节点视为要填充的 "gap"（因为我们弹出了它）：
*
/ \
/ \
1 2
/ \ /
4 5 3
为了填充它，它会搜索最低的立即数 child（在本例中为：1）。然后它向上移动值以填补空白（child 现在是新的空白）：
1
/ \
/ \
* 2
/ \ /
4 5 3
然后它对新的差距做完全相同的事情，所以差距再次向下移动：
1
/ \
/ \
4 2
/ \ /
* 5 3
当间隙到达底部时，算法...采用树的 bottom-rightmost 值并用它来填充间隙：
1
/ \
/ \
4 2
/ \ /
3 5 *
现在间隙位于 bottom-rightmost 节点，它递减 _count 以从树中移除间隙：
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);
}
}
该代码的主要问题是递归实现，如果元素数量太多，递归实现就会中断。我强烈建议改用优化的第三方库。
编辑：我想我找到了缺少的东西。取了bottom-rightmost节点后，作者刚好忘记重新平衡堆：
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 的回答指出了问题所在。虽然他对堆的重新平衡会起作用，但如果你在原来的删除循环中修复了根本问题，就没有必要了。
正如他所指出的，这个想法是用最低的、最右边的项目替换堆顶部的项目，然后将其筛选到适当的位置。这是对原始循环的简单修改：
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);
我的替换代码包含该修复程序。
无法在 .NET Framework 4.8 中重现
尝试在 2020 年使用 PriorityQueue<T> 的 .NET Framework 4.8 实现重现此问题，如问题中 link 使用以下 XUnit 测试...
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();
}
}
}
}
...在所有 100 万个测试用例中均成功：
所以微软似乎修复了他们实现中的错误：
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
}
}
由于问题中的 link 仅指向最新版本的 Microsoft 源代码（当前为 .NET Framework 4.8），因此很难说代码中到底发生了什么变化，但最值得注意的是现在有一个明确的评论 not 泄漏内存，因此我们可以假设@JimMischel 的回答中提到的内存泄漏也已得到解决，这可以使用 Visual Studio 诊断工具进行确认：
如果存在内存泄漏，我们会在几百万次 Pop() 操作后看到此处发生一些变化...
在 PresentationCore.dll 中的 .NET Framework 中，有一个泛型 PriorityQueue<T> class，其代码可以在 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 class 代码中的 bug 到底在哪里？
可以使用初始化向量 [0, 1, 2, 4, 5, 3] 重现该行为。结果是：
[0, 1, 2, 4, 3, 5]
(可以看出3放错了)
Push算法正确。它以直接的方式构建 min-heap：
- 从右下角开始
- 如果值大于 parent 节点则插入它并且 return
- 否则，将 parent 放在右下角的位置，然后尝试在 parent 位置插入值（并不断交换树直到找到正确的位置）
生成的树是：
0
/ \
/ \
1 2
/ \ /
4 5 3
问题出在 Pop 方法上。它首先将顶部节点视为要填充的 "gap"（因为我们弹出了它）：
*
/ \
/ \
1 2
/ \ /
4 5 3
为了填充它，它会搜索最低的立即数 child（在本例中为：1）。然后它向上移动值以填补空白（child 现在是新的空白）：
1
/ \
/ \
* 2
/ \ /
4 5 3
然后它对新的差距做完全相同的事情，所以差距再次向下移动：
1
/ \
/ \
4 2
/ \ /
* 5 3
当间隙到达底部时，算法...采用树的 bottom-rightmost 值并用它来填充间隙：
1
/ \
/ \
4 2
/ \ /
3 5 *
现在间隙位于 bottom-rightmost 节点，它递减 _count 以从树中移除间隙：
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);
}
}
该代码的主要问题是递归实现，如果元素数量太多，递归实现就会中断。我强烈建议改用优化的第三方库。
编辑：我想我找到了缺少的东西。取了bottom-rightmost节点后，作者刚好忘记重新平衡堆：
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 的回答指出了问题所在。虽然他对堆的重新平衡会起作用，但如果你在原来的删除循环中修复了根本问题，就没有必要了。
正如他所指出的，这个想法是用最低的、最右边的项目替换堆顶部的项目，然后将其筛选到适当的位置。这是对原始循环的简单修改：
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);
我的替换代码包含该修复程序。
无法在 .NET Framework 4.8 中重现
尝试在 2020 年使用 PriorityQueue<T> 的 .NET Framework 4.8 实现重现此问题，如问题中 link 使用以下 XUnit 测试...
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();
}
}
}
}
...在所有 100 万个测试用例中均成功：
所以微软似乎修复了他们实现中的错误：
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
}
}
由于问题中的 link 仅指向最新版本的 Microsoft 源代码（当前为 .NET Framework 4.8），因此很难说代码中到底发生了什么变化，但最值得注意的是现在有一个明确的评论 not 泄漏内存，因此我们可以假设@JimMischel 的回答中提到的内存泄漏也已得到解决，这可以使用 Visual Studio 诊断工具进行确认：
如果存在内存泄漏，我们会在几百万次 Pop() 操作后看到此处发生一些变化...