0

这是我的 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是原子操作。

4

2 回答 2

3

我可以指出几个问题：

  1. Count,get => Interlocked.Read(ref _itemCount); 你不用锁。因此，如果一个线程在另一个线程中调用它时，这很容易返回一个不正确的值，Push就在添加新元素和更新计数之间。也一样Pop。因此，IsFull并且IsEmpty也会失败。

  2. Peek- 你读Count了锁，所以它首先确定堆中有一个项目并尝试获取它，但还没有。

  3. ReadAll看起来坏了。除非我弄错了，否则它总是会返回一个空列表。您正确地尝试退回副本，但我没有看到您制作副本。你复制参考。

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

于 2019-12-17T13:59:59.223 回答
1

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

如果他们都不在场，那么你知道那left是在场的那个。在适当的堆中，因为它是左填充的，所以如果一个节点没有左孩子，它就不能有右孩子。

下面是一个更简单的实现。我维护了返回值，虽然我不明白为什么你需要这个方法来返回一个值。您当然不会在代码中使用它。

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;
}
于 2019-12-18T05:12:16.130 回答