Microsoft 내부 PriorityQueue의 버그?
PresentationCore.dll의 .NET Framework에는 여기PriorityQueue<T> 에서 코드를 찾을 수 있는 일반 클래스가 있습니다 .
정렬을 테스트하기 위해 짧은 프로그램을 작성했는데 결과가 좋지 않았습니다.
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클래스 코드의 버그는 정확히 어디에 있습니까?
이 동작은 초기화 벡터를 사용하여 재현 할 수 있습니다 [0, 1, 2, 4, 5, 3]. 결과는 다음과 같습니다.
[0, 1, 2, 4, 3, 5]
(3이 잘못 배치 된 것을 볼 수 있습니다)
Push알고리즘은 올바른 것입니다. 간단한 방법으로 최소 힙을 빌드합니다.
- 오른쪽 하단에서 시작
- 값이 부모 노드보다 크면 삽입하고 반환
- 그렇지 않으면 부모를 오른쪽 하단 위치에 놓고 부모 위치에 값을 삽입 해보십시오 (그리고 올바른 위치를 찾을 때까지 트리를 계속 교체하십시오).
결과 트리는 다음과 같습니다.
0
/ \
/ \
1 2
/ \ /
4 5 3
문제는 Pop방법에 있습니다. 맨 위 노드를 채울 "간격"으로 간주하는 것으로 시작합니다 (팝업 이후).
*
/ \
/ \
1 2
/ \ /
4 5 3
이를 채우기 위해 가장 낮은 직계 자식을 검색합니다 (이 경우 : 1). 그런 다음 값을 위로 이동하여 간격을 채 웁니다 (이제 자식이 새 간격이 됨).
1
/ \
/ \
* 2
/ \ /
4 5 3
그런 다음 새 간격과 똑같은 작업을 수행하므로 간격이 다시 아래로 이동합니다.
1
/ \
/ \
4 2
/ \ /
* 5 3
간격이 맨 아래에 도달하면 알고리즘은 ... 트리의 맨 오른쪽 아래 값을 가져와 간격을 채우는 데 사용합니다.
1
/ \
/ \
4 2
/ \ /
3 5 *
이제 간격이 맨 오른쪽 아래 노드에 _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);
}
}
이 코드의 주요 문제는 재귀 구현으로, 요소 수가 너무 많으면 중단됩니다. 대신 최적화 된 타사 라이브러리를 사용하는 것이 좋습니다.
편집 : 나는 무엇이 빠졌는지 알아 낸 것 같다. 맨 오른쪽 아래 노드를 가져온 후 작성자는 힙의 균형을 다시 조정하는 것을 잊었습니다.
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's answer identifies the problem. Although his re-balancing of the heap will work, it's not necessary if you fix the fundamental problem in the original removal loop.
As he pointed out, the idea is to replace the item at the top of the heap with the lowest, right-most item, and then sift it down to the proper location. It's a simple modification of the original loop:
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);
}
}
Note also that the code as written has a memory leak. This bit of code:
// Fill the last gap by moving the last (i.e., bottom-rightmost) node.
_heap[parent] = _heap[_count - 1];
Does not clear the value from _heap[_count - 1]. If the heap is storing reference types, then the references remain in the heap and cannot be garbage collected until the memory for the heap is garbage collected. I don't know where this heap is used, but if it's large and lives for any significant amount of time, it could cause excess memory consumption. The answer is to clear the item after it's copied:
_heap[_count - 1] = default(T);
My replacement code incorporates that fix.
참고URL : https://stackoverflow.com/questions/44221454/bug-in-microsofts-internal-priorityqueuet
'Development Tip' 카테고리의 다른 글
| 프로그래머는 자신의 코드를 "문서화"하기 위해 부울 변수를 사용해야합니까? (0) | 2020.10.12 |
|---|---|
| Angular 2에서 EventEmitter.next ()와 EventEmitter.emit ()의 차이점 (0) | 2020.10.12 |
| 매개 변수 유형의 객체 인스턴스화 (0) | 2020.10.12 |
| Should I use … in HTML5? (0) | 2020.10.12 |
| Django 모델 필드 기본값은 동일한 모델의 다른 필드를 기반으로 함 (0) | 2020.10.12 |