Использование C # HashSet для решения задач, где равно не равно

Question

Я основываюсь на характеристиках производительности, которые я недавно узнал о Dictionary, поэтому я использую Dictionary<type, bool>, где bool игнорируется, но предположительно я мог бы использовать HashSet.

Например:

Dictionary<bounds, bool> overlap;

class bounds
{
    public float top_left_x, top_left_y, width, height;

    public bool equal(bounds other)
    {
        return upper_left_x + width > other.upper_left_x &&
        upper_left_x < other.upper_left_x + other.width &&
        upper_left_y + height > other.upper_left_y &&
        upper_left_y < other.upper_left_y + other.height;
    }

    public ... GetHashCode()
    {
        ...;
    }
}

Здесь я использую не равенство для проверки на равенство, а вместо этого для перекрытия, что неизбежно раздражает в других местах, но есть причина, по которой я это делаю.

Я предполагаю, что если значение может быть найдено с помощью ключа за O (1) время, то и ключ может быть получен от самого себя.

Таким образом, я мог бы предположительно поместить тысячи границ вперекрываются и делают это:

overlap.ContainsKey(new bounds(...));

Чтобы узнать в O (1) раз, перекрывает ли данная граница какие-либо другие из коллекции.

Я также хотел бы знать, что произойдет, еслиЯ изменяю (x, y) положение границы, возможно, это похоже на удаление, а затем добавление его в набор снова с точки зрения производительности, очень дорого?

Что я помещаю в функцию GetHashCode?

гол

Если это сработает, то я нахожусь• используя механизм такого рода, чтобы выяснить, какие другие границы данной границы перекрываются.

В этой системе перемещается очень мало границ, и новые не добавляются после заполнения коллекции.Недавно добавленные границы должны иметь возможность перекрывать старые.

вывод

Подробнее см. В приведенном ниже отзыве.

В целом это невозможнодля достижения производительности O (1), поскольку, в отличие от значений по умолчанию, проверка на перекрытие не является транзитивной.

Однако, дерево интервалов является хорошим решением.

Answer 1

Отношение равенства * - совершенно неправильное отношение для использования здесь, потому что равенство должно быть отношением эквивалентности .То есть он должен быть рефлексивным - A == A для любого A. Он должен быть симметричным - A == B означает, что B == A. И это должно быть переходный - если A == B и B == C, то A == C.

Вы предлагаете нарушение переходного свойства;«перекрытия» не являются транзитивными отношениями, поэтому «перекрытия» не являются отношениями эквивалентности, и поэтому вы не можете определить равенство как перекрывающиеся .

Вместо того, чтобы пытаться сделать эту опасную вещь, решитенастоящая проблема.Ваша цель состоит в том, чтобы взять набор интервалов, а затем быстро определить, перекрывает ли данный интервал какой-либо из этих интервалов.Желаемая структура данных называется дерево интервалов ; он специально оптимизирован для решения именно этой проблемы, поэтому используйте его . Ни при каких обстоятельствах не пытайтесь использовать хэш-набор в качестве дерева интервалов. Используйте правильный инструмент для задания:

http://wikipedia.org/wiki/Interval_tree

Answer 2

Здесь я использую равенство не для проверки на равенство, а для перекрытия, что наверняка раздражает в других местах, но есть причина, по которой я это делаю.

Я предполагаю, что это означает, что у вас будет сценарий, в котором A.Equals (B) - true, B.Equals (C) - true, а A.Equals (C) - false.Другими словами, ваши Equals не транзитивны.

Это нарушает правила Equals (), и в результате словарь не будет работать для вас.Правило Equals / GetHashCode: (от http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx):

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одинаковое значение.

Есливаши Равные не транзитивны, поэтому вы не можете написать действительный GetHashCode.

Answer 3

Вы не можете использовать Dictionary или HashSet, чтобы проверить, перекрывают ли границы.Чтобы иметь возможность использовать словарь (или хэш-набор), вам нужен метод Equals() и GetHashCode(), который соответствует следующим свойствам:

1. Метод Equals() является эквивалентом отношение
2. a.Equals(b) должно подразумевать a.GetHashCode() == b.GetHashCode()

Вы не можете выполнить ни одно из этих требований, поэтому вы должны использовать другую структуру данных: Интервалдерево .

Answer 4

Если вы используете упомянутый выше подход производного класса , вам потребуется следующее:

public class Bounds
{
    public Point position;
    public Point size; // I know the width and height don't really compose
                       // a point, but this is just for demonstration

    public override int GetHashCode(){...}
}

public class OverlappingBounds : Bounds
{
    public override bool Equals(object other)
    {
        // your implementation here
    }
}

// Usage:
if (_bounds.ContainsKey(new OverlappingBounds(...))){...}

но поскольку метод GetHashCode () должен всегда возвращать одно и то же значение, сложность среды выполнения скорее всего будет равна O (n), а не O (1).

Answer 5

Вы не можете гарантировать O(1) производительность в словаре, где вы настраиваете hashcode calculation. Если я добавлю в метод GetHashCode() какой-либо запрос WebService, который должен контролировать для меня равенство двух предоставленных элементов, ясно, что время никогда не может быть O(1), как ожидалось. Хорошо, это своего рода «крайний случай», но просто чтобы дать представление.

Действуя так, как вам кажется (предполагая, что это даже возможно), imo , вы сводите на нет преимущества, предоставляемые Dictionary<K,V>, поэтому постоянное время восстановления ключа также в больших коллекциях.

Это нужно измерить на разумном количестве объектов, которые у вас есть , но я сначала попробую использовать List<T> как держатель объекта, и сделайте что-то вроде этого:

var bounds = new List<Bound> {.... initialization... }
Bound providedBound = //something. Some data filled in it. 
var overlappedany = bounds.Any<Bound>(b=>return b.Equals(providedBound));