Por que o HashSet <Point> é muito mais lento que o HashSet <string>?

165

Eu queria armazenar algumas localizações de pixels sem permitir duplicatas, então a primeira coisa que vem à mente é HashSet<Point>ou classes semelhantes. No entanto, isso parece ser muito lento em comparação com algo comoHashSet<string> .

Por exemplo, este código:

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

leva cerca de 22,5 segundos.

Enquanto o código a seguir (que não é uma boa escolha por razões óbvias) leva apenas 1,6 segundos:

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

Então, minhas perguntas são:

  • Existe uma razão para isso? Eu verifiquei esta resposta , mas 22,5 segundos é muito mais do que os números mostrados nessa resposta.
  • Existe uma maneira melhor de armazenar pontos sem duplicatas?
Ahmed Abdelhameed
fonte
Quais são essas "razões óbvias" para não usar seqüências de caracteres concatenadas? Qual é a melhor maneira de fazer isso se eu não quiser implementar meu próprio IEqualityComparer?
Ivan Yurchenko

Respostas:

290

Existem dois problemas de desempenho induzidos pela estrutura Point. Algo que você pode ver quando adicionaConsole.WriteLine(GC.CollectionCount(0)); ao código de teste. Você verá que o teste de ponto requer ~ 3720 coleções, mas o teste de cadeia precisa apenas de ~ 18 coleções. Não de graça. Quando você vê um tipo de valor induzir tantas coleções, precisa concluir "uh-oh, muito boxe".

O problema é que HashSet<T>precisa de um IEqualityComparer<T>para fazer seu trabalho. Como você não forneceu um, ele precisa retornar ao retornado EqualityComparer.Default<T>(). Esse método pode fazer um bom trabalho para string, implementa IEquatable. Mas não para o Point, é um tipo que remete ao .NET 1.0 e nunca recebeu o amor dos genéricos. Tudo o que você pode fazer é usar os métodos Object.

A outra questão é que Point.GetHashCode () não faz um trabalho estelar neste teste, muitas colisões, então martela muito o Object.Equals (). String possui uma excelente implementação GetHashCode.

Você pode resolver os dois problemas fornecendo ao HashSet um bom comparador. Como este:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

E use-o:

HashSet<Point> list = new HashSet<Point>(new PointComparer());

E agora é 150 vezes mais rápido, superando facilmente o teste de cordas.

Hans Passant
fonte
26
+1 por fornecer a implementação do método GetHashCode. Só por curiosidade, como você veio com uma obj.X << 16 | obj.Y;implementação específica .
Akash KC
32
Foi inspirado na maneira como o mouse passa sua posição nas janelas. É um hash perfeito para qualquer bitmap que você deseja exibir.
Hans Passant
2
É bom saber isso. Alguma documentação ou melhor orientação para escrever código hash como o seu? Na verdade, eu ainda gostaria de saber se o código hash acima vem com a sua experiência ou com alguma orientação que você segue.
Akash KC
5
@AkashKC Eu não sou muito experiente com C #, mas até onde eu sei os números inteiros geralmente são 32 bits. Nesse caso, você deseja o hash de 2 números e, ao deslocar para a esquerda um 16 bits, você garante que os 16 bits "inferiores" de cada número não "afetem" o outro |. Para 3 números, poderia fazer sentido usar 22 e 11 como turno. Para 4 números, seria 24, 16, 8. No entanto, ainda haverá colisões, mas apenas se os números aumentarem. Mas isso também depende crucialmente da HashSetimplementação. Se ele usa o endereço aberto com "truncamento de bits" (acho que não!), A abordagem à esquerda pode ser ruim.
precisa saber é o seguinte
3
@ HansPassant: Gostaria de saber se o uso de XOR em vez de OR em GetHashCode pode ser um pouco melhor - no caso de as coordenadas do ponto excederem 16 bits (talvez não em telas comuns, mas em um futuro próximo). // XOR geralmente é melhor em funções de hash que OR, já que perde menos informações, é reversível, etc. // por exemplo, se coordenadas negativas são permitidas, considere o que acontece com a contribuição X se Y for negativo.
Krazy Glew
85

A principal razão para a queda no desempenho é todo o boxe (como já explicado na resposta de Hans Passant ).

Além disso, o algoritmo de código hash piora o problema, porque causa mais chamadas para Equals(object obj) aumentar a quantidade de conversões de boxe.

Observe também que o código hash dePoint é calculado por x ^ y. Isso produz muito pouca dispersão no seu intervalo de dados e, portanto, os depósitos HashSetsão superpovoados - algo que não acontece string, onde a dispersão dos hashes é muito maior.

Você pode resolver esse problema implementando sua própria Pointestrutura (trivial) e usando um algoritmo de hash melhor para o intervalo de dados esperado, por exemplo, deslocando as coordenadas:

(x << 16) ^ y

Para alguns bons conselhos sobre códigos de hash, leia o post de Eric Lippert no blog sobre o assunto .

Entre
fonte
4
Olhando para a fonte de referência de Point as GetHashCodeexecuta: unchecked(x ^ y)enquanto que para stringele parece muito mais complicado ..
Gilad Verde
2
Hmm ... bem, para verificar se sua suposição está correta, tentei usar em HashSet<long>()vez disso e usei list.Add(unchecked(x ^ y));para adicionar valores ao HashSet. Isso foi ainda mais rápido que HashSet<string> (345 ms) . Isso é de alguma forma diferente do que você descreveu?
Ahmed Abdelhameed 10/09
4
@AhmedAbdelhameed é provavelmente porque você está adicionando muito menos membros ao seu conjunto de hash do que imagina (novamente devido à horrível dispersão do algoritmo de código de hash). Qual é a contagem de listquando você termina de preenchê-lo?
Inbetween
4
@AhmedAbdelhameed Seu teste está errado. Você está adicionando os mesmos comprimentos repetidamente, portanto, na verdade, existem apenas alguns elementos que você está inserindo. Ao inserir point, o HashSetchamará internamente GetHashCodee para cada um desses pontos com o mesmo código hash, vai chamar Equalspara determinar se ele já existe
Ofir Winegarten
49
Não há necessidade de implementar Pointquando você pode criar uma classe que implemente IEqualityComparer<Point>e mantenha a compatibilidade com outras coisas com as quais trabalha, Pointenquanto obtém o benefício de não ter os pobres GetHashCodee a necessidade de se encaixar Equals().
Jon Hanna