时间戳

首页 > 解决方案 > 元素重复的 SortedSet - 无法删除元素

c# - 元素重复的 SortedSet - 无法删除元素

问题描述

我正在 Unity 中用 C# 实现 A-star 算法。

我需要评估一组Node：

class Node
    {
        public Cell cell;
        public Node previous;
        public int f;
        public int h;

        public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
        {
            this.cell = cell;
            this.previous = previous;
            this.f = f;
            this.h = h;
        }
    }

我有一个SortedSet，它允许我存储几个Node，按h属性排序。不过，我需要能够存储两个具有相同h属性的节点。所以我实现了一个特定的IComparer，以一种允许我按h属性排序的方式，并且仅当两个节点表示完全相同的单元格时才触发相等性。

class ByHCost : IComparer<Node>
    {
        public int Compare(Node n1, Node n2)
        {
            int result = n1.h.CompareTo(n2.h);
            result = (result == 0) ? 1 : result;
            result = (n1.cell == n2.cell) ? 0 : result;
            return result;
        }
    }

我的问题：我很难从我的SortedSet中删除东西（我将其命名为openSet）。这是一个示例：

在算法的某个时刻，我需要根据一些标准从列表中删除一个节点（注意：我使用isCell127变量将调试集中在一个唯一的单元格上）

int removedNodesNb = openSet.RemoveWhere((Node n) => {
    bool isSame = n.cell == candidateNode.cell;
    bool hasWorseCost = n.f > candidateNode.f;

    if(isCell127)
    {
       Debug.Log(isSame && hasWorseCost); // the predicate match exactly one time and debug.log return true
    }

    return isSame && hasWorseCost;
});

if(isCell127)
{
   Debug.Log($"removed {removedNodesNb}"); // 0 nodes where removed
}

在这里， removeWhere 方法似乎找到了匹配项，但没有删除节点。我尝试了另一种方法：

 Node worseNode = openSet.SingleOrDefault(n => {
      bool isSame = n.cell == candidateNode.cell;
      bool hasWorseCost = n.f > candidateNode.f;
      return isSame && hasWorseCost;
 });

 if(isCell127)
 {
      Debug.Log($"does worseNode exists ? {worseNode != null}"); // Debug returns true, it does exist.
 }

 if(worseNode != null)
 {
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10
      }
      openSet.Remove(worseNode);
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10 - It should have been 9.
      }
 }

我认为这个问题与我非常不寻常的 IComparer 有关，但我无法弄清楚问题到底是什么。

另外，我想知道使用自动排序集而不是手动排序列表是否有显着的性能改进，特别是在 A-star 算法用例中。

标签： c#unity3dsortedset

解决方案

我会回答我自己的话题，因为我有一个非常完整的话题。

比较

IComparer 接口的比较需要遵循一些规则。就像@frenchy 说的，我自己的比较被打破了。这是我完全忘记的比较的数学基础（我在这里找到了）：

1) A.CompareTo(A) must return zero.

2) If A.CompareTo(B) returns zero, then B.CompareTo(A) must return zero.

3) If A.CompareTo(B) returns zero and B.CompareTo(C) returns zero, then A.CompareTo(C) must return zero.

4) If A.CompareTo(B) returns a value other than zero, then B.CompareTo(A) must return a value of the opposite sign.

5) If A.CompareTo(B) returns a value x not equal to zero, and B.CompareTo(C) returns a value y of the same sign as x, then A.CompareTo(C) must return a value of the same sign as x and y.

6) By definition, any object compares greater than (or follows) null, and two null references compare equal to each other.

就我而言，规则 4) - 对称性 - 被打破了。

我需要存储具有相同 h 属性的多个节点，还需要按该 h 属性进行排序。所以，当 h 属性相同时，我需要避免相等。

我决定做的不是当 h 比较导致 0（这违反了第 4 条规则）时使用默认值，而是以一种永远不会导致 0 且每个节点实例的唯一值的方式来细化比较。好吧，这个实现可能不是最好的，也许为了一个独特的价值可以做一些更好的事情，但这就是我所做的。

private class Node
{
   private static int globalIncrement = 0;

   public Cell cell;
   public Node previous;
   public int f;
   public int h;
   public int uid;

   public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
   {
       Node.globalIncrement++;

       this.cell = cell;
       this.previous = previous;
       this.f = f;
       this.h = h;
       this.uid = Node.globalIncrement;
   }
}

private class ByHCost : IComparer<Node>
{
   public int Compare(Node n1, Node n2)
   {
       if(n1.cell == n2.cell)
       {
           return 0;
       }

       int result = n1.h.CompareTo(n2.h);
       result = (result == 0) ? n1.uid.CompareTo(n2.uid) : result; // Here is the additional comparison which never lead to 0. Depending on use case and number of object, it would be better to use another system of unique values.
       return result;
   }
}

RemoveWhere 方法

RemoveWhere 使用谓词查看集合，所以我认为它不关心比较。但是 RemoveWhere 在内部使用 Remove 方法，它确实关心比较。因此，即使 RemoveWhere 找到了一个元素，如果您的比较不一致，它也会默默地通过。这是一个非常奇怪的实现，不是吗？

推荐阅读