¿Debería "Set" tener un método Get?

22

Tengamos esta clase de C # (sería casi lo mismo en 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;
   }
}

Como puede ver, la igualdad de dos instancias MyClassdepende Asolo. Por lo tanto, puede haber dos instancias que sean iguales, pero que contengan información diferente en su Bpropiedad.

En una biblioteca de colección estándar de muchos lenguajes (incluidos C # y Java, por supuesto) hay un Set( HashSeten C #), que es una colección, que puede contener como máximo un elemento de cada conjunto de instancias iguales.

Se pueden agregar elementos, eliminar elementos y verificar si el conjunto contiene un elemento. Pero, ¿por qué es imposible obtener un artículo en particular del conjunto?

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

La única forma de recuperar mi artículo es iterar sobre toda la colección y verificar la igualdad de todos los artículos. Sin embargo, esto lleva O(n)tiempo en lugar de O(1)!

No he encontrado ningún lenguaje que admita obtener de un conjunto hasta ahora. Todos los lenguajes "comunes" que conozco (Java, C #, Python, Scala, Haskell ...) parecen estar diseñados de la misma manera: puede agregar elementos, pero no puede recuperarlos. ¿Hay alguna buena razón por la cual todos estos idiomas no admiten algo tan fácil y obviamente útil? No pueden estar completamente equivocados, ¿verdad? ¿Hay algún idioma que lo soporte? Tal vez recuperar un elemento particular de un conjunto está mal, pero ¿por qué?


Hay algunas preguntas SO relacionadas:

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

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

vojta
fuente
12
C ++ std::setadmite la recuperación de objetos, por lo que no todos los lenguajes "comunes" son como usted describe.
Vuelva a instalar Mónica el
17
Si usted afirma (y codifica) que "la igualdad de dos instancias de MyClass depende de A solamente", entonces otra instancia que tenga el mismo valor A y diferente B efectivamente es "esa instancia particular", ya que usted mismo definió que son iguales y las diferencias en B no importan; el contenedor está "permitido" para devolver la otra instancia ya que es igual.
Peteris
77
Historia real: en Java, muchas Set<E>implementaciones son solo Map<E,Boolean>por dentro.
corsiKa
10
hablando con la persona A : "Hola, ¿puedes traer a la Persona A aquí, por favor?"
Brad Thomas
77
Esto rompe la reflexividad ( a == bsiempre cierto) en el caso this.A == null. La if (item == null || this.A == null || item.A == null)prueba está "exagerada" y comprueba demasiado, posiblemente para crear código artificialmente de "alta calidad". Veo este tipo de "sobrecomprobación" y ser excesivamente correcto todo el tiempo en la Revisión de Código.
usr

Respuestas:

66

El problema aquí no es que HashSetcarece de un Getmétodo, es que su código no tiene sentido desde la perspectiva del HashSettipo.

Ese Getmétodo es efectivamente, "consígueme este valor, por favor", a lo que la gente del framework .NET respondería con sensatez, "¿eh? Ya tienes ese valor <confused face />".

Si desea almacenar elementos y luego recuperarlos en función de la coincidencia de otro valor ligeramente diferente, utilice Dictionary<String, MyClass>lo que puede hacer:

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

La información de igualdad se filtra de la clase encapsulada. Si quisiera cambiar el conjunto de propiedades involucradas Equals, tendría que cambiar el código fuera MyClass...

Bueno, sí, pero eso se debe a que MyClassse vuelve loco con el principio del mínimo asombro (POLA). Con esa funcionalidad de igualdad encapsulada, es completamente razonable suponer que el siguiente código es válido:

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.
}

Para evitar esto, MyClassdebe documentarse claramente en cuanto a su extraña forma de igualdad. Una vez hecho esto, ya no está encapsulado y cambiar cómo funciona esa igualdad rompería el principio abierto / cerrado. Ergo, no debería cambiar y, por Dictionary<String, MyClass>lo tanto, es una buena solución para este extraño requisito.

David Arno
fuente
2
@vojta, en ese caso, use Dictionary<MyClass, MyClass>ya que luego obtendrá el valor en función de una clave que use MyClass.Equals.
David Arno
8
Usaría un Dictionary<MyClass, MyClass>suministrado con un apropiado IEqualityComparer<MyClass>, y sacaría la relación de equivalencia de MyClass¿Por qué MyClasstiene que saber sobre esta relación sobre sus instancias?
Caleth
16
@vojta y el comentario allí: " meh. Anular la implementación de iguales para que los objetos no iguales sean" iguales "es el problema aquí. Pedir un método que diga" consígueme el objeto idéntico a este objeto ", y luego esperar que se devuelva un objeto no idéntico parece una locura y es fácil causar problemas de mantenimiento "es perfecto. Ese es a menudo el problema con SO: las respuestas seriamente defectuosas son votadas por personas que no han pensado en los implicantes de su deseo de una solución rápida a su código roto ...
David Arno
66
@DavidArno: aunque inevitable, siempre y cuando persistamos en el uso de lenguajes que distingan entre igualdad e identidad ;-) Si desea canonizar objetos que son iguales pero no idénticos, entonces necesita un método que diga "no me den lo mismo". objetar a este objeto ", pero" tráeme el objeto canónico que es igual a este objeto ". Cualquiera que piense que HashSet.Get en estos idiomas necesariamente significaría "dame el objeto idéntico" ya está gravemente en error.
Steve Jessop
44
Esta respuesta tiene muchas declaraciones generales como ...reasonable to assume.... Todo esto puede ser cierto en el 99% de los casos, pero aún así la capacidad de recuperar un elemento de un conjunto puede ser útil. El código del mundo real no siempre puede adherirse a los principios de POLA, etc. Por ejemplo, si está deduplicando cadenas sin distinción entre mayúsculas y minúsculas, es posible que desee obtener el elemento "maestro". Dictionary<string, string>es una solución, pero cuesta perf.
usr
24

Ya tiene el elemento que está "en" el conjunto; lo pasó como clave.

"Pero no es la instancia a la que llamé Agregar con": Sí, pero usted afirmó específicamente que eran iguales.

A Setes también un caso especial de un Map| Dictionary, con void como tipo de valor (bueno, los métodos inútiles no están definidos, pero eso no importa).

La estructura de datos que está buscando es Dictionary<X, MyClass>donde de Xalguna manera obtiene el As de MyClasses.

El tipo de diccionario C # es bueno en este sentido, ya que le permite proporcionar un IEqualityComparer para las claves.

Para el ejemplo dado, tendría lo siguiente:

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;
   }
}

Usado así:

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
fuente
Hay una serie de situaciones en las que puede ser ventajoso que el código que tiene un objeto que coincide con la clave, lo reemplace con una referencia al objeto utilizado como clave. Por ejemplo, si se sabe que muchas cadenas coinciden con una cadena en una colección hash, reemplazar las referencias a todas esas cadenas con referencias a la de la colección podría ser una ganancia de rendimiento.
supercat
@supercat hoy que se logra con a Dictionary<String, String>.
MikeFHay
@MikeFHay: Sí, pero parece un poco poco elegante tener que almacenar cada referencia de cadena dos veces.
Supercat
2
@supercat Si te refieres a una cadena idéntica , eso es solo una secuencia interna. Usa el material incorporado. Si te refieres a algún tipo de representación "canónica" (una que no se puede lograr usando técnicas simples de cambio de mayúsculas y minúsculas, etc.), parece que básicamente necesitas un índice (en el sentido de que los DB usan el término). No veo un problema con el almacenamiento de cada "forma no canónica" como una clave que se asigna a una forma canónica. (Creo que esto se aplica igualmente bien si la forma "canónica" no es una cadena.) Si esto no es de lo que estás hablando, entonces me has perdido por completo.
jpmc26
1
Personalizado Comparery Dictionary<MyClass, MyClass>es una solución pragmática. En Java, lo mismo se puede lograr mediante TreeSeto TreeMapmás personalizado Comparator.
Markus Kull el
19

Su problema es que tiene dos conceptos contradictorios de igualdad:

  • igualdad real, donde todos los campos son iguales
  • establecer igualdad de membresía, donde solo A es igual

Si usaría la relación de igualdad real en su conjunto, no surge el problema de recuperar un elemento particular del conjunto: para verificar si un objeto está en el conjunto, ya tiene ese objeto. Por lo tanto, nunca es necesario recuperar una instancia particular de un conjunto, suponiendo que esté utilizando la relación de igualdad correcta.

También podríamos argumentar que un conjunto es un tipo de datos abstracto que se define únicamente por la relación S contains xo x is-element-of S("función característica"). Si desea otras operaciones, en realidad no está buscando un conjunto.

Lo que sucede con bastante frecuencia, pero no es un conjunto, es que agrupamos todos los objetos en distintas clases de equivalencia . Los objetos en cada clase o subconjunto son solo equivalentes, no iguales. Podemos representar cada clase de equivalencia a través de cualquier miembro de ese subconjunto, y luego es deseable recuperar ese elemento representativo. Esto sería un mapeo de la clase de equivalencia al elemento representativo.

En C #, un diccionario puede usar una relación de igualdad explícita, creo. De lo contrario, dicha relación se puede implementar escribiendo una clase de envoltura rápida. Pseudocódigo:

// 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)); }
}
amon
fuente
"recuperar una instancia particular de un conjunto" Creo que esto transmitiría lo que quiere decir más directamente si cambia "instancia" a "miembro". Solo una sugerencia menor. =) +1
jpmc26
7

Pero, ¿por qué es imposible obtener un artículo en particular del conjunto?

Porque para eso no están los sets.

Permítanme reformular el ejemplo.

"Tengo un HashSet en el que quiero almacenar objetos MyClass y quiero poder obtenerlos utilizando la propiedad A que es igual a la propiedad A del objeto".

Si reemplaza "HashSet" con "Colección", "objetos" con "Valores" y "propiedad A" con "Clave", la oración se convierte en:

"Tengo una Colección en la que quiero almacenar los Valores de MyClass y quiero poder obtenerlos usando la Clave que es igual a la Clave del objeto".

Lo que se describe es un diccionario. La pregunta real que se hace es "¿Por qué no puedo tratar HashSet como un diccionario?"

La respuesta es que no se usan para lo mismo. La razón para usar un conjunto es garantizar la unicidad de sus contenidos individuales, de lo contrario, podría usar una Lista o una matriz. El comportamiento que se describe en la pregunta es para qué sirve un diccionario. Todos los diseñadores de idiomas no se equivocaron. No proporcionan un método get porque si tiene el objeto y está en el conjunto, son equivalentes, lo que significa que estaría "obteniendo" un objeto equivalente. Argumentar que HashSet debe implementarse de tal manera que pueda "obtener" objetos no equivalentes que haya definido como iguales no es un iniciador cuando los idiomas proporcionan otras estructuras de datos que le permiten hacer eso.

Una nota sobre la OOP y comentarios / respuestas de igualdad. Está bien que la clave de la asignación sea una propiedad / miembro del valor almacenado en un Diccionario. Por ejemplo: tener un Guid como clave y también la propiedad que se usa para el método igual es perfectamente razonable. Lo que no es razonable es tener valores diferentes para el resto de las propiedades. Me parece que si me dirijo en esa dirección, probablemente deba repensar la estructura de mi clase.

Viejo gordo ned
fuente
6

Tan pronto como anule es igual que anular mejor el código hash. Tan pronto como haya hecho esto, su "instancia" nunca debería volver a cambiar su estado interno.

Si no anula equals y hashcode VM, la identidad del objeto se usa para determinar la igualdad. Si coloca este objeto en un Conjunto, podrá encontrarlo nuevamente.

Cambiar un valor de un objeto que se usa para determinar la igualdad conducirá a la imposibilidad de rastreo de este objeto en estructuras basadas en hash.

Entonces un Setter en A es peligroso.

Ahora no tienes B que no participa en igualdad. El problema aquí es semánticamente no técnicamente. Porque técnicamente cambiar B es neutral al hecho de la igualdad. Semánticamente B tiene que ser algo así como una bandera de "versión".

La cuestión es:

Si tiene dos objetos que son iguales a A pero no B, se supone que uno de estos objetos es más nuevo que el otro. Si B no tiene información sobre la versión, esta suposición está oculta en su algoritmo CUANDO decide "sobrescribir / actualizar" este objeto en un Conjunto. Esta ubicación del código fuente donde esto sucede puede no ser obvia, por lo que un desarrollador tendrá dificultades para identificar la relación entre el objeto X y el objeto Y que difiere de X en B.

Si B tiene información de versión, expone la suposición de que anteriormente solo era derivable implícitamente del código. Ahora puede ver que ese objeto Y es una versión más nueva de X.

Piensa en ti: tu identidad permanece toda tu vida, tal vez algunas propiedades cambien (por ejemplo, el color de tu cabello ;-)). Claro, puede suponer que si tiene dos fotos, una con cabello castaño y otra con cabello gris, puede ser más joven en la foto con cabello castaño. ¿Pero tal vez te has teñido el pelo? El problema es: TÚ puedes saber que te coloreaste el cabello. ¿Pueden otros? Para poner esto en un contexto válido, debe introducir la edad de la propiedad (versión). Entonces eres semánticamente explícito e inequívoco.

Para evitar la operación oculta de "reemplazar objetos viejos por objetos nuevos", un Set no debería tener un método get. Si desea un comportamiento como este, debe hacerlo explícito eliminando el objeto antiguo y agregando el nuevo objeto.

Por cierto: ¿Qué debería significar si pasa un objeto que es igual al objeto que desea obtener? Eso no tiene sentido. Mantenga su semántica limpia y no haga esto, aunque técnicamente nadie lo obstaculizará.

oopexpert
fuente
77
"Tan pronto como la anulación sea igual, mejor anulará el código hash. Tan pronto como haya hecho esto, su" instancia "nunca debería volver a cambiar su estado interno". Esa declaración vale +100, justo allí.
David Arno
+1 por señalar los peligros de la igualdad y el código hash dependiendo del estado mutable
Hulk
3

Específicamente en Java, HashSetse implementó inicialmente usando un de HashMaptodos modos, y solo ignorando el valor. Por lo tanto, el diseño inicial no anticipó ninguna ventaja al proporcionar un método get HashSet. Si desea almacenar y recuperar un valor canónico entre varios objetos que son iguales, simplemente use HashMapuno.

No he mantenido al día con estos detalles de implementación, así que no puedo decir si este razonamiento se sigue aplicando en su totalidad en Java, y mucho menos en C #, etc. Pero incluso si HashSetse reimplementado usar menos memoria que HashMap, en cualquier caso, Sería un cambio radical agregar un nuevo método a la Setinterfaz. Por lo tanto, es bastante doloroso obtener una ganancia que no todos consideran que valga la pena tener.

Steve Jessop
fuente
Bueno, en Java podría ser posible proporcionar una defaultimplementación para hacer esto de una manera ininterrumpida. Simplemente no parece un cambio terriblemente útil.
Hulk el
@Hulk: Puedo estar equivocado, pero creo que cualquier implementación predeterminada sería extremadamente ineficiente, ya que, como dice el interrogador, "La única forma de recuperar mi artículo es iterar sobre toda la colección y verificar la igualdad de todos los artículos". Entonces, un buen punto, puede hacerlo de una manera compatible con versiones anteriores, pero agregando un error que la función get resultante solo garantiza que se ejecute en las O(n)comparaciones, incluso si la función hash está dando una buena distribución. Luego, las implementaciones de Setese tipo anulan la implementación predeterminada en la interfaz, incluida HashSet, podrían ofrecer una mejor garantía.
Steve Jessop el
De acuerdo, no creo que sea una buena idea. Sin embargo, habría precedentes para este tipo de comportamiento: List.get (int index) o - para elegir una implementación predeterminada agregada recientemente List.sort . La interfaz proporciona garantías de máxima complejidad, pero algunas implementaciones pueden funcionar mucho mejor que otras.
Hulk el
2

Hay un idioma principal cuyo conjunto tiene la propiedad que desea.

En C ++, std::setes un conjunto ordenado. Tiene un .findmétodo que busca el elemento en función del operador de pedido <o la bool(T,T)función binaria que proporcione. Puede usar find para implementar la operación de obtención que desee.

De hecho, si la bool(T,T)función que proporciona tiene un indicador específico ( is_transparent), puede pasar objetos de un tipo diferente para los que la función tiene sobrecargas. Eso significa que no tiene que pegar los datos "ficticios" en el segundo campo, solo asegúrese de que la operación de pedido que usa pueda ordenar entre los tipos de búsqueda y contenidos.

Esto permite un eficiente:

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

donde my_string_compareentiende cómo ordenar enteros y cadenas sin convertir primero el entero en una cadena (a un costo potencial).

Para unordered_set(el conjunto hash de C ++), no hay un indicador transparente equivalente (todavía). Debe pasar Ta un unordered_set<T>.findmétodo. Podría agregarse, pero los hash requieren ==y un hasher, a diferencia de los conjuntos ordenados que solo requieren un pedido.

El patrón general es que el contenedor hará la búsqueda, luego le dará un "iterador" a ese elemento dentro del contenedor. En ese momento puede obtener el elemento dentro del conjunto, o eliminarlo, etc.

En resumen, no todos los contenedores estándar de los idiomas tienen los defectos que usted describe. Los contenedores basados ​​en iterador de la biblioteca estándar de C ++ no lo hacen, y al menos algunos de los contenedores existían antes que cualquiera de los otros lenguajes que describió, y la capacidad de obtener un resultado aún más eficiente que la forma en que describe incluso se ha agregado. No hay nada malo con su diseño, o querer esa operación; Los diseñadores de los conjuntos que está utilizando simplemente no proporcionaron esa interfaz.

Los contenedores estándar de C ++ se diseñaron para envolver limpiamente las operaciones de bajo nivel del código C enrollado a mano equivalente, que fue diseñado para coincidir con la forma en que podría escribirlo de manera eficiente en el ensamblaje. Sus iteradores son una abstracción de punteros de estilo C. Los lenguajes que menciona se han alejado de los punteros como concepto, por lo que no utilizaron la abstracción del iterador.

Es posible que el hecho de que C ++ no tenga este defecto es un accidente de diseño. La ruta centrada en el iterador significa que para interactuar con un elemento en un contenedor asociativo primero se obtiene un iterador para el elemento, luego se usa ese iterador para hablar sobre la entrada en el contenedor.

El costo es que hay reglas de invalidación de iteración que debe rastrear, y algunas operaciones requieren 2 pasos en lugar de uno (lo que hace que el código del cliente sea más ruidoso). El beneficio es que la abstracción robusta permite un uso más avanzado que los que los diseñadores de API tenían en mente originalmente.

Yakk
fuente