Hash cons
A hash cons a számítógép-programozásban, különösen a funkcionális programozásban egy módszer szerkezetileg egyenlő értékek megosztására. Az elnevezést a Lisp implementációk adták, amelyek cons cellákat használtak fel újra ahhoz, hogy adminisztrációs költségeket spóroljanak meg.[1][2] Leggyakoribb megvalósítása gyenge referenciákat tároló hashtáblák, amiket a szemétszedő összegyűjthet, ha kívülről nincs rájuk referencia. Mind térben, mind időben sokat javít a szimbolikus és a dinamikus algoritmusokon. Érdekes tulajdonsága, hogy két szerkezet egyenlősége konstans időben eldönthető, ami feljavítja az oszd meg és uralkodj algoritmusok hatékonyságát, ha az adathalmazok átfedő blokkokat tartalmaznak.[3]
Ez a minta rokon a könnyűsúlyúval. Stringekre alkalmazva ezt a technikát string bekebelezésnek nevezik.
Példa[szerkesztés]
Az alábbi Scheme nyelvű példa egyszerű, de nem túlságosan hatékony megvalósítása egy emlékező struktúrának hash táblával és gyenge referenciákkal:
;; weak hashes
;;
(require 'hash-table)
(define (make-weak-table . args)
(apply make-hash-table args))
(define (weak-table-set! table key data)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-set! w 0 data)
(let ((w (make-weak-vector 1)))
(vector-set! w 0 data)
(hash-table-set! table key w)))))
(define (weak-table-ref table key)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-ref w 0)
#f)))
;; memoizer factory: for given (side-effect-free) procedure,
;; return a procedure which does the same memoizing some of results
;; in the sense of equal? on the whole list of args
;;
(define (make-weak-memoizer proc)
(let ((cache (make-weak-table equal?)))
(lambda args
(let ((x (weak-table-ref cache args)))
(if (bwp-object? x)
(let ((r (apply proc args)))
(weak-table-set! cache args r)
r)
x)))))
Jegyzetek[szerkesztés]
- ↑ Deutsch, Laurence Peter (1973). „An Interactive Program Verifier”, Kiadó: Xerox Palo Alto Research Center Terhnical Report CSL-73-1.
- ↑ Goto, Eiichi (1974). „Monocopy and associative algorithms in extended Lisp”, Kiadó: University of Tokyo Technical Report TR 74-03.
- ↑ „Confluently Persistent Sets and Maps”.
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a Hash consing című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
További olvasmányok[szerkesztés]
- Merkle tree
- Ershov, A.P. (1958). „On programming of arithmetic operations”. Communications of the ACM 1 (8), 3–6. o. DOI:10.1145/368892.368907.
- Jean Goubault. Implementing Functional Languages with Fast Equality, Sets and Maps: an Exercise in Hash Consing. In Journées Francophones des Langages Applicatifs (JFLA’93), pages 222–238, Annecy, February 1993.
