Persistent and Transient Data Structures in Clojure

이 글 은 이미 작가 장 조 붕 이 왕 이 운 지역사회 에 권한 을 부여 하여 발표 하 였 다.
왕 이 클 라 우 드 커 뮤 니 티 를 방문 하여 더 많은 왕 이 기술 제품 의 운영 경험 을 알 아 보 는 것 을 환영 합 니 다.
최근 프로젝트 에 Transient 데이터 구 조 를 사 용 했 는데 이 데이터 구 조 를 사용 하면 프로그램의 집행 효율 이 어느 정도 향상 된다.Transient Data Stuctures 를 방금 접 했 습 니 다. 다음은 자신 이 그 에 대한 이 해 를 다음 과 같이 요약 합 니 다.
1. clojure 의 가 변 데이터 특성 및 저장 방식:
* 8195: 8195: clojure 의 데이터 구 조 는 가 변 적 이지 않 은 특성 (Persistent) 을 가진다. 즉, 하나의 데이터 구조 에 요 소 를 추가 하고 요 소 를 삭제 하 며 요 소 를 변경 하 며 새로운 데이터 구 조 를 되 돌려 주 는 것 이다. 원래 의 데이터 구 조 는 변 하지 않 는 다.

;;;      
(def data [1 2 3 4 5])
;;=> #'user/data;;        ，      ，       
(update data 3 str)
;;=> [1 2 3 "4" 5]
data
;;=> [1 2 3 4 5]

;;         ，      ，           
(assoc data 5 6)
;;=> [1 2 3 4 5 6]
data
;;=> [1 2 3 4 5]

    이상 은 data = [122345] 에 대해 증가 와 변경 작업 을 하고 data 데이터 자체 가 변 하지 않 고 새로운 데 이 터 를 생 성 했다. 이런 데 이 터 는 가 변성 이 데이터 의 안전성 에 매우 유리 하고 변경 대상 이 가 져 오 는 부작용 이 나타 나 지 않 는 다.이러한 특성 은 반드시 데이터 의 저장 방식 에 대해 높 은 요 구 를 가지 고 클 로 저 에서 의 데이터 구 조 는 아이디어 hash trees (http://lampwww.epfl.ch/papers/idealhashtrees.pdf) 저장 하기:
    vector 의 모든 요 소 는 Leaf node 에 놓 여 있 습 니 다. Internal node 는 요 소 를 저장 하지 않 고 아들 노드 를 가리 키 는 지침 만 저장 합 니 다. 잎 노드 를 찾 는 데 사 용 됩 니 다. 그 중에서 Head 지침 은 나무의 뿌리 노드 를 가리 키 고 이 Head 지침 은 데 이 터 를 이 vector 의 크기 로 저장 합 니 다. vector 의 size 에 따라우 리 는 Internal node 를 따라 모든 번호 에 저 장 된 요 소 를 찾 을 수 있 습 니 다.『 8195 』 클 로 저 에서 의 vector 데이터 구 조 는 불변성 을 가지 기 때문에 복제 의 원 가 를 줄 이기 위해 클 로 저 는 저장 에 효율 적 인 공유 모델 을 취한 다.

;;
(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 5 'beef))

『 8195 』 위 에 brown 의 벡터 를 정의 한 다음 에 brown 의 여섯 번 째 요 소 를 바 꾸 어 새로운 벡터 blue 를 생 성 합 니 다. brown 과 blue 간 의 저장 구 조 는 다음 과 같 습 니 다.
    위의 그림 에서 보 듯 이 brown 데이터 구조 에서 요 소 를 변경 한 후에 원래 의 brown 데이터 구 조 는 head 지침 부터 전혀 바 뀌 지 않 았 다. 모든 vector 는 자신의 head 지침 이 있 기 때문에 blue 는 반드시 자신의 head 지침 을 구성 해 야 한다. 구조 과정 에서 brown 기 존의 데이터 구 조 를 공유 하고 변 경 된 잎 노드 만 새로 추 가 했 을 뿐이다.불필요 한 저장 공간의 낭 비 를 줄 였 다.    이런 이상 적 인 저장 방식 은 가 변 적 이지 않 은 데이터 구조의 삭제 작업 에 매우 유리 하 다. 시간 복잡 도 는 O (log 2 n) 이다. 실제 저장 에서 clojure 는 2 개의 키 노드 가 아 닌 32 개의 키 노드 의 저장 방식 을 취하 고 해당 하 는 시간 복잡 도 는 O (log 32 n) 이다.n 이 매우 큰 상황 에서 O (log 32 n) 와 O (log n) 의 복잡 도 는 같다 는 것 을 알 고 있 습 니 다. 그러나 상대 적 으로 작은 데이터 에 있어 O (log 32 n) 는 O (1) 와 비슷 할 수 있 습 니 다. 이것 은 clojure 가 왜 자신 이 vector 에 대한 첨삭 작업 이 상수 시간 에 가깝다 고 말 하 는 이유 입 니 다.
2. 왜 Transient Data Structures 가 있어 야 합 니까?
* 8195: 8195: 비록 vector 데이터 구조의 저장 방식 효율 이 높 지만 저장 공간 을 빈번하게 분배 하고 저장 공간 을 쓰레기 로 회수 해 야 합 니 다. 예 를 들 어 우 리 는 다음 과 같은 작업 을 수행 해 야 합 니 다.

    ;;   0 9     vector 
    (reduce conj [] (range 10))
    ;;=> [0 1 2 3 4 5 6 7 8 9]

    이 10 개의 수 를 배열 에 순서대로 넣 을 때마다 하나의 수 를 넣 을 때마다 헤드 포인터 가 있 는 새로운 vector 를 생산 합 니 다. 또한 앞의 vector 는 더 이상 사용 되 지 않 기 때문에 시스템 은 그 공간 에 대해 쓰레기 수 거 를 해 야 합 니 다. 앞 뒤 데이터 구조 에 저 장 된 공간 이 어느 정도 공유 되 지만 이런 조작 은 일정한 시간 을 낭비 할 수 있 습 니 다.효율 에 대한 요구 가 비교적 높 은 코드 는 받 아들 이기 어렵다.이 때문에 효율 을 높이 기 위해 클 로 저 는 Transient 데이터 형식 을 추 가 했 습 니 다. transient 는 클 로 저 데이터 구 조 를 바 꿀 수 있 습 니 다. transient 는 vector 뿐만 아니 라 set 와 map 에서 도 사용 할 수 있 지만 list 에 사용 할 수 없습니다.다음은 하나의 vector 의 요소 작업 을 업데이트 하여 transient 와 persistent 데이터 형식의 차 이 를 비교 하고 [1, 2, 3, 4, 5, 6] 을 [1, 2 F 4, 5, 6] 로 업데이트 합 니 다. 두 가지 서로 다른 데이터 유형 간 의 변화 과정 은 다음 과 같 습 니 다.
* 8195: persistent 업데이트 작업 후 두 개의 head 지침 이 있 고 두 개의 서로 다른 vector 가 있 습 니 다. transient 업데이트 작업 을 한 후에 기 존의 데이터 구 조 를 바탕 으로 한 개의 잎 노드 를 바 꾸 었 습 니 다. head 지침 이 변 하지 않 고 기 존의 vector 에 저 장 된 내용 이 바 뀌 었 기 때문에 transient 는 어느 정도 에 저장 공간의 낭 비 를 줄 였 습 니 다.코드 실행 효율 을 높 였 다.
3. Transient Data Structures 의 관련 조작 함수:
    읽 기 전용 조작 에 대해 데이터 내용 을 바 꾸 지 않 기 때문에 transient data 와 persistent data 는 읽 기 전용 조작 함수 한 세트 를 공유 합 니 다. 예 를 들 어 nth, get, count 등 함수 이지 만 데 이 터 를 변경 하 는 함수 에 대해 다른 조작 함수 가 있 습 니 다. 다음은 transient data structures 데이터 구조 와 관련 된 조작 함수 에 대한 상세 한 설명 입 니 다.

transient 함수:

    이 함 수 는 persistent 데이터 형식 을 transient 데이터 형식 으로 변환 하 는 것 입 니 다. 이 작업 의 시간 복잡 도 는 O (1) 에 가 깝 습 니 다. 만약 에 우리 가 변환 후의 변경 작업 을 하면 기 존의 데이터 내용 에 영향 을 주지 않 고 기 존의 데 이 터 는 여전히 persistent 입 니 다.

persistent!함수:

    이 함 수 는 transient 함수 와 반대로 transient 의 데이터 형식 을 persistent 형식 으로 변환 합 니 다. 다른 것 은 변환 후 기 존의 transient 데이터 에 영향 을 주어 기 존의 transient 데 이 터 를 사용 할 수 없 게 합 니 다.

    (def a [1 2 3])
    ;;=> #'insight.main/a
    ;; transient    transient     
    (def a' (transient a))
    ;;=> #'insight.main/a'
    ;;       
    (nth a' 2)
    ;;=> 3
    ;;    
    (conj! a' 4)
    ;; persistent！             
    (persistent! a')
    ;=> [1 2 3 4]
    ;;       a'          ，          
    (nth a' 2)
    IllegalAccessError Transient used after persistent! call  clojure.lang.PersistentVector$TransientVector.ensureEditable (PersistentVector.java:548)
    (conj! a' 4)
    IllegalAccessError Transient used after persistent! call  clojure.lang.PersistentVector$TransientVector.ensureEditable (PersistentVector.java:548)

관련 "쓰기" 조작 함수:

    transient 관련 '쓰기' 조작 함수 에 대해 서 는: assoc! /conj!/disassoc!/pop!/disj!，이 쓰기 조작 함 수 는 persistent 관련 함수 에 만 "!" 를 추가 합 니 다. 그들의 함수 매개 변수 형식 은 "!" 를 제거 한 후의 함수 와 똑 같 습 니 다. 아래 에 관련 조작 코드 를 열거 하 였 습 니 다.

    ;; 0 9       transient  vector ,         ，      vector，
    (loop [i 0 v (transient [])]
      (if ( [0 1 2 3 4 5 6 7 8 9]

특히 주의해 야 할 점:

    요 소 를 추가 할 때 기 존의 구조 에 요 소 를 추가 하 는 것 이지 만 이것 은 기 존의 데이터 구조의 헤드 포인터 (Head) 가 반드시 변 하지 않 는 다 는 것 을 의미 하지 않 는 다. 만약 에 추 가 된 요소 가 특히 많은 상황 에서 데이터 차원 구 조 를 새로 조정 해 야 한다 면 헤드 포인터 가 바 뀌 고 기 존의 데이터 구조의 헤드 포인 터 는 이 데이터 구조의 이름과 일일이 대응한다.따라서 이 transient 데 이 터 를 조작 할 때 작업 후의 데 이 터 를 기 존 데이터 의 이름 에 할당 해 야 합 니 다.

    ;;  8  t  key-value ，        
    (let [t (transient {})]
      (dotimes [i 8]
        (assoc! t i i))
      (persistent! t))
    ;;=> {0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7}
    ;;   9  t  key-value  ，        ，   9      ， map         ，             t
    (let [t (transient {})]
      (dotimes [i 9]
        (assoc! t i i))
      (persistent! t))
    ;;=> {0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7}

    정확 한 사용 추가 방식 은 다음 과 같 아야 합 니 다.

    ;;    reduce  ，        assoc!            ，           
    (persistent!
      (reduce (fn [t i] (assoc! t i i))
              (transient {})
              (range 10)))
    ;;=>{0 0, 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 5 5, 8 8}

4. clojure. cor e 라 이브 러 리 에서 transient data 관련 함수 와 효율 을 사용 합 니 다.
    는 어떤 상황 에서 Transient Data Structurese 를 적용 합 니까?우선, 우 리 는 변 경 된 데이터 에 만 신경 을 쓰 고 원시 데 이 터 는 우리 에 게 중요 하지 않 으 며 더 이상 사용 되 지 않 을 것 이다.그 다음으로 Transient Data Structures 는 단일 스 레 드 프로그램 에 적용 된다. 모든 스 레 드 가 같은 데 이 터 를 공유 할 때 동시에 변경 하면 병발 문 제 를 일 으 킬 수 있 기 때문이다. 이것 은 clojure 가 persistent 데이터 구 조 를 사용 하 는 이유 중 하나 이다.마지막 으로 과도 데이터 구 조 는 주로 코드 효율 을 높이 기 위해 설계 되 었 기 때문에 여러 번 연속 으로 요 소 를 추가 하 는 데 transient 데이터 형식 을 사용 하 는 것 을 고려 할 수 있다.    clojure. cor e 라 이브 러 리 의 관련 함수 정의 원본 코드 에 대한 검색 을 통 해 transient data structure 관련 함 수 를 찾 아 냈 습 니 다. set 함수 / into 함수 / mapv 함수 / filterv 함수 / group - by 함수 / freequencies 함수 입 니 다. 우 리 는 이러한 함수 들 의 특징 이 모두 한 서열 에 대해 변경 작업 을 하 는 것 임 을 알 수 있 지만 원시 데이터 의 내용 에 관심 이 없습니다.다음은 criterium. cor e 라 이브 러 리 의 quick - bench 함수 로 코드 운행 시간 을 테스트 하여 transient data 의 효율 을 증명 합 니 다.

    ;;into         ：
    ;; concat        vector list，        vector，       ：4.354145 µs
    (quick-bench (vec (concat [1 2 3] (range 100 200))))
    ;;Evaluation count : 154098 in 6 samples of 25683 calls.
    ;;Execution time mean : 4.354145 µs

    ;;    into     list         vector ，         1.549213 µs
    (quick-bench (into [1 2 3] (range 100 200)))
    ;;Evaluation count : 382944 in 6 samples of 63824 calls.
    ;;Execution time mean : 1.549213 µs

    ;;mapv         ：

    ;;       mapv'   mapv        
    (defn mapv' [f coll]
      (loop [result [] r coll]
        (if (nil? (seq r))
          result
          (recur (conj result (f (first r))) (rest r))
          )))

    ;;           ，       794.484682 µs
    (quick-bench (mapv' inc (range 10000)))
    ;;Evaluation count : 780 in 6 samples of 130 calls.
    ;;Execution time mean : 794.484682 µs

    ;;     mapv  ，       197.386935 µs
    (quick-bench (mapv inc (range 10000)))
    ;;Evaluation count : 3090 in 6 samples of 515 calls.
    ;;Execution time mean : 197.386935 µs

    ;;  map vec    ，       418.949804 µs
    (quick-bench (vec (map inc (range 10000))))
    ;;Evaluation count : 1482 in 6 samples of 247 calls.
    ;;Execution time mean : 418.949804 µs

    상기 함수 에 대한 대 비 를 통 해 우 리 는 transient 함수 가 빅 데 이 터 를 조작 하 는 상황 에서 확실히 우리 에 게 많은 시간 을 절약 할 수 있다 는 것 을 알 게 되 었 다. 그래서 평소에 코드 를 쓸 때 반드시 좋 은 습관 을 길러 야 한다. 코드 효율 을 높이 기 위해 상기 에서 언급 한 편 지 를 되도록 사용 해 야 한다.
5. 요약:
    오늘 은 주로 방금 배 운 transient data structures 를 귀납 적 으로 정리 했다. 과도 데이터 구 조 는 코드 효율 의 향상 에 큰 역할 을 한다. 이 데이터 유형 은 map, vector, map 에 응용 할 수 있다. 만약 에 우리 가 원시 데이터 에 관심 이 없다 면 변 경 된 데이터, 특히 여러 번 이런 조작 을 할 수 있다.그러면 우 리 는 과도 데이터 구 조 를 사용 하 는 것 을 고려 할 수 있 습 니 다. clojure. core 에서 일부 함 수 는 과도 데이터 구 조 를 사 용 했 기 때문에 우 리 는 가능 한 한 인 코딩 할 때 이런 함 수 를 사용 하여 코드 효율 을 높 일 수 있 습 니 다.
클 라 우 드 안전 (방패) 콘 텐 츠 안전, 인증 코드 등 서비스 무료 체험
더 많은 왕 이 기술, 제품, 운영 경험 공유 클릭 하 세 요.
추천 [전문가 출석] 네 가지 병행 프로 그래 밍 모델 소개 [추천] 브 라 우 저 에서 사용 할 NPM 패 키 지 를 만 듭 니 다.