Matriz híbrida e tabela hash de Lua;existe em algum outro lugar?

Question

A implementação de tabelas em Lua mantém seus elementos em duas partes:uma parte de array e uma parte de hash.

Existe tal coisa em alguma outra língua?

Dê uma olhada na seção 4, Tabelas, em A implementação de Lua 5.0.

Código-fonte Lua 5.1 - tabela.c

Answer 1

Essa ideia foi original de Roberto Ierusalimschy e do restante da equipe Lua.Ouvi Roberto dar uma palestra sobre isso no workshop Lightweight Languages ​​do MIT em 2003, e nessa palestra ele discutiu trabalhos anteriores e argumentou de forma convincente que a ideia era nova.Não sei se outras línguas o copiaram desde então.

O Awk original possui um modelo de linguagem um pouco mais restrito que Lua;um número ou uma string podem ser usados ​​como chave em um array, mas os arrays em si não são valores de primeira classe:um array deve ter um nome e um array não pode ser usado como chave no array.

Em relação à implementação, verifiquei as fontes do Awk original mantidas por Brian Kernighan, e a implementação do Awk usa uma tabela hash, não a estrutura híbrida de array/tabela de Lua.A distinção é importante porque em Lua, quando uma tabela é usada com chaves inteiras consecutivas, a sobrecarga de espaço é a mesma que para um array C.Isso é não verdadeiro para o Awk original.

Não me preocupei em investigar todas as implementações posteriores do awk, por exemplo, Gnu Awk, mawk e assim por diante.

Answer 2

EDITAR: Isso não responde à pergunta, que foi sobre a implementação.

Awk Também fez isso.

É interessante como alguns idiomas confundem operações diferentes em outras:

• Indexação da lista - a[10]
• Indexação associativa - a['foo']
• Acesso ao campo de objeto - a.foo
• Chamadas de função/método - a('foo') / a.foo()

Exemplos muito incompletos:

• Perl é a linguagem rara em que a indexação sequencial/associativa tem sintaxe separada - a[10] / a{'foo'}. Afaik, os campos de objetos são mapeados para uma das outras operações, dependendo do que o implementador da classe parecia usar.

• Em Python, todos os 4 são distintos; A indexação sequencial/associativa usa a mesma sintaxe, mas os tipos de dados separados são otimizados para eles.

• Em Ruby, os campos de objeto são métodos sem argumentos - a.foo.

• Em JavaScript, campos de objeto a.foo são a sintaxe açúcar para indexação associativa a['foo'].

• Em Lua e Awk, as matrizes associativas também são usadas para indexação sequencial - a[10].

• Dentro Arco, indexação seqüencial e associativa parece chamadas de função - (a 10) / (a "foo"), e eu penso a.foo O açúcar de sintaxe também é (?).

Answer 3

A coisa mais próxima que consigo pensar é o JavaScript - você cria uma matriz com new Array(), e depois prossiga para indexar por número ou pelo valor da string. Pode ser por razões de desempenho que algumas implementações do JavaScript escolhem fazê -lo usando duas matrizes, pelos motivos mencionados na documentação da Lua a que você vinculou.

Answer 4

Arraywithhash é uma implementação rápida do híbrido de matriz-hashtable em C ++.

Como o C ++ é um idioma tipado estaticamente, apenas as teclas inteiras são permitidas no Arraywithhash (não há como inserir a tecla String ou Pointer). Em outras palavras, é algo como uma matriz com backup de tabela de hash para grandes índices. Ele também usa diferentes implementação de tabela de hash que é menos eficiente em termos de memória que a implementação da tabela Lua.