데이터 구조

데이터 구조 (Data Structures)

Clojure는 풍부한 데이터 구조 집합을 가져요. 그것들은 공통된 성질들을 공유해요:

불변(immutable)이다
읽을 수 있다(read-able)
equals 구현에서 올바른 값 동등성 의미를 지원한다
좋은 해시 값을 제공한다
추가로, 컬렉션들은:
- 인터페이스로 조작된다
- 시퀀싱을 지원한다
- 지속적(persistent) 조작을 지원한다
- 메타데이터를 지원한다
- java.lang.Iterable을 구현한다
- java.util.Collection 또는 java.util.Map의 비-선택(읽기 전용) 부분을 구현한다

출처: Data Structures

본문

nil

nil은 Clojure에서 어떤 데이터 타입의 값이든 될 수 있어요. nil은 Java의 null과 같은 값을 가져요. Clojure 조건 시스템은 nil과 false에 기반하며, nil과 false는 조건 테스트에서 논리적 거짓 값을 나타내고, 그 외 무엇이든 논리적 참이에요. 또한 nil은 시퀀스 프로토콜에서 시퀀스-종료 센티널 값으로 사용돼요.

숫자 (Numbers)

Clojure는 기본적으로 JVM 프리미티브 값에 대한 완전한 지원을 제공해, 숫자 애플리케이션을 위한 고성능의 관용적 Clojure 코드를 가능하게 해요.

Clojure는 java.lang.Number에서 파생된 Java 박싱 숫자 타입(BigInteger와 BigDecimal 포함)과 자체 Ratio 타입도 지원해요. 특별한 처리가 몇 가지 있어요:

Longs

기본적으로 Clojure는 자연수를 Java의 long 프리미티브 타입의 인스턴스로 다뤄요. 프리미티브 정수 연산 결과가 프리미티브 값에 들어가기엔 너무 클 때 java.lang.ArithmeticException이 던져져요. Clojure는 아포스트로피로 끝나는 대체 수학 연산자 집합을 제공해요: +', -', *', inc', dec'. 이 연산자들은 오버플로 시 BigInt로 자동 승격되지만, 일반 수학 연산자보다 덜 효율적이에요.

Ratio

정수 사이의 비율을 나타내요. 정수로 줄일 수 없는 정수의 나눗셈은 부동소수나 잘린 값 대신 비율을 산출해요, 즉 22/7 = 22/7이에요.

전염 (Contagion)

BigInt와 부동소수 타입은 연산에 걸쳐 "전염성(contagious)"이 있어요. 즉 BigInt를 포함하는 정수 연산은 BigInt를 결과로 내고, double이나 float을 포함하는 연산은 double을 결과로 내요.

BigInt와 BigDecimal 리터럴

BigInt와 BigDecimal의 숫자 리터럴은 각각 접미사 N과 M으로 지정돼요.

| 예시 표현식 | 반환 값 | | (== 1 1.0 1M) | true | | (/ 2 3) | 2/3 | | (/ 2.0 3) | 0.6666666666666666 | | (map #(Math/abs %) (range -3 3)) | (3 2 1 0 1 2) | | (class 36786883868216818816N) | clojure.lang.BigInt | | (class 3.14159265358M) | java.math.BigDecimal |

문자열 (Strings)

Clojure 문자열은 Java의 String이에요. Printing도 참조해요.

user=> (map (fn [x] (.toUpperCase x)) (.split "Dasher Dancer Prancer" " "))
("DASHER" "DANCER" "PRANCER")

문자 (Characters)

Clojure 문자는 Java의 Character예요.

키워드 (Keywords)

키워드는 스스로로 평가되는 상징적 식별자예요. 그것들은 매우 빠른 동등성 테스트를 제공해요. Symbol처럼, 이름과 선택적 네임스페이스를 가지며, 둘 다 문자열이에요. 앞의 :는 네임스페이스나 이름의 일부가 아니에요.

키워드는 한 인자(맵)의 invoke()를 위한 IFn을 선택적 두 번째 인자(기본 값)와 함께 구현해요. 예를 들어 (:mykey my-hash-map :none)은 (get my-hash-map :mykey :none)과 같은 뜻이에요. get을 참조해요.

Symbol

Symbol은 보통 다른 무엇을 가리키는 데 사용되는 식별자예요. 프로그램 형식에서 함수 파라미터, let 바인딩, 클래스 이름, 클래스 멤버, 전역 var를 가리키는 데 사용될 수 있어요. 이름과 선택적 네임스페이스를 가지며, 둘 다 문자열이에요. Symbol은 메타데이터를 가질 수 있어요(with-meta 참조).

Symbol은 키워드처럼 한 인자(맵)의 invoke()를 위한 IFn을 선택적 두 번째 인자(기본 값)와 함께 구현해요. 예를 들어 ('mysym my-hash-map :none)은 (get my-hash-map 'mysym :none)과 같은 뜻이에요. get을 참조해요.

컬렉션 (Collections)

모든 Clojure 컬렉션은 불변이고 지속적(persistent)이에요. 특히 Clojure 컬렉션은 구조적 공유(structural sharing)를 활용해 '수정된' 버전의 효율적 생성을 지원하며, 지속적 사용에 대한 모든 성능 보장을 지켜요. 컬렉션은 효율적이고 본질적으로 스레드-안전해요. 컬렉션은 추상화로 표현되며, 하나 이상의 구체적인 실현이 있을 수 있어요. 특히 '수정' 연산이 새 컬렉션을 산출하므로, 새 컬렉션은 원본 컬렉션과 같은 구체적 타입이 아닐 수 있지만 같은 논리적(인터페이스) 타입을 가져요.

모든 컬렉션은 크기를 얻기 위한 count, 컬렉션에 '추가'하는 conj, 전체 컬렉션을 순회할 수 있는 시퀀스를 얻는 seq를 지원하지만, 그 특정 동작은 컬렉션 타입에 따라 조금씩 달라요.

컬렉션이 seq 함수를 지원하므로, 모든 시퀀스 함수를 어떤 컬렉션과도 사용할 수 있어요.

Java 컬렉션 해시

Java 컬렉션 인터페이스는 hashCode() 값 계산을 위한 알고리즘을 Lists, Sets, Maps에 지정해요. 모든 Clojure 컬렉션은 hashCode() 구현에서 이 명세들을 따르지 않아요.

Clojure 컬렉션 해시

Clojure는 컬렉션(과 다른 타입)에 더 나은 해시 성질을 제공하는 자체 해시 계산인 hasheq 값을 제공해요.

IHashEq 인터페이스는 hasheq 값을 얻기 위한 hasheq() 함수를 제공하는 컬렉션을 표시해요. Clojure에서 hash 함수를 hasheq 값 계산에 사용할 수 있어요.

순서 있는 컬렉션(벡터, 리스트, seq 등)은 hasheq 계산에 다음 알고리즘을 사용해야 해요(여기서 hash는 hasheq를 계산). 정수 오버플로 계산을 얻기 위해 unchecked-add-int와 unchecked-multiply-int가 사용됨을 유의해요.

(defn hash-ordered [collection]
  (-> (reduce (fn [acc e] (unchecked-add-int
                            (unchecked-multiply-int 31 acc)
                            (hash e)))
              1
              collection)
      (mix-collection-hash (count collection))))

순서 없는 컬렉션(맵, 셋)은 hasheq 계산에 다음 알고리즘을 사용해야 해요. 맵 항목은 키와 값의 순서 있는 컬렉션으로 취급돼요. 정수 오버플로 계산을 얻기 위해 unchecked-add-int가 사용됨을 유의해요.

(defn hash-unordered [collection]
  (-> (reduce unchecked-add-int 0 (map hash collection))
      (mix-collection-hash (count collection))))

mix-collection-hash 알고리즘은 변경될 수 있는 구현 세부 사항이에요.

리스트 (Lists, IPersistentList)

리스트는 컬렉션이에요. 그것들은 ISeq 인터페이스를 직접 구현해요. (빈 리스트도 ISeq를 구현하지만, seq 함수는 빈 시퀀스에 대해 항상 nil을 반환해요.) count는 O(1)이에요. conj는 항목을 리스트 앞에 놓아요.

벡터 (Vectors, IPersistentVector)

벡터는 연속된 정수로 색인된 값들의 컬렉션이에요. 벡터는 log32N 홉으로 항목에 색인 접근을 지원해요. count는 O(1)이에요. conj는 항목을 벡터 끝에 놓아요. 벡터는 항목을 역순으로 반환하는 rseq도 지원해요. 벡터는 한 인자(색인으로 가정하고, 세 번째에 있는 것처럼 자신을 조회)의 invoke()를 위한 IFn을 구현해요, 즉 벡터는 자신의 색인의 함수예요. 벡터는 먼저 길이로 비교되고, 그다음 각 요소가 순서대로 비교돼요.

맵 (Maps, IPersistentMap)

맵은 키를 값에 매핑하는 컬렉션이에요. 두 가지 다른 맵 타입이 제공돼요 — 해시맵과 정렬맵. 해시맵은 hashCode와 equals를 올바르게 지원하는 키를 요구해요. 정렬맵은 Comparable을 구현하거나 Comparator의 인스턴스인 키를 요구해요. 해시맵은 더 빠른 접근(log32N 홉) 대 (logN 홉)을 제공하지만, 정렬맵은, 음, 정렬돼 있어요. count는 O(1)이에요. conj는 항목으로서 (단일 항목일 수 있는) 다른 맵을 기대하고, 이전 맵에 새 것의 항목들을 더한 새 맵을 반환하며, 새 것이 이전 것을 덮어쓸 수 있어요. conj는 MapEntry나 두 항목(키와 값)의 벡터도 받아요. seq는 키/값 쌍인 맵 항목의 시퀀스를 반환해요. 정렬맵은 항목을 역순으로 반환하는 rseq도 지원해요. 맵은 한 인자(키)의 invoke()를 선택적 두 번째 인자(기본 값)와 함께 위한 IFn을 구현해요, 즉 맵은 자신의 키의 함수예요. nil 키와 값은 괜찮아요.

StructMap

참고: 대부분의 StructMap 사용은 이제 records로 더 잘 다뤄져요.

종종 많은 맵 인스턴스가 같은 기본 키 집합을 가지며, 예를 들어 맵이 다른 언어에서 struct나 object로 사용될 때처럼이에요. StructMap은 키 정보를 효율적으로 공유하면서 그 키들에 대한 선택적 성능 향상 접근자도 제공해 이 사용 사례를 지원해요. StructMap은 모든 면에서 맵이며, 같은 함수 집합을 지원하고, 모든 다른 맵과 상호 운용되며, 지속적으로 확장 가능해요(즉 struct 맵은 기본 키로 제한되지 않아요). 유일한 제약은 struct 맵을 기본 키 중 하나로부터 dissociate할 수 없다는 점이에요. struct 맵은 기본 키를 순서대로 유지해요.

StructMap은 먼저 create-struct나 defstruct로 구조 기본(structural basis) 객체를 만든 다음, struct-map이나 struct로 인스턴스를 만들면서 생성돼요.

(defstruct desilu :fred :ricky)
(def x (map (fn [n]
              (struct-map desilu
                :fred n
                :ricky 2
                :lucy 3
                :ethel 4))
             (range 100000)))
(def fred (accessor desilu :fred))
(reduce (fn [n y] (+ n (:fred y))) 0 x)
 -> 4999950000
(reduce (fn [n y] (+ n (fred y))) 0 x)
 -> 4999950000

ArrayMap

코드 형식 조작을 할 때 키 순서를 유지하는 맵을 가지는 것이 바람직한 경우가 많아요. ArrayMap은 그런 맵이에요 — 키 값 키 값...의 배열로 단순히 구현돼요. 따라서 선형 조회 성능을 가지며 매우 작은 맵에만 적합해요. 완전한 맵 인터페이스를 구현해요. 새 ArrayMap은 array-map 함수로 만들 수 있어요. ArrayMap은 '수정'되지 않았을 때만 정렬 순서를 유지함을 유의해요. 이후의 assoc-ing은 결국 그것을 해시맵으로 '만들어요'.

셋 (Sets)

셋은 고유 값들의 컬렉션이에요.

해시 셋에 대한 리터럴 지원이 있어요:

#{:a :b :c :d}
-> #{:d :a :b :c}

hash-set와 sorted-set 함수로 셋을 만들 수 있어요:

(hash-set :a :b :c :d)
-> #{:d :a :b :c}

(sorted-set :a :b :c :d)
-> #{:a :b :c :d}

set 함수로 컬렉션에 있는 값들의 셋을 얻을 수도 있어요:

(set [1 2 3 2 1 2 3])
-> #{1 2 3}

셋은 컬렉션이에요:

(def s #{:a :b :c :d})
(conj s :e)
-> #{:d :a :b :e :c}

(count s)
-> 4

(seq s)
-> (:d :a :b :c)

(= (conj s :e) #{:a :b :c :d :e})
-> true

셋은 disj로 '제거'를, 그리고 _contains?_와 _get_도 지원하며, 후자는 발견되면 키와 동등하게 비교되는 셋에 잡힌 객체를 반환해요:

(disj s :d)
-> #{:a :b :c}

(contains? s :b)
-> true

(get s :a)
-> :a

셋은 _Get_을 사용해 자신의 멤버의 함수예요:

(s :b)
-> :b

(s :k)
-> nil

Clojure는 union / difference / intersection 같은 기본 셋 연산과, '관계(relations)'를 위한 의사 관계대수 지원도 제공하는데, 관계는 단순히 맵의 셋이에요 — select / index / rename / join.

데이터 구조