Usando Hash Maps para representar uma fonte de dados extremamente grandes

Question

Eu tenho um conjunto muito grande de dados possível que eu estou tentando visualizar de uma só vez. O conjunto em si consiste em centenas de milhares de segmentos, cada um dos quais é mapeado para um id.

Eu recebi uma segunda fonte de dados que dá mais informações em tempo real para cada segmento, mas do id não correspondem ao id é que eu tenho.

Eu tenho um mapeamento 1: 1 de (cordas 9 caracteres) do id dados (inteiros longos) do id atual. O problema é que há um grande número de ID do e os dados que está chegando é em nenhuma ordem específica.

A solução que eu vim com é ter um hash-map que mapeia as cordas para os da id estrada. O problema é que eu não sei se o hash-mapa será suficiente eficiente ter todas as entradas 166K de dados.

Alguém tem alguma sugestão e / ou algoritmos de hash que eu posso usar para isso?

Answer 1

Se você só está lidando com centenas de milhares de pontos de dados, ele provavelmente não vai ser um problema para ir com a maneira ingênua e ficar com um hash-mapa.

Mesmo se você tem 500.000 cordas 9 caracteres e um número igual de longs, que ainda só bytes 16ish por item, ou 8.000.000 bytes total. Mesmo se você dobro para cima, 16 MB é quase demasiado grande para ter na memória de uma vez.

Basicamente, tentar o caminho mais fácil em primeiro lugar, e só se preocupe com isso quando o seu perfil de lhe diz que está demorando muito.

Answer 2

Judy Arrays são projetados para este tipo de coisa: "principais benefícios de Judy são escalabilidade, alta performance, e eficiência de memória. [...] Judy pode substituir muitas estruturas comuns de dados, como matrizes, matrizes esparsas, tabelas de hash, B-árvores, árvores binárias, listas lineares, skiplists, outro tipo e algoritmos de busca e funções de contagem."

Answer 3

Uma vez que os comentários sobre a questão indicam a principal preocupação pode ser o uso de memória:

• Uso de um a utilização comum ou outro pequeno-objeto-optimizado alocador ; supondo que você tenha acesso a impulso você pode provavelmente encontrar um substituto em Piscina . Usando um melhor pequeno-objeto alocador é provavelmente o único grande memória ganhar você vai encontrar.
• Se você sabe que as cordas são de largura fixa, você pode querer certificar-se de que você está alocando único espaço o suficiente para armazená-los. Por exemplo, um struct enrolado em um de comprimento fixo char [] com um operador de comparação personalizada pode funcionar melhor do que um std :: string. std :: string vem com uma alocação dinâmica adicional (e usa o espaço para o ponteiro correspondente) e alguns tamanho extra e capacidade de rastreamento de sobrecarga. (Geralmente, tente reduzir o número de alocações que ficar por aqui;. Que reduz a sobrecarga)
• (Assumindo STL) olhar para a diferença entre sobrecarga std :: mapa e std :: unordered_map (este último pode ou não estar disponível para você no momento); um baseada em RBtree std :: map pode estar perto o suficiente para as características do seu "hashmap" desempenho de pesquisa e pode (ou não) ser mais eficiente de memória, dependendo da sua implementação da biblioteca padrão.

O caminho que você toma deve ser influenciada pela informação que você pode reunir -. Tentar obter uma imagem do número de alocações e alloc sobrecarga tamanho / alinhamento

Você pode instrumento seu alocador ou inserir alguns elementos e ver como você está fazendo em relação à forma como você acha que deveria estar fazendo em termos de uso de memória.

Answer 4

Uma vez que as cordas são conhecidos na frente e ter um comprimento fixo, teórica e praticamente a melhor solução é a perfeito hash. Você pode usar cmph para gerá-la.

De acordo com a Wikipedia, suas chaves caracterizaria tomar 2,5 bits / key, ou cerca de 50KB. Isso é insignificante em comparação com o 664KB para os valores.

Answer 5

Apesar de 166K entradas de dados é bastante pequena IMO você pode ter um olhar para google-sparsehash