Como acelerar o carregamento de grandes hashtables?

7

Pelo que entendi no manual (últimos parágrafos de http://www.gnu.org/software/emacs/manual/html_node/elisp/Creating-Hash.html ) e na pergunta /programming/11745097 / no stackoverflow, é possível salvar uma versão impressa de uma hashtable no disco para carregá-la para uso posterior.

Por exemplo, a versão impressa de uma hashtable criada por

(setq ht (make-hash-table :test 'equal))
(puthash "orange" 1 ht)
(puthash "apple" 2 ht)

é o seguinte

#s(hash-table size 65 test equal rehash-size 1.5 rehash-threshold 0.8 data ("orange" 1 "apple" 2))

Esta versão impressa já é o melhor formato (para consideração de velocidade) que o Emacs pode usar? Existe um procedimento especial para reformatar (compilar bytes, alterar) o formato impresso acima para um formato melhor (talvez apenas legível por máquina) para que o Emacs carregue essa hashtable mais rapidamente. Se a resposta for afirmativa, quais são as maneiras de fazê-lo.

hash-tables Nome
fonte

Respostas:

3

Sim, é o melhor formato (para consideração de velocidade).

Stefan
fonte
Eu aceito seu juramento.
Nome
5

Você precisará hash e inserir todos os valores, independentemente de qual seja, e a menos que esteja lidando com enormes tabelas de hash, o tempo gasto não deve realmente importar. No entanto, se suas tabelas forem grandes, você deverá usar o :sizeparâmetro para make-hash-tableque nenhuma realocação tenha que ocorrer. Quando uma tabela de hash atinge o limite, ter que realocar um novo local na memória para colocar os valores e refazer todas as entradas atuais será uma grande perda de desempenho.

Se você sabe que está prestes a inserir 1 milhão de entradas em uma tabela de hash, use (make-hash-table :size 1000000)

Considere a seguinte referência:

(benchmark 10
           '(let ((ht (make-hash-table :size 1000000)))
              (dotimes (n 1000000) (puthash n (1+ n) ht))
              ht))
"Elapsed time: 4.156233s (2.087411s in 10 GCs)"


(benchmark 10
           '(let ((ht (make-hash-table)))
              (dotimes (n 1000000) (puthash n (1+ n) ht))
              ht))
"Elapsed time: 10.276816s (7.713422s in 41 GCs)"

Você também pode definir sua própria função de teste e hash para tabelas de hash. Se você souber que suas chaves estarão em um conjunto específico, você poderá escrever funções de equidade e hash mais rápidas que exploram isso. Veja: define-hash-table-test.

Jordon Biondo
fonte
Comparação de tempo muito interessante. Obrigado. Como você demonstrou, definir o tamanho de uma tabela de hash pode influenciar significativamente seu tempo de criação.
Name
Permitam-me, contudo, mencionar que, na pergunta original, perguntei sobre a velocidade de um ponto de vista ligeiramente diferente. Já criei uma tabela de hash grande e já salvei essa tabela de disco no disco (por comando de impressão). Então, eu tenho um arquivo grande com conteúdo semelhante #s(hash-table size 65 test equal rehash-size 1.5 rehash-threshold 0.8 data ("orange" 1 "apple" 2 ..............)). Eu posso carregar esta tabela de hash. Eu estava interessado em saber se esse tipo de arquivo é o melhor formato que o Emacs pode usar para carregar rapidamente a tabela.
Name
Portanto, a ênfase é mais no momento de carregar uma tabela já salva no disco do que no momento da criação pela primeira vez.
Name