具有元素重复的 SortedSet - 无法删除元素

Question

我正在 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 算法用例中。

Answer 1

如果我写你的测试你会做：

          n1.h < n2.h
          n1.cell = n2.cell -> final result = 0

          n1.h > n2.h
          n1.cell = n2.cell -> final result = 0 

          n1.h = n2.h
          n1.cell != n2.cell -> final result = 1      

          n1.h < n2.h
          n1.cell != n2.cell -> final result = -1  

          n1.h > n2.h
          n1.cell != n2.cell -> final result = 1

当你的 h 值相等（测试编号 3）时，你选择始终获得相同的结果 -> 1。所以你必须对单元格进行另一次测试以澄清位置是不好的，因为存在混淆与其他给出相同结果的测试（测试编号 5）

所以我可以用样本进行测试，但我很确定你破坏了排序。

因此，如果您澄清测试，我建议您将 Linq 与列表一起使用...它的最佳性能。

Answer 2

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

比较

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

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 找到了一个元素，如果您的比较不一致，它也会默默地通过。这是一个非常奇怪的实现，不是吗？

具有元素重复的 SortedSet - 无法删除元素

SortedSet with element duplication - can't remove element

c#

sortedset

unity3d