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]
  1. ↑ Deutsch, Laurence Peter (1973). „An Interactive Program Verifier”, Kiadó: Xerox Palo Alto Research Center Terhnical Report CSL-73-1. 
  2. ↑ Goto, Eiichi (1974). „Monocopy and associative algorithms in extended Lisp”, Kiadó: University of Tokyo Technical Report TR 74-03. 
  3. ↑ „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]