Vamos ter essa classe C # (seria quase a mesma em 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 você pode ver, a igualdade de duas instâncias de MyClass
depende A
apenas. Portanto, pode haver duas instâncias iguais, mas mantendo informações diferentes em suas B
propriedades.
Em uma biblioteca de coleções padrão de muitas linguagens (incluindo C # e Java, é claro), existe uma Set
( HashSet
em C #), uma coleção que pode conter no máximo um item de cada conjunto de instâncias iguais.
Pode-se adicionar itens, remover itens e verificar se o conjunto contém um item. Mas por que é impossível obter um item específico do 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
A única maneira de recuperar meu item é percorrer toda a coleção e verificar a igualdade de todos os itens. No entanto, isso leva O(n)
tempo em vez de O(1)
!
Não encontrei nenhum idioma compatível com o conteúdo de um conjunto até agora. Todas as linguagens "comuns" que conheço (Java, C #, Python, Scala, Haskell ...) parecem ter sido projetadas da mesma maneira: você pode adicionar itens, mas não pode recuperá-los. Existe alguma boa razão para que todos esses idiomas não suportem algo tão fácil e obviamente útil? Eles não podem estar todos errados, certo? Existem idiomas que o suportam? Talvez a recuperação de um item específico de um conjunto esteja errada, mas por quê?
Existem algumas perguntas relacionadas ao SO:
/programming/7283338/getting-an-element-from-a-set
/programming/7760364/how-to-retrieve-actual-item-from-hashsett
fonte
std::set
oferece suporte à recuperação de objetos, portanto nem todas as linguagens "comuns" são como você descreve.Set<E>
implementações são apenasMap<E,Boolean>
internas.a == b
sempre verdadeira) no casothis.A == null
. Oif (item == null || this.A == null || item.A == null)
teste é "exagerado" e verifica muito, possivelmente para criar código artificialmente "de alta qualidade". Vejo esse tipo de "verificação excessiva" e excessivamente correta o tempo todo na Revisão de Código.Respostas:
O problema aqui não é que
HashSet
falta umGet
método, é que seu código não faz sentido da perspectiva doHashSet
tipo.Esse
Get
método é efetivamente "obtenha-me esse valor, por favor", ao qual o pessoal da estrutura .NET responderia sensatamente: "eh? Você já tem esse valor<confused face />
".Se você deseja armazenar itens e recuperá-los com base em outro valor ligeiramente diferente, use
Dictionary<String, MyClass>
o que pode fazer:Bem, sim, mas isso
MyClass
ocorre porque se diverte com o princípio do mínimo espanto (POLA). Com essa funcionalidade de igualdade encapsulada, é completamente razoável supor que o seguinte código é válido:Para evitar isso,
MyClass
precisa ser claramente documentado quanto à sua forma ímpar de igualdade. Tendo feito isso, não está mais encapsulado e mudando como essa igualdade funciona quebraria o princípio de aberto / fechado. Portanto, não deve mudar e, portanto,Dictionary<String, MyClass>
é uma boa solução para esse requisito estranho.fonte
Dictionary<MyClass, MyClass>
como ele buscará o valor com base em uma chave que usaMyClass.Equals
.Dictionary<MyClass, MyClass>
fornecido com um apropriadoIEqualityComparer<MyClass>
e extrairia a relação de equivalência deMyClass
Por queMyClass
precisa saber sobre essa relação em suas instâncias?...reasonable to assume...
. Tudo isso pode ser verdade em 99% dos casos, mas ainda assim a capacidade de recuperar um item de um conjunto pode ser útil. O código do mundo real nem sempre pode aderir aos princípios da POLA etc. Por exemplo, se você estiver deduplicando cadeias sem distinção entre maiúsculas e minúsculas, convém obter o item "mestre".Dictionary<string, string>
é uma solução alternativa, mas custa perf.Você já tem o item que está "no" conjunto - você o passou como chave.
"Mas não foi o caso em que chamei Adicionar com" - Sim, mas você afirmou especificamente que eles eram iguais.
A
Set
também é um caso especial de umMap
|Dictionary
, com nulo como o tipo de valor (bem, os métodos inúteis não estão definidos, mas isso não importa).A estrutura de dados que você está procurando é um local
Dictionary<X, MyClass>
onde, deX
alguma forma, tira o As das MyClasses.O tipo de dicionário C # é bom nesse sentido, pois permite fornecer um IEqualityComparer para as chaves.
Para o exemplo dado, eu teria o seguinte:
Utilizado assim:
fonte
Dictionary<String, String>
.Comparer
eDictionary<MyClass, MyClass>
é uma solução pragmática. Em Java, o mesmo pode ser alcançado porTreeSet
ouTreeMap
mais personalizadoComparator
.Seu problema é que você tem dois conceitos contraditórios de igualdade:
Se você usasse a relação de igualdade real em seu conjunto, o problema de recuperar um item específico do conjunto não surgiria - para verificar se um objeto está no conjunto, você já o possui. Portanto, nunca é necessário recuperar uma instância específica de um conjunto, supondo que você esteja usando a relação de igualdade correta.
Também poderíamos argumentar que um conjunto é um tipo de dados abstrato que é definido exclusivamente pela relação
S contains x
oux is-element-of S
("função característica"). Se você deseja outras operações, não está procurando um conjunto.O que acontece com bastante frequência - mas o que não é um conjunto - é que agrupamos todos os objetos em classes de equivalência distintas . Os objetos em cada classe ou subconjunto são apenas equivalentes, não iguais. Podemos representar cada classe de equivalência através de qualquer membro desse subconjunto e, em seguida, torna-se desejável recuperar esse elemento representativo. Isso seria um mapeamento da classe de equivalência para o elemento representativo.
Em C #, um dicionário pode usar uma relação explícita de igualdade, eu acho. Caso contrário, essa relação poderá ser implementada escrevendo uma classe de wrapper rápido. Pseudo-código:
fonte
Porque não é para isso que servem os sets.
Deixe-me reformular o exemplo.
Se substituir "HashSet" por "Coleção", "objetos" por "Valores" e "propriedade A" por "Chave", a sentença se tornará:
O que está sendo descrito é um dicionário. A pergunta real é "Por que não posso tratar o HashSet como um dicionário?"
A resposta é que eles não são usados para a mesma coisa. O motivo para usar um conjunto é garantir a exclusividade de seu conteúdo individual; caso contrário, você pode simplesmente usar uma lista ou uma matriz. O comportamento descrito na pergunta é para que serve um dicionário. Todos os designers de idiomas não estragaram tudo. Eles não fornecem um método get, porque se você tiver o objeto e ele estiver no conjunto, eles serão equivalentes, o que significa que você estaria "obtendo" um objeto equivalente. Argumentar que o HashSet deve ser implementado de tal maneira que você possa "obter" objetos não equivalentes que você definiu como iguais não é um iniciador quando os idiomas fornecem outras estruturas de dados que permitem que você faça isso.
Uma observação sobre o POO e comentários / respostas sobre igualdade. Não há problema em ter a chave do mapeamento como uma propriedade / membro do valor armazenado em um Dicionário. Por exemplo: ter um Guid como chave e também a propriedade usada para o método equals é perfeitamente razoável. O que não é razoável é ter valores diferentes para o restante das propriedades. Acho que, se estou indo nessa direção, provavelmente preciso repensar minha estrutura de classes.
fonte
Assim que você substituir, é melhor substituir o código de hash. Assim que você fizer isso, sua "instância" nunca deverá mudar de estado interno novamente.
Se você não substituir iguais e a identidade do objeto da VM com código hash, será usada para determinar a igualdade. Se você colocar esse objeto em um Conjunto, poderá encontrá-lo novamente.
Alterar um valor de um objeto usado para determinar a igualdade levará à impossibilidade de rastreabilidade desse objeto em estruturas baseadas em hash.
Portanto, um setter em A é perigoso.
Agora você não tem B que não participa da igualdade. O problema aqui é semanticamente não tecnicamente. Porque mudar tecnicamente B é neutro ao fato de igualdade. Semanticamente, B deve ser algo como um sinalizador de "versão".
O ponto é:
Se você tiver dois objetos iguais a A, mas não B, você assume que um desses objetos é mais novo que o outro. Se B não possui informações de versão, essa suposição está oculta no seu algoritmo. Quando você decide "sobrescrever / atualizar" esse objeto em um conjunto. Esse local do código-fonte onde isso acontece pode não ser óbvio, portanto, o desenvolvedor terá dificuldade em identificar a relação entre o objeto X e o objeto Y que difere de X em B.
Se B tiver informações de versão, você expõe a suposição de que anteriormente era apenas implicitamente derivável do código. Agora você pode ver, esse objeto Y é uma versão mais recente do X.
Pense em si mesmo: sua identidade permanece a vida toda, talvez algumas propriedades mudem (por exemplo, cor do seu cabelo ;-)). Você pode supor que, se você tiver duas fotos, uma com cabelos castanhos e outra com cabelos grisalhos, talvez seja mais jovem na foto com cabelos castanhos. Mas talvez você tenha pintado o cabelo? O problema é: você deve saber que pintou o cabelo. Outros podem? Para colocar isso em um contexto válido, é necessário introduzir a idade da propriedade (versão). Então você é semanticamente explícito e sem ambiguidade.
Para evitar a operação oculta "substituindo antigo por novo objeto", um conjunto não deve ter um método get. Se você deseja um comportamento como esse, é necessário explicitá-lo removendo o objeto antigo e adicionando o novo objeto.
BTW: O que deveria significar se você passasse um objeto igual ao objeto que você deseja obter? Isso não faz sentido. Mantenha sua semântica limpa e não faça isso, embora tecnicamente ninguém o impeça.
fonte
Especificamente em Java,
HashSet
foi implementado inicialmente usando um método deHashMap
qualquer maneira e apenas ignorando o valor. Portanto, o design inicial não antecipou nenhuma vantagem em fornecer um método getHashSet
. Se você deseja armazenar e recuperar um valor canônico entre vários objetos iguais, basta usar umHashMap
você mesmo.Eu não me atualizei com esses detalhes de implementação, por isso não posso dizer se esse raciocínio ainda se aplica totalmente em Java, muito menos em C # etc. Mas mesmo se
HashSet
foram reimplementados para usar menos memória do queHashMap
, em qualquer caso, seria uma mudança inédita para adicionar um novo método àSet
interface. Portanto, é muito doloroso para um ganho que nem todo mundo vê como vale a pena ter.fonte
default
implementação para fazer isso de maneira ininterrupta. Simplesmente não parece uma mudança muito útil.O(n)
comparações, mesmo se a função hash estiver fornecendo boa distribuição. Em seguida, as implementaçõesSet
que substituem a implementação padrão na interface, inclusiveHashSet
, podem dar uma garantia melhor.Existe um idioma principal cujo conjunto possui a propriedade que você deseja.
Em C ++,
std::set
é um conjunto ordenado. Ele possui um.find
método que procura o elemento com base no operador de pedidos<
ou nabool(T,T)
função binária que você fornece. Você pode usar o find para implementar a operação de obtenção desejada.De fato, se a
bool(T,T)
função que você fornecer possui um sinalizador específico (is_transparent
), você pode passar objetos de um tipo diferente para os quais a função está sobrecarregada. Isso significa que você não precisa colar o dado fictício no segundo campo, apenas assegure-se de que a operação de pedido que você usa possa solicitar entre os tipos de pesquisa e de conjunto.Isso permite uma eficiente:
onde
my_string_compare
entende como ordenar números inteiros e cadeias de caracteres sem primeiro converter o número inteiro em uma cadeia de caracteres (a um custo potencial).Para
unordered_set
(o conjunto de hash do C ++), ainda não existe um sinalizador transparente equivalente. Você deve passar umT
para umunordered_set<T>.find
método. Ele pode ser adicionado, mas os hashes exigem==
e um hasher, ao contrário dos conjuntos solicitados que exigem apenas uma solicitação.O padrão geral é que o contêiner fará a pesquisa e fornecerá um "iterador" para esse elemento no contêiner. Nesse ponto, você pode obter o elemento dentro do conjunto ou excluí-lo etc.
Em resumo, nem todos os contêineres padrão de todos os idiomas têm as falhas que você descreve. Os contêineres baseados em iteradores da biblioteca padrão C ++ não existem, e pelo menos alguns deles já existiam antes de qualquer um dos outros idiomas que você descreveu, e a capacidade de obter uma experiência ainda mais eficiente do que a maneira como você descreve foi adicionada. Não há nada de errado com seu design, ou com o desejo dessa operação; os designers dos conjuntos que você está usando simplesmente não forneceram essa interface.
Os contêineres padrão C ++ foram projetados para envolver de maneira limpa as operações de baixo nível do código C enrolado à mão equivalente, projetado para corresponder à maneira como você pode escrevê-lo com eficiência na montagem. Seus iteradores são uma abstração de ponteiros no estilo C. As linguagens que você mencionou se afastaram dos ponteiros como conceito, portanto, eles não usaram a abstração do iterador.
É possível que o fato de o C ++ não ter essa falha seja um acidente de design. O caminho centrado no iterador significa que, para interagir com um item em um contêiner associativo, você primeiro obtém um iterador para o elemento e, em seguida, usa esse iterador para falar sobre a entrada no contêiner.
O custo é que existem regras de invalidação de iteração que você precisa rastrear e algumas operações exigem duas etapas em vez de uma (o que torna o código do cliente mais barulhento). O benefício é que a abstração robusta permite um uso mais avançado do que os que os projetistas de API tinham em mente originalmente.
fonte