Mapa de string-to-string com eficiência de memória em Python (ou C)

StackOverflow https://stackoverflow.com/questions/4026359

Pergunta

Preciso de uma estrutura de dados com eficiência de memória para armazenar cerca de um milhão de pares de chaves, onde as chaves são strings de cerca de 80 bytes, e os valores são strings de cerca de 200 bytes, sendo a chave total e o tamanho do valor de cerca de 280 MB. Eu também preciso de uma pesquisa eficiente de valor por chave, de preferência um mapa de hash. A sobrecarga da memória deve ser o mínimo possível, por exemplo, 280 MB de dados úteis, a estrutura de dados não deve usar mais de 300 MB de memória virtual (incluindo malloc() sobrecarga e tudo mais). O padrão de uso é o seguinte: começamos com uma estrutura de dados vazia e o preenchemos gradualmente, nunca alterando as teclas e nunca alteramos o comprimento dos valores. Como mais, a estrutura de dados pode suportar a alteração do comprimento dos valores, às custas de uma sobrecarga de valor de 100% (o que significa que, para os bytes de valor x, os bytes x podem ser desperdiçados temporariamente no espaço buffer não utilizado).

Preciso de um módulo python puro, ou um módulo Python embutido, ou uma implementação C de preferência com (c) ligações de Python. Eu preferiria se fosse possível serializar toda a estrutura de dados ao disco e lê -lo de volta muito rapidamente.

Só para provar que é possível uma sobrecarga tão pequena, criei um design simples com endereçamento aberto, a tabela de hash de 1,25 milhão de elementos contendo ponteiros de 4 bytes a 1 MB de blocos de dados, os blocos de dados que contêm os comprimentos de chave e valor como Base-128 Varints. Esse design tem uma limitação importante: não permite remover ou alterar pares sem desperdiçar sua área de memória. De acordo com meus cálculos com 1 milhão de pares-chave-pares de 280 bytes cada, a sobrecarga é inferior a 3,6% (10 080 000 bytes). Os limites acima são mais generosos, eles permitem 20.000.000 bytes de sobrecarga.

Acabei de encontrar http://www.pytables.org/ , que fornece acesso rápido e embalagem de dados com eficiência de memória. Eu tenho que examiná -lo mais de perto para verificar se atende às minhas necessidades.

Foi útil?

Solução 10

Como não consegui encontrar soluções existentes que empacotem bem a memória, decidi implementá -la em C para mim. Veja meu design com endereçamento aberto na questão.

Outras dicas

Ok, a abordagem sujeira simples.

Use um dicionário Python para a estrutura de dados. Encheguei um dicionário de Python com 1 milhão de pares de valor-chave aleatório, onde a chave tinha 80 caracteres e o valor de 200 caracteres. Foram necessários 360.844 KB no meu computador, que está fora da sua especificação de não mais que 300 MB, mas eu o ofereço como uma solução de qualquer maneira, porque ainda é bastante eficiente em memória.

Isso também falha na sua exigência de ter uma API C. Não sei por que você precisa de C, mas, como a pergunta é marcada pelo Python e não tem uma tag C, oferecerei o python puro para ver se ela pode caber na conta.

Em relação à persistência. Use o módulo cpickle. É muito rápido e, novamente, sujeira-simples. Para salvar seu dicionário:

cPickle.dump(mydict, "myfile.pkl")

Para recarregar seu dicionário:

mydict = cPickle.load("myfile.pkl")

Uma segunda idéia de sujeira simples é usar o shelve Módulo, que é basicamente o dicionário Python baseado em disco. A sobrecarga da memória é muito baixa (está tudo no disco). Mas também é muito mais lento.

Martijn mencionou isso em um comentário (não sei por que as pessoas comentam com respostas), mas eu concordo: use o sqlite. Você deve tentar e ver se ele atenderá às suas necessidades.

Se você não planeja ter grandes quantidades de exclusão, isso não é tão difícil. Exclui a fragmentação.

Você também precisa se comprometer com uma tecla de comprimento fixo. Você mencionou 80 bytes. Suas chaves podem duplicar? Caso contrário, é ainda mais fácil.

Então, aqui está o que você faz.

Você cria uma variedade de: 

struct {
    char value[80];
    char *data;
} key;

E você mantém essa matriz classificada.

Se você as chaves podem duplicar, então você precisa:

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(Meu C está enferrujado, mas essa é a essência), este último tem cada chave apontando para uma lista vinculada de valores.

Então uma pesquisa é uma pesquisa binária simples. A "dor" está em manter essa matriz e inserir/excluir teclas. Não é tão doloroso quanto parece, mas economiza muita memória, especialmente em sistemas de 64 bits.

O que você deseja reduzir é o número de ponteiros. Os ponteiros são caros quando você tem muitas estruturas cheias de ponteiros. Em um sistema de 64 bits, um ponteiro é de 8 bytes. Então, para um único ponteiro, lá vai 8 MB do seu orçamento de memória.

Portanto, a despesa está na construção da matriz, copiando e compactando memória (se você "souber", terá um milhão de linhas e poderá se comprometer com isso, então Malloc (1000000 * sizeof (chave)) imediatamente, ele salvará você alguns copiando durante a expansão).

Mas não tenha medo, uma vez que está em funcionamento, o desempenho é muito bom. As CPUs modernas são realmente muito boas em copiar bloqueios de 100m de memória.

Assim como um aparte, eu apenas fiz algo assim em Java. Em uma JVM de 64 bits, um mapa com 25m de entradas é 2g de RAM. Minha solução (usando técnicas semelhantes para isso) tem cerca de 600m). Java usa mais ponteiros que C, mas a premissa é a mesma.

Você já tentou usar um ditado direto? A maioria dos seus dados está em cordas, portanto a sobrecarga pode se encaixar nas suas necessidades.

Você pode usar o sha1 da chave em vez da própria chave. Se as chaves são únicas, então o sha1 Hash das chaves também é provável. Ele fornece uma economia de memória para tentar riscar sob o seu limite.

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

Na minha caixa Ubuntu, isso chega a 304 MB de memória:

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Perto o suficiente? É Python, não C.

Posterior: Além disso, se seus dados são um pouco redundantes, você pode gzip os valores. É um tempo versus trade-off espacial.

Usar o SQLite é uma boa ideia. Uma implementação rápida pode dizer se você é rápido o suficiente com pouco esforço.

Se você determinar que precisa rolar o seu próprio, eu recomendaria o seguinte:

Quão bem você pode prever o número de pares ou um limite superior para isso?
Quão bem você pode prever o tamanho total dos dados ou um limite superior para isso?

Alocador de arena Para cordas e nós. (Geralmente, você trabalhava em uma lista de arenas, para não precisar prever o tamanho total).

O alinhamento depende de seus algoritmos, em princípio que você pode embalar o byte-tight, e a única sobrecarga é a sua localização geral, que afeta minimamente o seu conjunto de trabalho.

No entanto, se você precisar executar qualquer CMP/cópia etc. Operações nessas seqüências, lembre -se de que, com as seguintes garantias, você pode espremer um pouco ou muito dessas operações de string:

  • Todos os elementos estão alinhados com a palavra da CPU
  • Todos os bytes de pads são (por exemplo) 0
  • Você pode ler com segurança "Beyond" um final de corda, desde que não cruze uma borda da CPU

Tabela de hash para o índice. Um dicionário também funcionaria, mas isso faz sentido apenas se a degradação / reforma potencial seria um problema sério. Não conheço nenhuma implementação de hashtable "estoque" para C, mas deve haver um, certo? certo? Basta substituir as alocações por chamadas para o alocador da arena.

Localidade da memória

Se você puder garantir que a pesquisa nunca solicitará uma string que não esteja no mapa, você deve armazenar as chaves em uma arena separada, pois elas são necessárias apenas em colisões de hash. Isso pode melhorar significativamente a localidade da memória. (Nesse caso, se você tiver uma tabela "final", poderá até copiar as chaves em colisão de uma nova arena e jogar fora todos os outros. Os benefícios disso provavelmente são marginais.

A separação pode ajudar ou prejudicar, dependendo dos seus padrões de acesso. Se você normalmente usa o valor uma vez após cada pesquisa, fazê-los em pares na mesma arena é ótimo. Se você, por exemplo, procurar algumas teclas, use seus valores repetidamente, arenas separadas fazem sentido.

Se você precisar suportar "personagens engraçados" / unicode, normalize suas cordas antes de armazená -las.

Você pode usar o módulo Struct para empacotar dados binários e descompactá -los quando necessário. Você pode implementar um armazenamento com eficiência de memória usando essa abordagem. Eu acho que o acesso seria uma dor.

O Apache Portable Runtime (também conhecido como APR) possui uma tabela de hash baseada em C. Você pode ver a documentação em http://apr.apache.org/docs/apr/0.9/group_Apr_hash.html

Com APR_HASH_T, tudo o que você armazena é nulo*. Por isso, fornece controle total sobre os valores. Portanto, se você quiser, poderá armazenar o ponteiro para um bloco de 100 bytes em vez do comprimento real da string.

Judy deve ter eficiência de memória: http://judy.sourceforge.net/
(Benchmarks: http://www.nothings.org/computer/Judy/, consulte "Tamanho da estrutura de dados").
Veja também: http://www.dalkescientific.com/python/pyjudy.html

Também,

Para chaves de tamanho fixo, existe http://panthema.net/2007/stx-btree/ Em C ++ (tenho certeza de que, com um invólucro C personalizado, ele pode ser usado no Cpython). Se o conjunto de dados permitir, você poderá armazenar as teclas de comprimento variável no valor e usar um hash ou um prefixo da tecla de comprimento variável como a chave de comprimento fixo.

A mesma lógica se aplica a http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and time.html e http://code.google.com/p/sparsehash/ -ISTead de usar uma String STD :: pesada como uma chave, use uma chave inteira de 32 bits ou 64 bits, tornando-a de alguma forma a partir da chave de comprimento variável real.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top