Должен ли «Set» иметь метод Get?

22

Давайте иметь этот класс C # (это будет почти то же самое в Java)

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}

   public override bool Equals(object obj) {
        var item = obj as MyClass;

        if (item == null || this.A == null || item.A == null)
        {
            return false;
        }
        return this.A.equals(item.A);
   }

   public override int GetHashCode() {
        return A != null ? A.GetHashCode() : 0;
   }
}

Как видите, равенство двух экземпляров MyClassзависит Aтолько от. Таким образом, могут быть два экземпляра, которые равны, но содержат различную информацию в своем Bсвойстве.

В стандартной библиотеке коллекций многих языков (включая, конечно, C # и Java) есть Set( HashSetв C #) коллекция, которая может содержать не более одного элемента из каждого набора равных экземпляров.

Можно добавлять элементы, удалять элементы и проверять, содержит ли набор элемент. Но почему невозможно получить конкретный предмет из набора?

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
    //something
}

//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye

Единственный способ получить мой элемент - это перебрать всю коллекцию и проверить все элементы на равенство. Однако O(n)вместо этого требуется время O(1)!

До сих пор я не нашел ни одного языка, который бы поддерживал набор. Все «общие» языки, которые я знаю (Java, C #, Python, Scala, Haskell ...), выглядят одинаково: вы можете добавлять элементы, но не можете их извлекать. Есть ли веская причина, почему все эти языки не поддерживают что-то такое простое и очевидно полезное? Они не могут быть просто не правы, верно? Есть ли языки, которые поддерживают это? Может быть, получение определенного предмета из набора неправильно, но почему?


Есть несколько связанных с этим вопросов SO:

/programming/7283338/getting-an-element-from-a-set

/programming/7760364/how-to-retrieve-actual-item-from-hashsett

Войта
источник
12
C ++ std::setподдерживает поиск объектов, поэтому не все «общие» языки такие, как вы описали.
Восстановите Монику
17
Если вы утверждаете (и кодируете), что «равенство двух экземпляров MyClass зависит только от A», тогда другой экземпляр, имеющий одинаковое значение A и различные B, фактически является «тем конкретным экземпляром», поскольку вы сами определили, что они равны и различия в В не имеют значения; Контейнеру «разрешено» возвращать другой экземпляр, поскольку он равен.
Петерис
7
Правдивая история: в Java многие Set<E>реализации находятся только Map<E,Boolean>внутри.
CorsiKa
10
говоря с человеком А : «Привет, вы можете привести человека А прямо здесь, пожалуйста»
Брэд Томас
7
Это нарушает рефлексивность ( a == bвсегда верно) на всякий случай this.A == null. if (item == null || this.A == null || item.A == null)Тест «перестарались» и проверяет много, возможно , для того , чтобы искусственно создать «высокого качества» кода. Я вижу этот вид «перепроверки» и все время слишком корректен в Code Review.
USR

Ответы:

66

Проблема здесь не в том, что HashSetне хватает Getметода, а в том, что ваш код не имеет смысла с точки зренияHashSet типа.

Этот Getметод, по сути, «принесите мне это значение, пожалуйста», на что люди .NET Framework разумно ответили бы: «А? У вас уже есть это значение<confused face /> ».

Если вы хотите сохранить элементы, а затем извлечь их на основе сопоставления с другим немного другим значением, используйте следующее Dictionary<String, MyClass>:

var mset = new Dictionary<String, MyClass>();
mset.Add("Hello", new MyClass {A = "Hello", B = "Bye"});

var item = mset["Hello"];
Console.WriteLine(item.B); // will print Bye

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

Ну да, но это потому, что не в порядке MyClassс принципом наименьшего удивления (POLA). С этой инкапсулированной функциональностью равенства вполне разумно предположить, что следующий код допустим:

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) 
{
    // this code is unreachable.
}

Чтобы предотвратить это, MyClassнеобходимо четко документировать его странную форму равенства. Сделав это, он больше не заключен в капсулу, и изменение принципа равенства нарушит принцип открытия / закрытия. Поэтому это не должно измениться и, следовательно, Dictionary<String, MyClass>является хорошим решением для этого странного требования.

Дэвид Арно
источник
2
@vojta, в этом случае используйте, Dictionary<MyClass, MyClass>поскольку это тогда выберет значение, основанное на ключе, который использует MyClass.Equals.
Дэвид Арно
8
Я хотел бы использовать Dictionary<MyClass, MyClass>поставляемое с соответствующим IEqualityComparer<MyClass>и вытащить отношение эквивалентности из. MyClassПочему MyClassнужно знать об этом отношении по его экземплярам?
Caleth
16
@vojta и комментарий там: « Мех. Переопределение реализации equals, чтобы неравные объекты были« равными », является проблемой здесь. Запрашиваем метод, который говорит« доставь мне объект, идентичный этому объекту », а затем ожидать, что неидентичный объект будет возвращен, кажется сумасшедшим и легко вызывает проблемы с обслуживанием ». Это часто проблема с SO: за серьезные ошибочные ответы голосуют люди, которые не продумали смысл их желания быстро исправить свой неработающий код ...
Дэвид Арно
6
@DavidArno: отчасти неизбежно, хотя мы продолжаем использовать языки, различающие равенство и идентичность ;-) Если вы хотите канонизировать объекты, которые равны, но не идентичны, то вам нужен метод, который говорит: «не получайте мне идентичное» возражать против этого объекта », но« достань мне канонический объект, равный этому объекту ». Любой, кто думает, что HashSet.Get на этих языках обязательно будет означать «доставь мне идентичный объект», уже серьезно ошибается.
Стив Джессоп
4
Этот ответ имеет много общих утверждений, таких как ...reasonable to assume.... Все это может быть правдой в 99% случаев, но возможность извлечения предмета из набора может оказаться полезной. Код реального мира не всегда может следовать принципам POLA и т. Д. Например, если вы дедуплицируете строки без учета регистра, вы можете получить «главный» элемент. Dictionary<string, string>это обходной путь, но стоит перф.
USR
24

У вас уже есть предмет, который находится «в» наборе - вы передали его в качестве ключа.

«Но это не тот случай, когда я назвал« Добавить »» - да, но вы специально утверждали, что они были равны.

A Setтакже является частным случаем Map|Dictionaryс void в качестве типа значения (ну, бесполезные методы не определены, но это не имеет значения).

Структура данных, которую вы ищете, - это то, Dictionary<X, MyClass>откуда Xкаким-то образом получается As из MyClasses.

Тип C # Dictionary хорош в этом отношении, так как он позволяет вам предоставлять IEqualityComparer для ключей.

Для приведенного примера у меня будет следующее:

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}
}

public class MyClassEquivalentAs : IEqualityComparer<MyClass>{
   public override bool Equals(MyClass left, MyClass right) {
        if (Object.ReferenceEquals(left, null) && Object.ReferenceEquals(right, null))
        {
            return true;
        }
        else if (Object.ReferenceEquals(left, null) || Object.ReferenceEquals(right, null))
        {
            return false;
        }
        return left.A == right.A;
   }

   public override int GetHashCode(MyClass obj) {
        return obj?.A != null ? obj.A.GetHashCode() : 0;
   }
}

Используется таким образом:

var mset = new Dictionary<MyClass, MyClass>(new MyClassEquivalentAs());
var bye = new MyClass {A = "Hello", B = "Bye"};
var seeyou = new MyClass {A = "Hello", B = "See you"};
mset.Add(bye);

if (mset.Contains(seeyou)) {
    //something
}

MyClass item = mset[seeyou];
Console.WriteLine(item.B); // prints Bye
Caleth
источник
Существует ряд ситуаций, когда для кода, который имеет объект, соответствующий ключу, может быть выгодно заменить его ссылкой на объект, используемый в качестве ключа. Например, если известно, что многие строки соответствуют строке в хешированной коллекции, замена ссылок на все эти строки ссылками на строку в коллекции может привести к выигрышу в производительности.
суперкат
@supercat сегодня, что достигается с Dictionary<String, String>.
MikeFHay
@MikeFHay: Да, но кажется немного неуместным хранить каждую строковую ссылку дважды.
суперкат
2
@supercat Если вы имеете в виду идентичную строку, это просто интернирование строк. Используйте встроенные вещи. Если вы имеете в виду какое-то «каноническое» представление (которое не может быть достигнуто с помощью простых техник смены регистра и т. Д.), Это звучит так, как будто вам в основном нужен индекс (в том смысле, что БД используют этот термин). Я не вижу проблемы с хранением каждой "неканонической формы" в качестве ключа, который отображается в каноническую форму. (Я думаю, что это применимо одинаково хорошо, если «каноническая» форма не является строкой.) Если это не то, о чем вы говорите, то вы полностью потеряли меня.
jpmc26
1
Обычай Comparerи Dictionary<MyClass, MyClass>является прагматичным решением. В Java то же самое может быть достигнуто TreeSetили TreeMapплюс пользовательский Comparator.
Маркус Кулл
19

Ваша проблема в том, что у вас есть два противоречивых понятия равенства:

  • фактическое равенство, где все поля равны
  • установить равенство членства, где только A равен

Если бы вы использовали фактическое отношение равенства в вашем наборе, проблема извлечения определенного элемента из набора не возникает - чтобы проверить, находится ли объект в наборе, у вас уже есть этот объект. Поэтому никогда не требуется извлекать конкретный экземпляр из набора, если вы используете правильное отношение равенства.

Мы также можем утверждать, что набор - это абстрактный тип данных, который определяется исключительно отношением S contains xили x is-element-of S(«характеристическая функция»). Если вы хотите другие операции, вы на самом деле не ищете набор.

То, что происходит довольно часто, но не является множеством, - это то, что мы группируем все объекты в отдельные классы эквивалентности . Объекты в каждом таком классе или подмножестве являются только эквивалентными, а не равными. Мы можем представлять каждый класс эквивалентности через любой член этого подмножества, и тогда становится желательным получить этот представляющий элемент. Это будет отображение класса эквивалентности на представительный элемент.

Я думаю, что в C # словарь может использовать явное отношение равенства. В противном случае такое отношение можно реализовать, написав быстрый класс-обертку. псевдокод:

// The type you actually want to store
class MyClass { ... }

// A equivalence class of MyClass objects,
// with regards to a particular equivalence relation.
// This relation is implemented in EquivalenceClass.Equals()
class EquivalenceClass {
  public MyClass instance { get; }
  public override bool Equals(object o) { ... } // compare instance.A
  public override int GetHashCode() { ... } // hash instance.A
  public static EquivalenceClass of(MyClass o) { return new EquivalenceClass { instance = o }; }
}

// The set-like object mapping equivalence classes
// to a particular representing element.
class EquivalenceHashSet {
  private Dictionary<EquivalenceClass, MyClass> dict = ...;
  public void Add(MyClass o) { dict.Add(EquivalenceClass.of(o), o)}
  public bool Contains(MyClass o) { return dict.Contains(EquivalenceClass.of(o)); }
  public MyClass Get(MyClass o) { return dict.Get(EquivalenceClass.of(o)); }
}
Амон
источник
«извлекать конкретный экземпляр из набора». Я думаю, это дало бы то, что вы имеете в виду, более прямо, если бы вы изменили «экземпляр» на «член». Просто незначительное предложение. =) +1
jpmc26
7

Но почему невозможно получить конкретный предмет из набора?

Потому что это не то, для чего наборы.

Позвольте мне перефразировать пример.

«У меня есть HashSet, в котором я хочу хранить объекты MyClass, и я хочу иметь возможность получить их, используя свойство A, равное свойству объекта A».

Если заменить «HashSet» на «Collection», «objects» на «Values» и «property A» на «Key», предложение становится:

«У меня есть коллекция, в которой я хочу хранить значения MyClass, и я хочу получить их, используя ключ, равный ключу объекта».

Описывается словарь. Фактический вопрос, который задают: «Почему я не могу рассматривать HashSet как словарь?»

Ответ в том, что они не используются для одной и той же вещи. Причина использования набора состоит в том, чтобы гарантировать уникальность его индивидуального содержимого, в противном случае вы можете просто использовать List или массив. Поведение, описываемое в этом вопросе, предназначено для словаря. Все дизайнеры языка не облажались. Они не предоставляют метод get, потому что если у вас есть объект, и он находится в наборе, они эквивалентны, что означает, что вы «получаете» эквивалентный объект. Утверждение, что HashSet должен быть реализован таким образом, чтобы вы могли «получить» неэквивалентные объекты, которые вы определили как равные, не является началом, когда языки предоставляют другие структуры данных, которые позволяют вам это делать.

Заметка об ООП и равенстве комментариев / ответов. Это нормально, когда ключ сопоставления является свойством / членом хранимого значения в словаре. Например: иметь в качестве ключа Guid, а также свойство, которое используется для метода equals, вполне разумно. Что не разумно, так это иметь разные значения для остальных свойств. Я считаю, что если я иду в этом направлении, мне, вероятно, нужно переосмыслить структуру своего класса.

Старый Толстый Нед
источник
6

Как только вы переопределите равно, вам лучше переопределить хэш-код. Как только вы это сделаете, ваш «экземпляр» никогда не должен снова менять внутреннее состояние.

Если вы не переопределяете equals и для определения равенства используется хеш-код, то идентификатор объекта VM. Если вы поместите этот объект в набор, вы сможете найти его снова.

Изменение значения объекта, используемого для определения равенства, приведет к невозможности отслеживания этого объекта в структурах на основе хеша.

Так что сеттер на А опасен.

Теперь у вас нет B, который не участвует в равенстве. Проблема здесь семантически, а не технически. Потому что технически изменение B нейтрально для факта равенства. Семантически B должен быть чем-то вроде флага «версия».

Дело в том:

Если у вас есть два объекта, которые равны A, но не B, у вас есть предположение, что один из этих объектов новее, чем другой. Если у B нет информации о версии, это предположение скрыто в вашем алгоритме, когда вы решаете «перезаписать / обновить» этот объект в наборе. Такое расположение исходного кода, где это происходит, может быть неочевидным, поэтому разработчику будет непросто определить отношение между объектом X и объектом Y, которое отличается от X в B.

Если B имеет информацию о версии, вы выставляете предположение, что ранее он был только неявным образом выводим из кода. Теперь вы можете видеть, что объект Y является более новой версией X.

Подумайте о себе: ваша личность остается на всю жизнь, возможно, некоторые свойства меняются (например, цвет ваших волос ;-)). Конечно, вы можете предположить, что если у вас есть две фотографии, одна с каштановыми волосами, другая с седыми, то вы можете быть моложе на фотографии с коричневыми волосами. Но, может быть, вы покрасили волосы? Проблема в том, что вы можете знать, что вы покрасили волосы. Могут другие? Чтобы поместить это в действительный контекст, вы должны ввести свойство age (версию). Тогда вы семантически откровенны и однозначны.

Чтобы избежать скрытой операции «замена старого на новый объект», в Set не должно быть метода get. Если вам нужно такое поведение, вы должны сделать его явным, удалив старый объект и добавив новый объект.

Кстати: что это должно означать, если вы передаете объект, равный объекту, который вы хотите получить? Это не имеет смысла. Держите семантику в чистоте и не делайте этого, хотя технически никто не будет вам мешать.

oopexpert
источник
7
«Как только вы переопределите равные, вам лучше переопределить хеш-код. Как только вы это сделаете, ваш« экземпляр »никогда не должен снова менять внутреннее состояние». Это утверждение стоит +100, прямо здесь.
Дэвид Арно
+1 за указание на опасность равенства и хэш-кода в зависимости от изменяемого состояния
Hulk
3

В частности, в Java HashSetизначально был реализован с использованием в HashMapлюбом случае, и просто игнорируя значение. Таким образом, первоначальный дизайн не предполагал каких-либо преимуществ в предоставлении метода get HashSet. Если вы хотите сохранить и извлечь каноническое значение среди различных объектов, которые равны, то вы просто используете HashMapсами.

Я не был в курсе таких подробностей реализации, поэтому не могу сказать, применимы ли эти рассуждения в полной мере в Java, не говоря уже о C # и т. Д. Но даже если бы HashSetбыло переопределено использовать меньше памяти, чем HashMap, в любом случае, было бы серьезным изменением добавить новый метод в Setинтерфейс. Так что это довольно большая боль для выгоды, которую не все считают достойной.

Стив Джессоп
источник
Что ж, в Java можно было бы обеспечить реализацию для defaultнепрерывной работы. Это просто не кажется очень полезным изменением.
Халк
@ Халк: Я могу ошибаться, но я думаю, что любая реализация по умолчанию была бы ужасно неэффективна, поскольку, как говорит спрашивающий: «Единственный способ извлечь мой элемент - это перебрать всю коллекцию и проверить все элементы на равенство». Итак, хороший момент, вы можете сделать это обратно совместимым способом, но добавив уловку, что получающаяся функция get гарантирует выполнение только в O(n)сравнениях, даже если хеш-функция дает хорошее распределение. Тогда реализации Setэтого переопределения реализации по умолчанию в интерфейсе, в том числе HashSet, могут дать лучшую гарантию.
Стив Джессоп
Согласился - не думаю, что это будет хорошая идея. Тем не менее, для такого поведения были бы приоритеты - List.get (int index) или - для выбора реализации по умолчанию, добавленной недавно List.sort . Интерфейс обеспечивает максимальные гарантии сложности, но некоторые реализации могут работать намного лучше, чем другие.
Халк
2

Существует основной язык, набор которого имеет свойство, которое вы хотите.

В C ++ std::setэто упорядоченный набор. У него есть .findметод, который ищет элемент на основе предоставленного вами оператора упорядочения <или двоичной bool(T,T)функции. Вы можете использовать find для реализации нужной вам операции get.

Фактически, если bool(T,T)указанная вами функция имеет определенный флаг ( is_transparent), вы можете передавать объекты другого типа, для которых функция имеет перегрузки. Это означает, что вам не нужно вставлять «пустые» данные во второе поле, просто убедитесь, что используемая вами операция упорядочения может упорядочивать между поиском и вложенными типами.

Это позволяет эффективно:

std::set< std::string, my_string_compare > strings;
strings.find( 7 );

где my_string_compareпонимает, как упорядочить целые числа и строки без предварительного преобразования целого числа в строку (с потенциальной ценой).

Для unordered_set(хеш-набор C ++) не существует эквивалентного прозрачного флага (пока). Вы должны перейти Tк unordered_set<T>.findметоду. Его можно добавить, но для хэшей требуется ==и хеш, в отличие от упорядоченных наборов, которые просто требуют упорядочения.

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

Короче говоря, не у всех стандартных контейнеров есть недостатки, которые вы описываете. Контейнеры, основанные на итераторах стандартной библиотеки C ++, отсутствуют, и, по крайней мере, некоторые из контейнеров существовали раньше, чем любой из других языков, которые вы описали, и возможность сделать получение еще эффективнее, чем вы описали, была даже добавлена. Нет ничего плохого в вашем дизайне или желании этой операции; дизайнеры наборов, которые вы используете, просто не предоставили этот интерфейс.

Стандартные контейнеры C ++, предназначенные для чистой обертки низкоуровневых операций эквивалентного свернутого вручную кода C, который был разработан, чтобы соответствовать тому, как вы могли бы эффективно написать его в сборке. Его итераторы являются абстракцией указателей в стиле C. Все языки, о которых вы упомянули, отошли от указателей как понятия, поэтому они не использовали абстракцию итератора.

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

Стоимость состоит в том, что есть правила аннулирования итерации, которые вы должны отслеживать, и некоторые операции требуют 2 шага вместо одного (что делает клиентский код более шумным). Преимущество заключается в том, что надежная абстракция позволяет более расширенное использование, чем те, которые изначально задумывались дизайнерами API.

Yakk
источник