Je me demande s'il y a une implémentation d'une carte qui est:
En bref, y a-t-il une structure de données fonctionnelle qui peut comparer avec les cartes de hachage dans la performance?
4 Réponses :
Clojure a des cartes immuables. ( lien ). Je ne sais pas quelle structure de données sous-jacente utilisée. Le code source de Clojure vous donnera plus d'informations!
Merci beaucoup pour votre réponse utile. Je vais vérifier le clojure bientôt.
Les cartes immuables de Clojure utilisent des essais mappés de hachage de hachage 32 voies ( en.wikipedia.org/wiki/hash_array_mbappe_trie). Ils constituent une excellente structure de données - presque aussi rapide qu'un hashmap mutable, mais avec tous les avantages d'être persistant et immuable.
scala a aussi cartes immuables , Mais ils sont plus lents que les tables de hachage. Je soupçonne que la réponse à votre question est non, vous ne trouverez pas de mise en oeuvre de carte immuable avec O (1) Opérations d'insertion de temps et de requête attendues.
Oui, j'essaie actuellement de Scala et je ne suis généralement pas satisfait de la performance.
Quoi qu'il en soit, juste pour partager avec des personnes, ce sont deux entrées de blog intéressantes sur la mise en œuvre des vecteurs persistants dans Scala utilisant des essais. Ils mentionnent également la mise en œuvre de Clojure, ainsi que la nouvelle INTMAP dans les dernières rejets Scala.
http://www.codecommit.com/blog / SCALA / Mise en œuvre-Vecteurs persistants-in-scala http://www.codecommit.com/blogg/scala/ Plus de vecteurs persistants-performance-analyse
Pour ces structures de données, j'ai testé avec la clé comme des entiers, mais pas encore des chaînes. Parce que ma demande réelle va utiliser des chaînes comme des clés, je ne sais pas si la mise en œuvre sera plus efficace qu'une carte de hachage. Et si j'utilise le hashcode de la chaîne en tant que clé, utilisez un vecteur persistant pour prendre en charge la carte? Je vais utiliser une trie 32 voies pour implémenter le vecteur persistant. Je suppose que la collision serait très rare et la mémoire ne serait interdite qu'en conséquence. Mais je ne suis pas sûr du montant réel nécessaire de copier sur des mises à jour.
Je vais bientôt poster mes résultats.
Je ne l'ai pas lu, mais je pense que certaines personnes considèrent Structures de données purement fonctionnelles comme la Bible pour ce genre de chose.
N'a rien sur les cartes / hashtables.