Блог

Главная - Вопросы по программированию - IEqualityComparer, который найдет следующий ближайший элемент

IEqualityComparer, который найдет следующий ближайший элемент

#c# #comparator #binary-search

#c# #Компаратор #двоичный поиск

Вопрос:

Можно ли написать a IEqualityComparer для a SortedList <double, GameObject> , который вернет «следующий ближайший» double ?

Например;

 SortedList <double, GameObject> list = new SortedList <double, GameObject>(new MyComparer());
list[0.00] = go1;
list[1.00] = go2;

list[0.55]; // should return go2. Ie, find the next-closest key, value pair 
            // and return that

Возможно ли это сделать? Использую ли я a IEqualityComparer для достижения этого?

 #region Comparator
public class MyComparer : IEqualityComparer<double> // should this be Pair<double, GameObject> instead?
{
    public bool Equals(double a, double b)
    {
        return (Math.Abs(a-b) <= 0.01);
    }

}
#endregion

PS: Если я добавлю свой собственный пользовательский comparer ( IEqualityComparer ) — останется ли мой алгоритм сортировки и поиска SortedList по-прежнему в виде двоичного поиска? Изменив средство сравнения, я только что сделал SortedList его намного менее эффективным? Я только что сделал lookup и insertion менее эффективен?

Комментарии:

1. Алгоритм сортировки варьируется в зависимости от . Версия NET Framework. Средство сравнения равенства не имеет ничего общего с сортировкой. Сортировка использует IComparer<t> (или косвенно IComparer, IComparable<T>, IComparable)

2. Вы должны быть очень осторожны, делая подобные вещи, изменяя значение подобных интерфейсов и, в частности, равенство. Я бы настоятельно рекомендовал вам не делать этого, независимо от того, какой интерфейс вы в конечном итоге измените. В качестве примера, если x == y и y == z тогда у вас должно быть x == z , но если вы начнете делать «достаточно близкое» сравнение, вы можете этого не допустить. Например, если «достаточно близко» равно 0,5 или меньше между, то 0.5 == 1.0 и 1.0 == 1.5 но 0.5 != 1.5 (с вашими новыми операторами == и !=, то есть). Не делайте этого! Найдите другой способ выражения своего намерения.

Ответ №1:

Пожалуйста, используйте следующую программу для этого исправления. и да, будут небольшие накладные расходы из-за округления. если вы получите 0.45, он вернет вам A, а 1.55 вернет вам C.

   class SortedListTest
    {
        public static void Test()
        {
            var list = new SortedList<double, string>(new MyComparer());

            list[0.00] = "A";
            list[1.00] = "B";
            list[2.00] = "C";

            Console.WriteLine(list[0.55]);
        }
        private static void Main()
        {
            SortedListTest.Test();
        }
    }

    internal class MyComparer : IComparer<double>
    {
        public int Compare(double x, double y)
        {
            return (int) (Math.Round(x) - Math.Round(y));
        }

    }

Комментарии:

1. Вы получите исключение, если ваш список не содержит ключа, до которого вы округляете.

2. @KajalSinha спасибо за ответ, но это будет работать только для целых чисел.

3. @Jake M: это будет работать для double, и вы сравниваете double. Вы даже можете сравнивать с десятичным знаком, если хотите. Метод сравнения возвращает либо меньше 0, либо 0, либо больше 0. Меньше 0 означает выбор нижней границы во время сравнения, а больше 0 означает выбор верхней границы.

Ответ №2:

Я сильно сомневаюсь, что это возможно. Equals Ваш метод IQualityComparer даже не вызывается при индексации SortedList с помощью double!

Я бы рекомендовал создать новый класс, который наследует от SortedList и переопределяет Indexer ( [] ) .

Этот пример вернет значение следующего по старшинству ключа. Если нет более высокого ключа, то он вернет значение самого высокого ключа:

    class Program
   {
      static void Main(string[] args)
      {
         var list = new MySortedList();

         list[0.5] = "A";
         list[1.0] = "B";
         list[3.0] = "C";

         Console.WriteLine(list[-0.6]); // writes: A
         Console.WriteLine(list[0.1]); // writes: A
         Console.WriteLine(list[0.6]); // writes: B
         Console.WriteLine(list[1.1]); // writes: C
         Console.WriteLine(list[1.2]); // writes: C
         Console.WriteLine(list[4.0]); // writes: C
      }
   }

   class MySortedList : SortedList<double, string>
   {
      new public string this[double key]
      {
         get
         {
            double newKey = Keys.FirstOrDefault(p => p >= key);
            if (!Keys.Contains(newKey)) newKey = Keys.Max();
            return base[newKey];
         }
         set
         {
            base[key] = value;
         }
      }
   }