ConcurrentHeap 实现中的问题

Question

这是我的 MaxHeap 实现。大多数时候它都有效，但偶尔它只会导致一些值出现故障。我希望它是线程安全的。试过多次调试，但无法确定问题所在。谁能指出我实施中的问题？

using System.Threading;
using Crossbones.Common;
using LanguageExt;
using static LanguageExt.Prelude;

namespace MySpace
{

public static class Operators
{
    public static bool XOR(bool x, bool y) => (x && !y) || (!x && y);
    public static bool XAND(bool x, bool y) => (x || !y) && (!x || y);
}
    public enum CompareResult
    {
        Left = 1,
        Equal = 0,
        Right = -1
    };

    public delegate CompareResult HeapComparer<T>(in T left, in T right);

    public class Heap<T> where T : struct
    {
        private readonly int _capacity;
        private readonly IComparer<T> _comparer;
        private readonly List<T> _list;
        private long _itemCount;

        public Heap(int capacity, IComparer<T> comparer)
        {
            _capacity = capacity;
            _comparer = comparer;
            _list = new List<T>(capacity);
        }

        public Option<T> Pop()
        {
            Option<T> head = None;


            lock (_list)
            {
                if (_list.Any())
                {
                    head = Some(_list[0]);
                    _list[0] = _list[^1];
                    _list.RemoveAt(_list.Count - 1);
                    Count = _list.Count;
                    ShiftDown(0);
                }
            }


            return head;
        }
        public void Push(in T item)
        {
            lock (_list)
            {
                _list.Add(item);
                var itemIdx = _list.Count - 1;
                while (itemIdx > 0)
                {
                    var parentIdx = (int)(itemIdx - 1) / 2;
                    if (Compare(parentIdx, itemIdx) == CompareResult.Right)
                    {
                        Swap(parentIdx, itemIdx);
                        itemIdx = parentIdx;
                    }
                    else break;
                }

                Count = _list.Count;
            }
        }

        public bool IsEmpty => Count ==0;
        public bool IsFull => Count == _capacity;
        public long Count
        {
            get => Interlocked.Read(ref _itemCount);
            private set => Interlocked.Exchange(ref _itemCount, value);
        }

        public Option<T> Peek(int position)
        {
            Option<T> ret = None;

            if (position < Count - 1)
            {
                lock (_list)
                {
                    ret = Some(_list[position]);
                }
            }

            return ret;

        }

        public IEnumerable<T> ReadAll()
        {
            var ret = new List<T>((int)Count);

            lock (_list)
            {
                ret = _list;
                _list.Clear();
                Count = 0L;
            }

            return ret;
        }

        void Swap(int leftIdx, int rightIdx)
        {
            var tmp = _list[leftIdx];
            _list[leftIdx] = _list[rightIdx];
            _list[rightIdx] = tmp;
        }
        CompareResult Compare(int idxLeft, int idxRight) => _comparer.Compare(_list[idxLeft], _list[idxRight]) switch
        {
            -1 => CompareResult.Right,
            0 => CompareResult.Equal,
            1 => CompareResult.Left
        };
        int ShiftDown(int itemIdx)
        {
            var ret = itemIdx;
            var maxIdx = _list.Count - 1;
            while (itemIdx < maxIdx)
            {
                var left = (index: 2 * itemIdx + 1, present: (2 * itemIdx + 1) <= maxIdx);
                var right = (index: 2 * itemIdx + 2, present: (2 * itemIdx + 2) <= maxIdx);

                if (left.present && right.present)
                {
                    var target = Compare(left.index, right.index) switch
                    {
                        CompareResult.Left => left,
                        CompareResult.Right => right,
                        CompareResult.Equal => left
                    };
                    if (target.present)
                    {
                        Swap(target.index, itemIdx);
                        itemIdx = target.index;
                    }
                    else break;
                }
                else if (Operators.XOR(left.present, right.present))
                {
                    var target = left.present ? left : right.present ? right : (index: itemIdx, present: false);
                    if (target.present && Compare(target.index, itemIdx) == CompareResult.Left)
                    {
                        Swap(target.index, itemIdx);
                        itemIdx = target.index;
                    }
                    else itemIdx = target.index;
                }

                else break;
            }

            return ret;
        }
    }

}

我使用 LanguageExt.Core 来处理一些功能性的东西。主要是Option, Some, None.

我单独保存计数，以便读取 Count 和 IsEmpty、IsFull 是原子操作。

Answer 1

我可以指出几个问题：

Count,get => Interlocked.Read(ref _itemCount); 你不使用锁。因此，如果一个线程调用它而另一个线程在 Push 中，这很容易 return 一个不正确的值，就在添加新元素和更新计数之间。 Pop 也是如此。因此，IsFull 和 IsEmpty 也会失败。
Peek - 您从锁中读取了 Count，因此它首先确定堆中有一个项目并尝试获取它，但没有任何已经。
ReadAll 看起来坏了。除非我弄错了，否则它总是 return 一个空列表。您正确地尝试 return 一份副本，但我没有看到您在制作副本。您复制参考。

根据您的用例，您可能希望查看 ReaderWriterLockSlim 而不是 lock。

Answer 2

ShiftDown 的逻辑过于复杂。当 left 和 right 都存在时，不需要测试 target.present。您已经知道 target 存在，因为它只能是 left 或 right.

如果他们不在场，那么您知道 left 是在场的那一个。在适当的堆中，因为它是 left-filled，如果一个节点没有左 child.

，它就不能有右 child

下面是一个更简单的实现。我保留了 return 值，尽管我不明白为什么您需要此方法来 return 一个值。您当然不会在代码中使用它。

int ShiftDown(int itemIdx)
{
    var ret = itemIdx;
    var  maxIdx = _list.Count - 1;
    while (itemIdx < maxIdx)
    {
        var largestChild = itemIdx;
        var leftIdx = 2*itemIdx + 1;

        if (leftIdx > maxIdx)
        {
            // node has no children
            break;
        }

        // left child exists. See if it's larger than its parent.
        if (_list[itemIdx > _list[itemIdx]) 
        {
            largestChild = leftIdx;
        }
        var rightIdx = leftIdx + 1;
        if (rightIdx <= maxIdx && _list[rightIdx] > _list[largestChild])
        {
            // right child exists and is larger than current largest child.
            largestChild = rightIdx;
        }
        if (largestChild != itemIdx)
        {
            Swap(itemIdx, largestChild);
            itemIdx = largestChild;
        }
    }
    return ret;
}

ConcurrentHeap 实现中的问题

Issues in the ConcurrentHeap implementation

c#

concurrency

multithreading

data-structures

max-heap