Convertendo identificadores inteiros para ponteiros

votos
1

Eu tenho valores de ID do tipo unsigned int. Eu preciso mapear um ID para um ponteiro em tempo constante .


Distribuição de chaves:

ID terá um valor no intervalo de 0 a UINT_MAX. A maioria das chaves serão agrupadas em um único grupo, mas não haverá valores discrepantes.


Implementação:

  • Eu pensei sobre como usar o C ++ coisas ext hash_map, mas eu ouvi o seu desempenho não é muito grande quando as teclas têm uma gama enorme potencial.

  • Eu também pensei em usar alguma forma de pesquisa acorrentado (equivalente a subdivisão recursiva o intervalo em mandris C). Se não houver chaves em um intervalo, esse intervalo vai apontar para NULL.

    N = Key Gama

    Nível 0 (dividida em C = 16, SO 16 peças) = ​​[0, N / 16), [N / 16, 2 * (N / 16)), ...

    Nível 1 (dividido em C = 16, então 16 * 16 peças) = ​​...


Alguém tem ideias sobre como esse mapeamento pode ser mais eficientemente implementadas?

Atualizar:

Por constante, Eu só quis dizer cada pesquisa chave não é significativamente influenciada pela # de valores no item. Eu não quis dizer que tinha que ser uma única op.

Publicado 27/08/2009 em 06:11
fonte usuário
Em outras línguas...                            


7 respostas

votos
11

Utilizar um mapa de hash ( unordered_map). Isto dá ~ O (1) vezes parecem-up. Você "ouvido" era ruim, mas você experimentá-lo, testá-lo, e determinar que ele seja um problema? Se não, use um mapa hash.

Depois de seu código fica perto de conclusão, perfil e determinar se os tempos de olhar-up são a principal causa da lentidão no seu programa. As possibilidades são, não será.

Respondeu 27/08/2009 em 06:14
fonte usuário

votos
3

Se você quer uma solução baseada em árvore e seus ids estão na faixa {0..n-1} então você pode usar uma estrutura de dados muito legal chamado van Emde Boas árvore . Isto irá proporcionar todas as operações em O (log n log) e usar o O espaço (n).

Respondeu 27/08/2009 em 06:35
fonte usuário

votos
1

Quantos itens devem estar em tal mapa e quantas vezes é que mudou?

Se todos os valores caber na cache do processador, em seguida, uma std::vector<std::pair<unsigned int,T*>>com os valores pré-classificados e busca binária pode ser mais rápido, apesar do acesso ser O (N).

Respondeu 27/08/2009 em 10:40
fonte usuário

votos
1

Como GMan sugere um unordered_map é provavelmente uma boa solução. Se você está preocupado com um grande número de colisões neste mapa de hash, em seguida, usar uma função hash que irá remover o agrupamento de seus dados. Por exemplo, você poderia trocar os bytes ao redor.

Um bom ponto a salientar é que você provavelmente vai gastar mais tempo de depuração e provando uma estrutura de dados personalizado de um que já tem boa pedigree.

Respondeu 27/08/2009 em 06:55
fonte usuário

votos
1

Reserve 4GB de memória RAM para isso, e simplesmente lançar seu uint para o ponteiro. Isso é definitivamente tempo constante.

Respondeu 27/08/2009 em 06:20
fonte usuário

votos
1

Se os seus valores inteiros são 32 bits de largura, então você pode usar uma plataforma de 64 bits, alocar 32 gigabytes de memória (8 bytes por 4 bilhões de ponteiros), e usar uma matriz simples. Isso vai ser o mais próximo que você vai chegar a tempo de pesquisa constante.

Respondeu 27/08/2009 em 06:17
fonte usuário

votos
1

Você não vai conseguir tempo constante.

Eu provavelmente usaria um B + Tree

Respondeu 27/08/2009 em 06:15
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more