Table de hachage de modification non destructive

Question

Est-il possible d'ajouter de manière non destructive de nouvelles paires clé-valeur à une table de hachage Common Lisp (SBCL)? La méthode standard pour ajouter de nouveaux éléments à une table de hachage consiste à appeler:

(setf (gethash key *hash-table*) value)

mais l'appel à setfmodifie la *hash-table*corruption de l'original. J'ai une application où j'aimerais profiter de l'efficacité des recherches de table de hachage, mais j'aimerais aussi les modifier de manière non destructive. Le contournement que je vois est de copier la table de hachage d'origine avant de l'utiliser, mais ce n'est pas pratique dans mon cas car les tables de hachage que je traite contiennent des milliers d'éléments et copient de grandes tables de hachage, disons, dans un boucle annulerait l'avantage d'efficacité de calcul de leur utilisation en premier lieu.

Answer 1

En fonction de vos besoins, vous pourrez peut-être simplement utiliser une liste d'associations, utiliser assocet d'autres fonctions pour établir de nouvelles liaisons par-dessus celles existantes. Le fait que assocrenvoie le premier élément correspondant signifie que vous pouvez masquer les liaisons:

(let ((list '((:a . 1) (:b . 2))))
  (acons :b 3 list))

=> ((:b . 3) (:a . 1) (:b . 2))

Si vous appelez (assoc :b list)dans la liste résultante, l'entrée sera (:b . 3), mais la liste d'origine n'est pas modifiée.

FSet

Si les listes d'associations ne suffisent pas, la bibliothèque FSet fournit des structures de données purement fonctionnelles pour Common Lisp, comme les cartes, qui sont des tables de hachage immuables. Ils sont mis en œuvre comme des arbres équilibrés, ce qui est mieux qu'une approche naïve. Il existe également d'autres structures de données plus efficaces, mais vous devez probablement les implémenter vous-même ( Hash array mapped trie ). Cela étant dit, FSet est assez bon en général.

FSet est disponible via Quicklisp

USER> (ql:quickload :fset)

Créez une carte; notez que la représentation imprimée est faite pour être relue, si vous installez les macros de lecteur appropriées. Mais vous pouvez parfaitement utiliser la bibliothèque sans la table de syntaxe modifiée.

USER> (fset:map (:a 0) (:b 1))
#{| (:A 0) (:B 1) |}

Mettez à jour la carte précédente avec une nouvelle liaison pour :c:

USER> (fset:with * :c 3)
#{| (:A 0) (:B 1) (:C 3) |}

Mettez à jour la carte précédente avec une nouvelle liaison pour :b, qui occulte la précédente:

USER> (fset:with * :b 4)
#{| (:A 0) (:B 4) (:C 3) |}

Toutes les cartes intermédiaires ne sont pas modifiées:

USER> (list * ** *** )
(#{| (:A 0) (:B 4) (:C 3) |}
 #{| (:A 0) (:B 1) (:C 3) |} 
 #{| (:A 0) (:B 1) |})

Answer 2

Je ne pense pas que vous puissiez passer par référence une table de hachage à une autre table de hachage dans le lisp commun. Mais ce que j'avais une idée était de savoir comment éviter de copier l'intégralité de la table de hachage, mais obtenir un résultat en un seul appel consiste à utiliser la position de l'argument de valeur par défaut de gethash.

(gethash key ht default-value)renvoie ce qui est donné pour la valeur par défaut, quand keyn'est pas présent dans ht.

;; prepare three example hash-tables, where *h3* and *h2* gets the additional keys
;; and if a key is not present in *h3*, one should look up in *h2*, and if not there too, in *h1*.
(defparameter *h1* (make-hash-table))
(setf (gethash 'a *h1*) 1)
(setf (gethash 'b *h1*) 2)
(setf (gethash 'c *h1*) 3)

(defparameter *h2* (make-hash-table))
(setf (gethash 'd *h2*) 4)
(setf (gethash 'e *h2*) 5)

(defparameter *h3* (make-hash-table))
(setf (gethash 'f *h3*) 6)

;; the call
(gethash 'a *h3* (gethash 'a *h2* (gethash 'a *h1*)))
;; would give the desired result `1`.

;; let us assume, there is a chain of hash-tables *hk* *h(k-1)* ... *h2* *h1*
;; in which one should look up into that order.
;; Then it is to us to build the code
;; (gethash 'a *hk* (gethash 'a *h(k-1)* ...(gethash 'a *h2* (gethash 'a *h1*))...))
;; automatically for every lookup.


;; this macro does it:
(defmacro mget (key hash-tables-list)
  (flet ((inject-last (e1 e2) `(,@e1 ,e2)))
    (reduce #'inject-last 
            (mapcar (lambda (ht) `(gethash ,key ,ht)) 
                    (nreverse hash-tables-list)))))

;; let's see its macroexpansion:
(macroexpand-1 '(mget 'a (*h3* *h2* *h1*)))
;; (GETHASH 'A *H3* (GETHASH 'A *H2* (GETHASH 'A *H1*))) ;
;; T

;; and run the code:
(mget 'a (*h2* *h1*))
;; 1 ;
;; NIL

On pourrait joindre des informations qui sont la prochaine table de hachage à rechercher dans l'objet table de hachage. Et même automatiser la génération de la liste (*h3* *h2* *h1*)pour que l'on n'écrive que (gethash* key ht)ce qui appelle alors mget...

Bien sûr, à travers tout cela, l'accès au hachage est ralenti.

C'est un compromis entre copier des tables de hachage entières ou payer le coût des performances à chaque appel ...

recherche automatique de tables de hachage qui sont étendues par *h3*

(setf (get '*h3* 'extendeds) '(*h2* *h1*))
(setf (get '*h2* 'extendeds) '(*h1*))

(defun collect-extendeds (hts)
  (let ((res (loop for ht in hts
                   nconcing (get ht 'extendeds))))
    (remove-duplicates res)))

;; this function can recursively retrieve all hashtables
(defun get-extendeds* (hts &optional (acc '()))
  (let ((hts (if (listp hts) hts (list hts))))
      (let ((nexts (collect-extendeds hts)))
        (cond ((every #'null nexts) (nreverse (remove-duplicates (append hts acc))))
              (t (get-extendeds* nexts (remove-duplicates (append hts acc))))))))

;; write a macro to retrieve key's value from all downstream hashtables
(defmacro geth (key ht)
  `(mget ,key ,(get-extendeds* ht)))

(geth 'a *h3*)
;; 1 ;
;; NIL  ;; NIL because it was not in *h3* directly but in one of the hashtables
;; which it extends.

;; problem is if 'NIL is a value of an existing key,
;; one would still get 'NIL NIL.