ibrido array e hash table di Lua; e non esiste altrove?

Question

attuazione di Lua delle tabelle mantiene l'elementi in due parti: una parte di matrice e una parte hash

.

Esiste una cosa del genere esiste in altre lingue?

Date un'occhiata a sezione 4, tabelle, in L'attuazione di Lua 5,0 .

Lua Codice 5.1 Source - table.c

Answer 1

Questa idea era originale con Roberto Ierusalimschy e il resto della squadra Lua. Ho sentito Roberto tenere un discorso su di esso presso il laboratorio MIT leggeri Lingue nel 2003, e in questo discorso ha discusso il lavoro prima e sostenuto in modo convincente che l'idea era nuova. Non so se altre lingue hanno copiato da allora.

L'Awk originale ha un modello di linguaggio un po 'più ristretta di Lua; un numero o una stringa può essere utilizzata come chiave in una matrice, ma loro volta array sono valori non di prima classe. un array deve avere un nome, e una matrice non possono essere utilizzati come chiave dell'array

Per quanto riguarda l'attuazione, ho controllato le fonti per l'originale Awk come sostenuto da Brian Kernighan, e l'implementazione di Awk usa una tabella hash, non ibrido struttura a matrice / tavolo di Lua. La distinzione è importante perché in Lua, quando viene usata una tabella con le chiavi interi consecutivi, l'overhead spazio è lo stesso per un array C. Si tratta di non vero per originale Awk.

Non ho preso la briga di indagare su tutte le implementazioni successive di awk, per esempio, Gnu Awk, mawk, e così via.

Answer 2

EDIT:. Questo non risponde alla domanda, che era circa l'attuazione

AWK anche lo ha fatto.

E 'interesing come alcune lingue confondono operazioni che sono diverse in altri:

• Lista indicizzazione - a[10]
• Associativo indicizzazione - a['foo']
• accesso campo oggetto - a.foo
• Funzione / Metodo chiamate - a('foo') / a.foo()

esempi molto incompleto:

• Perl è il linguaggio raro in cui l'indicizzazione sequenziale / associativo hanno sintassi separato - a[10] / a{'foo'}. Per quanto ne so, i campi oggetto della mappa per una delle altre operazioni, a seconda di quale l'implementatore della classe si sentiva come l'utilizzo.

• In Python, tutti e 4 sono distinti; uso indicizzazione / associativo stessa sintassi sequenziale ma dati separata tipi sono ottimizzati per loro.

• In Ruby, campi oggetto sono metodi senza argomenti -. a.foo

• In JavaScript, campi oggetto a.foo sono lo zucchero sintassi per associativa a['foo'] indicizzazione.

• In Lua e AWK, array associativi sono utilizzati anche per l'indicizzazione sequenziale -. a[10]

• In Arc , indicizzazione sequenziale e associativo si presenta come chiamate di funzione - (a 10) / (a "foo"), e penso a.foo è lo zucchero sintassi per questo troppo (?).

Answer 3

La cosa più vicina che posso pensare è Javascript - si crea un array con new Array(), e poi procedere per indicizzare sia per numero o per valore stringa. Potrebbe anche essere per motivi di prestazioni alcune implementazioni Javascript scelgono di farlo utilizzando due matrici, per i motivi noti nella documentazione Lua si è collegato al.

Answer 4

ArrayWithHash è un'implementazione veloce di ibrido array-hashtable in C ++.

Dato che C ++ è un linguaggio a tipizzazione statica, solo chiavi intere sono ammessi in ArrayWithHash (nessun modo per inserire la chiave di stringa o un puntatore). In altre parole, è qualcosa come un array con il backup tabella hash per grandi indici. Inoltre utilizza diversa implementazione tabella di hash che è meno memoria-efficiente di implementazione tavolo Lua.