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 MyClass
depende A
solo. Por lo tanto, puede haber dos instancias que sean iguales, pero que contengan información diferente en su B
propiedad.
En una biblioteca de colección estándar de muchos lenguajes (incluidos C # y Java, por supuesto) hay un Set
( HashSet
en 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
fuente
std::set
admite la recuperación de objetos, por lo que no todos los lenguajes "comunes" son como usted describe.Set<E>
implementaciones son soloMap<E,Boolean>
por dentro.a == b
siempre cierto) en el casothis.A == null
. Laif (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.Respuestas:
El problema aquí no es que
HashSet
carece de unGet
método, es que su código no tiene sentido desde la perspectiva delHashSet
tipo.Ese
Get
mé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:Bueno, sí, pero eso se debe a que
MyClass
se 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:Para evitar esto,
MyClass
debe 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, porDictionary<String, MyClass>
lo tanto, es una buena solución para este extraño requisito.fuente
Dictionary<MyClass, MyClass>
ya que luego obtendrá el valor en función de una clave que useMyClass.Equals
.Dictionary<MyClass, MyClass>
suministrado con un apropiadoIEqualityComparer<MyClass>
, y sacaría la relación de equivalencia deMyClass
¿Por quéMyClass
tiene que saber sobre esta relación sobre sus instancias?...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.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
Set
es también un caso especial de unMap
|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 deX
alguna 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:
Usado así:
fuente
Dictionary<String, String>
.Comparer
yDictionary<MyClass, MyClass>
es una solución pragmática. En Java, lo mismo se puede lograr medianteTreeSet
oTreeMap
más personalizadoComparator
.Su problema es que tiene dos conceptos contradictorios de igualdad:
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 x
ox 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:
fuente
Porque para eso no están los sets.
Permítanme reformular el ejemplo.
Si reemplaza "HashSet" con "Colección", "objetos" con "Valores" y "propiedad A" con "Clave", la oración se convierte en:
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.
fuente
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á.
fuente
Específicamente en Java,
HashSet
se implementó inicialmente usando un deHashMap
todos modos, y solo ignorando el valor. Por lo tanto, el diseño inicial no anticipó ninguna ventaja al proporcionar un método getHashSet
. Si desea almacenar y recuperar un valor canónico entre varios objetos que son iguales, simplemente useHashMap
uno.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
HashSet
se reimplementado usar menos memoria queHashMap
, en cualquier caso, Sería un cambio radical agregar un nuevo método a laSet
interfaz. Por lo tanto, es bastante doloroso obtener una ganancia que no todos consideran que valga la pena tener.fuente
default
implementación para hacer esto de una manera ininterrumpida. Simplemente no parece un cambio terriblemente útil.O(n)
comparaciones, incluso si la función hash está dando una buena distribución. Luego, las implementaciones deSet
ese tipo anulan la implementación predeterminada en la interfaz, incluidaHashSet
, podrían ofrecer una mejor garantía.Hay un idioma principal cuyo conjunto tiene la propiedad que desea.
En C ++,
std::set
es un conjunto ordenado. Tiene un.find
método que busca el elemento en función del operador de pedido<
o labool(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:
donde
my_string_compare
entiende 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 pasarT
a ununordered_set<T>.find
mé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.
fuente