SortedSet с дублированием элемента - невозможно удалить элемент

Question

Я работаю над реализацией алгоритма A-star в C# в Unity.

Мне нужно оценить коллекцию 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 . Поэтому я реализовал спецификатор c 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

Я отвечу на свою собственную топи c, потому что у меня довольно полная.

Сравнение

Необходимо выполнить сравнение интерфейса 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 с уникальным значением экземпляра узла foreach. Ну, эта реализация, вероятно, не самая лучшая, может быть, есть что-то лучше для уникального значения, но вот что я сделал.

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 обнаружил один элемент, если ваше сравнение не соответствует действительности, оно молча пройдет. Это довольно странная реализация, нет?

Answer 2

Если я пишу свой тест, вы делаете:

          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 со списком ... его лучшую производительность.