gamme hybride de Lua et table de hachage; t-il existe nulle part ailleurs?

Question

La mise en œuvre des tableaux de Lua garder ses éléments en deux parties: une partie de tableau et une partie de hachage

.

Est-ce qu'une telle chose existe dans toutes les autres langues?

Jetez un oeil à la section 4, tableaux, La mise en œuvre de Lua 5.0 .

Lua 5.1 Code source - table.c

Answer 1

Cette idée était originale avec Roberto Ierusalimschy et le reste de l'équipe Lua. J'ai entendu Roberto donner une conférence à ce sujet à l'atelier langues léger MIT en 2003, et dans ce discours il a discuté de travail avant et rétorquer que le fait idée était nouvelle. Je ne sais pas si d'autres langues l'ont copié depuis.

Le Awk d'origine a un modèle de langage un peu plus restreint que Lua; soit un nombre ou une chaîne peut être utilisé comme une clé dans un tableau, mais eux-mêmes tableaux ne sont pas des valeurs de première classe:. un tableau doit avoir un nom et un tableau ne peut pas être utilisé comme une clé dans le tableau

En ce qui concerne la mise en œuvre, j'ai vérifié les sources pour l'Awk original maintenu par Brian Kernighan, et la mise en œuvre de Awk utilise une table de hachage, pas la structure tableau / table hybride de Lua. La distinction est importante parce que, dans Lua, lorsqu'une table est utilisée avec des clés entières consécutives, la surcharge de l'espace est le même que pour une matrice C. Ceci est pas true pour Awk d'origine.

Je ne l'ai pas pris la peine d'enquêter sur toutes les implémentations ultérieures de awk, par exemple, Gnu awk, mawk, et ainsi de suite.

Answer 2

EDIT:. Cela ne répond pas à la question qui était sur le point de la mise en œuvre

AWK l'ai fait aussi.

Il est interesing comment certaines langues amalgament opérations qui sont différentes dans d'autres:

• Liste indexation - a[10]
• indexation Associatif - a['foo']
• Accès champ Objet - a.foo
• Fonction / méthode appelle - a('foo') / a.foo()

Des exemples très incomplets:

• Perl est la langue rare où l'indexation associative / séquentielle ont une syntaxe séparée - a[10] / a{'foo'}. AFAIK, champs d'objet carte à l'un des autres opérations, selon laquelle le implémenteur la classe était comme utiliser.

• tous les 4 sont en Python, distinct; l'utilisation de l'indexation séquentielle / associative même syntaxe mais les types de données séparés sont optimisés pour eux.

• Dans Ruby, champs d'objet sont des méthodes sans arguments -. a.foo

• En JavaScript, les champs d'objets a.foo sont le sucre syntaxe pour a['foo'] d'indexation associative.

• Dans Lua et AWK, les tableaux associatifs sont également utilisés pour l'indexation séquentielle -. a[10]

• Arc , l'indexation séquentielle et associative ressemble à des appels de fonctions - (a 10) / (a "foo"), et je pense a.foo est le sucre syntaxe pour cela aussi (?).

Answer 3

Le plus proche chose que je peux penser est Javascript - vous créez un tableau avec new Array(), puis passez à l'index soit par numéro ou par valeur de chaîne. Il pourrait bien être pour des raisons de performances certaines implémentations Javascript choisissent de le faire en utilisant deux tableaux, pour les raisons indiquées dans la documentation Lua vous liés à.

Answer 4

ArrayWithHash est une mise en œuvre rapide de

hybride série-Hashtable en C ++.

Comme C ++ est un langage typé statiquement, seules les touches entières sont autorisés dans ArrayWithHash (aucun moyen d'insérer la clé de chaîne ou pointeur). En d'autres termes, il est quelque chose comme un tableau avec la sauvegarde de la table de hachage pour les grands indices. En outre, il utilise différentes implémentation de table de hachage qui est moins efficace mémoire que la mise en œuvre de table Lua.