해시 처리

Hash consing

컴퓨터 과학, 특히 함수 프로그래밍에서 해시 콘소싱은 구조적으로 동등한 값을 공유하기 위해 사용되는 기술이다.해시 고려라는 용어는 메모리 할당의 패널티를 피하기 위해 이전에 구성된 콘셀을 재사용하려는 Lisp의[1][2] 구현에서 유래했습니다.해시 고려는 가장 일반적으로 취약한 참조를 저장하는 해시 테이블과 함께 구현됩니다.이러한 참조는 저장된 데이터에 [3][4]테이블 외부에서 참조가 없을 때 수집될 수 있습니다.해시 콘소싱은 심볼릭 [citation needed]및 다이내믹 프로그래밍 알고리즘의 공간 및 시간 모두에서 성능을 획기적으로 향상시키는 것으로 나타났습니다.해시 컨싱의 흥미로운 특성은 두 구조가 일정한 시간에 동일한지 테스트할 수 있다는 것입니다. 따라서 데이터 세트에 겹치는 [5]블록이 포함되어 있을 때 분할 및 정복 알고리즘의 효율성을 향상시킬 수 있습니다.

예

단순하고 효율적이지 않지만 해시 테이블과 스킴의 약한 참조를 사용하여 메모라이저의 개념 구현을 시연하기에 적합합니다.

;; 약한 해시 ;; (요구하다 '테이블)  (정의하다(약식 테이블 . args)   (적용합니다.제조표 args))  (정의하다(약한 테이블 세트! 테이블 열쇠 데이터.)   (허락하다((w (해시 테이블 참조 테이블 열쇠 #f)))     (한다면w         (벡터 세트! w 0 데이터.)       (허락하다((w (약하게 하다 1)))         (벡터 세트! w 0 데이터.)         (해시 테이블 세트! 테이블 열쇠 w)))))  (정의하다(weak-table-ref 테이블 열쇠)   (허락하다((w (해시 테이블 참조 테이블 열쇠 #f)))     (한다면w         (벡터 참조w 0)       #f)))  ;; 메모라이저 공장: 주어진 (부작용이 없는) 절차를 위해, ;; 일부 결과를 메모하는 것과 동일한 프로시저를 반환한다. ;;; 평등한 의미에서?모든 아르그 리스트에 ;; (정의하다(제조 약화기 프로세서)   (허락하다((캐시 (약식 테이블 동등하게?)))     (람다args       (허락하다((x (weak-table-ref 캐시 args)))         (한다면(bwp-object? x)             (허락하다((r (적용합니다.프로세서 args)))               (약한 테이블 세트! 캐시 args r)               r)           x)))))

「 」를 참조해 주세요.

레퍼런스

  1. ^ Deutsch, Laurence Peter (1973). An Interactive Program Verifier (PDF) (Phd). Palo Alto: Xerox Palo Alto Research Center Technical Report CSL-73-1.
  2. ^ Goto, Eiichi (1974). "Monocopy and associative algorithms in extended Lisp" (PDF). Tokyo: University of Tokyo Technical Report TR 74-03. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  3. ^ Allen, John (1978). Anatomy of Lisp. McGraw Hill. ISBN 0-07-001115-X.
  4. ^ Fillâtre, Jean-Christophe; Conchon, Sylvain (2006). "Type-Safe Modular Hash-Consing". Workshop on ML. ACM.
  5. ^ Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

추가 정보

  • Ershov, A.P. (1958). "On programming of arithmetic operations". Communications of the ACM. 1 (8): 3–6. doi:10.1145/368892.368907. S2CID 15986378.
  • 장 구보Fast Equality, Sets 및 Maps를 사용한 기능 언어 구현: 해시 컨싱 연습Journéees Francophones des Langages Application (JFLA'93) (안시, 1993년 2월)222 ~ 238페이지).


Stub icon

이 컴퓨터 과학 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.