前回は「ベクタ (vector)」について説明しました。今回は Clojure の基本的なコレクションである「マップ (Map)」と「セット (Set)」について説明します。
マップは「連想配列」のことで、Perl や Ruby では「ハッシュ (Hash)」と呼ばれています。ベクタが整数値を使って要素を指定するのに対し、マップはキー (key) というデータを使って要素を指定します。一般に、連想配列のキーには文字列が用いられますが、Clojure では immutable なデータであれば、マップのキーとして使用することができます。
Perl や Ruby で連想配列をハッシュと呼ぶのは、連想配列を実現するアルゴリズムに「ハッシュ法 (hashing)」が用いられているからです。Clojure の場合、マップは不変 (immutable) なデータ型で、Array Map, Hash Map, Sorted Map の 3 種類があります。Array Map は配列を使った単純な実装方法で、Hash Map はハッシュ法を、Sorted Map は木構造を使って実装されています。
ハッシュ法はデータを高速に探索できるアルゴリズムです。線形探索では時間がとてもかかる処理でも、マップを遣うと高速にデータを探索することができます。ハッシュ法 (ハッシュ表) のアルゴリズムに興味のある方は、拙作のページ Algorithms with Python 「ハッシュ法」をお読みくださいませ。
マップは次の方法で作成します。
マップは波カッコ '{' と '}' で囲み、キー key と値 value を空白で区切って表します。{ } は要素が一つもない空マップになります。{ ... } は read で読み込むことができる形式で、プログラムの中で指定することもできます。生成されるマップは Array Map です。関数 array-map は Array Map を、hash-map は Hash Map を、sorted-map は Sorted Map を生成します。sorted-map-by は引数 comp に比較関数を渡します。
簡単な例を示しましょう。
user=> (def a {:foo 10 :bar 20 :baz 30})
#'user/a
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (type a)
clojure.lang.PersistentArrayMap
user=> (array-map :bar 20, :foo 10, :baz 30)
{:bar 20, :foo 10, :baz 30}
user=> (first a)
[:foo 10]
user=> (first (array-map :bar 20, :foo 10, :baz 30))
[:bar 20]
user=> (= a (array-map :bar 20, :foo 10, :baz 30))
true
user=> (map? a)
true
user=> (map? 1)
false
user=> (count a)
3
type は引数のデータ型 (Java のクラス) を調べる関数です。Clojure はカンマ ( , ) を空白文字として扱います。REPL では、キーと値を組にしてカンマで区切って表示します。データの入力やプログラムでもカンマを使うことができます。
Array Map は入力したデータの順番を保持します。関数 first を適用すると、先頭のペア (キーと値を格納したベクタ) を求めることができます。データ入力の順番によって first の返り値は異なります。ただし、マップの中身 (キーと値) が同じであれば、述語 = で比較すると true を返します。データ型のチェックは型述語 map? を使います。マップの大きさは関数 count で求めることができます。
user=> (def b (hash-map :foo 10 :bar 20 :baz 30))
#'user/b
user=> b
{:baz 30, :bar 20, :foo 10}
user=> (type b)
clojure.lang.PersistentHashMap
user=> (= a b)
true
user=> (def c (sorted-map :foo 10 :bar 20 :baz 30))
#'user/c
user=> c
{:bar 20, :baz 30, :foo 10}
user=> (type c)
clojure.lang.PersistentTreeMap
user=> (first c)
[:bar 20]
user=> (last c)
[:foo 10]
user=> (sorted-map-by < 10 "foo", 30 "baz", 20 "bar")
{10 "foo", 20 "bar", 30 "baz"}
user=> (sorted-map-by > 10 "foo", 30 "baz", 20 "bar")
{30 "baz", 20 "bar", 10 "foo"}
user=> (= a c)
true
user=> (= b c)
true
関数 hash-map は Hash Map を生成します。REPL で表示されるデータの順番は、ハッシュ法の実装アルゴリズムに依存します。関数 sorted-map は Sorted Map を生成します。Sorted Map はキーを基準にソートした状態を保ちます。first で最小のペアを、last で最大のペアを求めることができます。デフォルトの比較関数は compare です。比較関数を変更する場合は sorted-map-by を使います。どのマップでも中身 (キーと値) が同じであれば、述語 = は true を返します。
Array Map は単純な実装方法なので、データ数が多くなるとキーの探索速度は遅くなります。Array Map で実用的なデータ数は一桁程度のようです。実際、Array Map にデータを追加したとき、8 個を超えると Hash Map に変換されます。
キーに対応する値を求めるには関数 get を使います。
マップ map にキー key があれば、その値を返します。キーが見つからない場合は nil を返します。第 3 引数に not-found を指定すると、キーが見つからない場合は not-found を返します。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (get a :foo)
10
user=> (get a :oops)
nil
user=> (get a :oops -1)
-1
また、マップは関数のように呼び出すことができます。(map key) を評価すると、key の値を求めることができます。関数 contains? はマップにキーが含まれていると true を返します。関数 find はマップからキーを探し、見つけた場合はペア (キーと値を格納したベクタ) を返します。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (a :bar)
20
user=> (a :oops)
nil
user=> (a :oops -1)
-1
user=> (contains? a :baz)
true
user=> (contains? a :oops)
false
user=> (find a :foo)
[:foo 10]
user=> (find a :oops)
nil
データの追加は関数 assoc を使います。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (def d (assoc a :oops 40))
#'user/d
user=> d
{:foo 10, :bar 20, :baz 30, :oops 40}
user=> (get d :oops)
40
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (assoc a :baz 100)
{:foo 10, :bar 20, :baz 100}
(assoc a :oops 40) は、マップ a に :oops と 40 を追加した新しいマップを生成します。キー key が存在している場合は、その値を value に置き換えた新しいマップを生成して返します。
マップは conj を使ってもデータを追加することができます。
引数にキーと値のペアを渡すところが異なるだけで、あとの動作は assoc と同じです。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (conj a [:oops 40])
{:foo 10, :bar 20, :baz 30, :oops 40}
user=> (conj a [:oops 40] [:baz 50])
{:foo 10, :bar 20, :baz 50, :oops 40}
user=> (conj a [:foo 100] [:baz 50])
{:foo 100, :bar 20, :baz 50}
データの削除は関数 dissoc で行います。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (dissoc a :foo)
{:bar 20, :baz 30}
user=> (dissoc a :foo :baz)
{:bar 20}
user=> (dissoc a :oops)
{:foo 10, :bar 20, :baz 30}
user=> (identical? a (dissoc a :oops))
true
dissoc は引数の map からキーとその値を削除した新しいマップを生成して返します。キーが見つからない場合は、引数の map をそのまま返します。
Clojure のマップは immutable ですが、キーや値を更新した新しいマップを生成することはできます。
関数 update は key の値を val とすると、(func val args ...) の評価結果が新しい値になります。update-vals は map の値を val とすると、それを (func val) の評価結果に置き換えた新しいマップを返します。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (update a :foo inc)
{:foo 11, :bar 20, :baz 30}
user=> (update a :foo + 10)
{:foo 20, :bar 20, :baz 30}
user=> (update-vals a dec)
{:foo 9, :bar 19, :baz 29}
user=> (update-vals a #(- % 10))
{:foo 0, :bar 10, :baz 20}
update-keys は map のキーを key とすると、それを (func key) の評価結果に置き換えた新しいマップを返します。
user=> (symbol :foo)
foo
user=> (update-keys a symbol)
{foo 10, bar 20, baz 30}
関数 symbol は引数をシンボルに変換します。
関数 keys は引数 map のキーをシーケンスに格納して返します。関数 vals は map の値をシーケンスに格納して返します。関数 zipmap はキーを格納したシーケンス ks と値を格納したシーケンス vs からマップを生成します。merge は複数のマップを併合して一つのマップを生成します。関数 seq は引数 coll をシーケンスに変換します。coll がマップの場合、ペア (キーと値を格納したベクタ) を格納したシーケンスを返します。
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (keys a)
(:foo :bar :baz)
user=> (vals a)
(10 20 30)
user=> (zipmap [:a :b :c] [1 2 3])
{:a 1, :b 2, :c 3}
user=> (merge {:a 1 :b 2} {:c 3 :d 4})
{:a 1, :b 2, :c 3, :d 4}
user=> (merge {:a 1 :b 2 :c 3} {:d 4 :e 5 :c 6})
{:a 1, :b 2, :c 6, :d 4, :e 5}
user=> (merge)
nil
user=> (seq a)
([:foo 10] [:bar 20] [:baz 30])
分配束縛はマップを使っても行うことができます。
[{変数名 キー ...} {キー 値 ...} ...]
左側の { } の中で変数の定義と初期値の指定を行います。初期値の指定にはキーを使います。すると、右側のマップからキーを検索し、その値が変数の初期値となります。キーが見つからない場合、変数は nil に初期化されます。
簡単な実行例を示します。
user=> (let [{a :a b :b} {:a 10 :b 20}] (println a b))
10 20
nil
user=> (let [{a :a b :b c :c} {:a 10 :b 20}] (println a b c))
10 20 nil
nil
user=> a
{:foo 10, :bar 20, :baz 30}
user=> (let [{x :foo y :bar z :baz} a] (println x y z))
10 20 30
nil
キーと同じ名前の変数を定義する場合、次のキーワードを使うと便利です。
簡単な実行例を示します。
user=> (let [{:keys [a b]} {:a 10 :b 20}] (println a b))
10 20
nil
user=> (let [{:strs [a b]} {"a" 10 "b" 20}] (println a b))
10 20
nil
user=> (let [{:syms [a b]} {'a 10 'b 20}] (println a b))
10 20
nil
キーワード :or を使うと変数のデフォルト値を指定することができます。
[{:keys [変数名 ...] :or {変数名 デフォルト値 ...}} ...]
:or の後ろのマップで変数に対応するデフォルト値を指定します。キーが見つからない場合はデフォルト値が使用されます。簡単な実行例を示します。
user=> (let [{:keys [a b c] :or {a 1 b 2 c 3}} {:a 10 :b 20}] (println a b c))
10 20 3
nil
user=> (let [{:keys [a b c] :or {a 1 b 2 c 3}} {:b 20}] (println a b c))
1 20 3
nil
user=> (let [{:keys [a b c] :or {a 1 b 2 c 3}} {}] (println a b c))
1 2 3
nil
それから、マップの分配束縛は入れ子にすることができ、ベクタの分配束縛と混在してもかまいません。
user=> (let [{{:keys [a b]} :x {:keys [c d]} :y} {:x {:a 1 :b 2} :y {:c 3 :d 4}}]
(println a b c d))
1 2 3 4
nil
user=> (let [[{:keys [a b]} {:keys [c d]}] [{:a 1 :b 2} {:c 3 :d 4}]]
(println a b c d))
1 2 3 4
nil
分配束縛はとても便利な機能です。興味のある方は Clojure のリファレンスマニュアルをお読みくださいませ。
「セット (Set)」はリストやマップのように要素を格納するコレクションですが、リストと違って要素に順番はなく、重複した要素を含まないところが特徴です。セットはデータの集合を表すのに便利なデータ型です。集合は要素の順番に意味はありません。たとえば集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合もあります。なお、Clojure のセットは immutable です。
セットは次の方法で作成します。
セットは #{ ... } の中に要素を空白で区切って記述します。#{ } は要素が一つもない空セットになります。#{ ... } は read で読み込むことができる形式で、プログラムの中で指定することもできます。生成されるセットは Hash Set です。
関数 set はコレクション coll を Hash Set に変換します。hash-set は引数を格納した Hash Set を返します。sorted-set は引数を格納した Sorted Set を返します。Hash Set は実装方法にハッシュ法を、Sorted Set は木構造を用いています。sorted-set-by は引数 comp に比較関数を渡します。
簡単な例を示しましょう。
user=> (def a #{1 2 3 4 5})
#'user/a
user=> a
#{1 4 3 2 5}
user=> #{1 2 3 4 5 1 3 5}
Error
user=> (type a)
clojure.lang.PersistentHashSet
user=> (set '(1 2 3 4 5))
#{1 4 3 2 5}
user=> (set '(1 2 3 4 5 1 3 5))
#{1 4 3 2 5}
user=> (hash-set 1 2 3 4 5)
#{1 4 3 2 5}
(set? a)
true
(set? 1)
false
(count a)
5
#{ ... } でセットを生成する場合、重複要素があるとエラーになります。set, hash-set の場合、重複要素はひとつだけセットに登録されます。データ型のチェックは型述語 set? を使います。マップの大きさは関数 count で求めることができます。
user=> (def b (sorted-set 1 2 3 4 5))
#'user/b
user=> b
#{1 2 3 4 5}
user=> (type b)
clojure.lang.PersistentTreeSet
user=> (first b)
1
user=> (last b)
5
user=> (= a b)
true
user=> (sorted-set-by > 1 2 3 4 5)
#{5 4 3 2 1}
user=> (sorted-set-by < 1 2 3 4 5)
#{1 2 3 4 5}
関数 sorted-set は Sorted Set を生成します。Sorted set は要素をソートした状態に保ちます。first で最小の要素を、last で最大の要素を求めることができます。デフォルトの比較関数は compare です。比較関数を変更する場合は sorted-set-by を使います。どのセットでも全ての要素が同じであれば、述語 = は true を返します。
セットの要素を取得するには関数 get を使います。
セット s に要素 item があれば、それ返します。item が見つからない場合は nil を返します。第 3 引数に not-found を指定すると、item が見つからない場合は not-found を返します。
user=> a
#{1 4 3 2 5}
user=> (get a 1)
1
user=> (get a 10)
nil
user=> (get a 10 -1)
-1
また、セットは関数のように呼び出すことができます。(set item) を評価すると、item を求めることができます。ただし、第 2 引数に not-found を指定することはできません。関数 contains? はセットに item が含まれていると true を返します。
user=> (a 1) 1 user=> (a 10) nil user=> (a 10 -1) Error user=> (contains? a 1) true user=> (contains? a 10) false
データの追加は conj で、削除は disj で行います。
conj は set に引数の item を追加します。重複要素がある場合は追加されません。disj は set から引数の item を削除します。item が見つからない場合は無視されます。
user=> a
#{1 4 3 2 5}
user=> (conj a 6 7 8)
#{7 1 4 6 3 2 5 8}
user=> (conj a 1 3 5)
#{1 4 3 2 5}
user=> (disj a 1 3 5)
#{4 2}
user=> (disj a 6 7 8)
#{1 4 3 2 5}
セットは集合を扱う関数が用意されています。主な関数を下表に示します。
| 関数 | 機能 |
|---|---|
| union [s ...] | 引数の和集合を求める |
| intersection s [s1 ...} | 引数の積集合を求める |
| difference s [s1 ...} | s から残りの引数を引いた集合 (差集合) を求める |
| select pred s | s から述語 pred が真を返す要素を求める |
| subset? s1 s2 | s1 が s2 の部分集合であれば真を返す |
| superset? s1 s2 | s1 が s2 の上位集合であれば真を返す |
これらの関数を使う場合、Clojure のライブラリ clojure.set をロードします。ライブラリのロードは関数 require で行います。
require 'lib-name require '[lib-name :as alias]
関数呼び出しは lib-name/func-name とします。:as を使って別名 alias を付けることもできます。ほかにもいろいろな機能があるので、詳細は Clojure のリファレンスマニュアルをお読みください。簡単な例を示しましょう。
user=> (require '[clojure.set :as set])
nil
user=> (def a #{1 2 3 4})
#'user/a
user=> a
#{1 4 3 2}
user=> (def b #{3 4 5 6})
#'user/b
user=> b
#{4 6 3 5}
user=> (set/union a b)
#{1 4 6 3 2 5}
user=> (set/intersection a b)
#{4 3}
user=> (set/difference a b)
#{1 2}
user=> (set/difference b a)
#{6 5}
user=> (set/select odd? a)
#{1 3}
user=> (set/subset? #{1 2} a)
true
user=> (set/subset? #{3 4} a)
true
user=> (set/subset? #{5 6} a)
false
user=> (set/superset? a #{2 3})
true
user=> (set/superset? a #{5})
false
一般に、複数の要素を格納するデータ型を「コンテナ (container)」とか「コレクション (collection)」と呼びます。これまでに説明したリスト、ベクタ、マップ、セットがコレクションになります。Clojure はこれらのデータ型を操作する共通な関数が用意されています。今までにも、count, empty?, conj などを使ってきましたが、ここで他の関数も簡単に説明しておきましょう。
doseq と for はコレクションでも動作します。マップとセットは seq を適用した結果と同じになります。簡単な例を示しましょう。
user=> (doseq [x '(1 2 3 4)] (println x))
1
2
3
4
nil
user=> (doseq [x [1 2 3 4]] (println x))
1
2
3
4
nil
user=> (doseq [x {1 2 3 4}] (println x))
[1 2]
[3 4]
nil
user=> (doseq [x #{1 2 3 4}] (println x))
1
4
3
2
nil
user=> (for [x '(1 2 3 4)] x)
(1 2 3 4)
user=> (for [x [1 2 3 4]] x)
(1 2 3 4)
user=> (for [x {1 2 3 4}] x)
([1 2] [3 4])
user=> (for [x #{1 2 3 4}] x)
(1 4 3 2)
apply は最後の引数がコレクションでも動作します。この場合も最後の引数に seq を適用した結果と同じになります。
user=> (apply list '(1 2 3 4))
(1 2 3 4)
user=> (apply list [1 2 3 4])
(1 2 3 4)
user=> (apply list {1 2 3 4})
([1 2] [3 4])
user=> (apply list #{1 2 3 4})
(1 4 3 2)
into はコレクション from の要素をコレクション to に追加した新しいコレクションを返します。生成されるコレクションの型は to と同じです。基本的には次の S 式と同じ動作になります。
(into to from) ≡ (apply conj to from)
user=> (into '(1 2 3) [4 5 6])
(6 5 4 1 2 3)
user=> (into [1 2 3] [4 5 6])
[1 2 3 4 5 6]
user=> (into #{1 2 3} [4 5 6])
#{1 4 6 3 2 5}
user=> (into {1 2 3 4} [[5 6] [7 8]])
{1 2, 3 4, 5 6, 7 8}
(info to xform from) は (info to (xform from)) と同じです。つまり、form を xform で変換した結果を to に追加します。Clojure の場合、map, filter, remove など高階関数は、カリー化関数のような使い方が可能です。たとえば、(map #(% %)) を評価すれば、リストの要素を 2 乗する関数を返します。
user=>: (into '(1 2 3) (map #(* % %)) [4 5 6])
(36 25 16 1 2 3)
user=> (into [1 2 3] (filter even?) [4 5 6])
[1 2 3 4 6]
user=>: (into #{1 2 3} (remove even?) [4 5 6 7])
#{7 1 3 2 5}
user=>: (into {1 2 3 4} (map (fn [[x y]] [x (* y 2)])) [[5 6] [7 8]])
{1 2, 3 4, 5 12, 7 16}
every? はコレクション coll の要素に述語 pred を適用し、一つでも偽を返す要素があれば偽を返します。すべての要素が真を返す場合、every? は真を返します。not-every? は (not (every? ...)) と同じです。some はリストの要素に述語 pred を適用し、ひとつでも真を返す要素があれば真を返します。すべての要素が偽を返す場合、some は偽を返します。not-any? は (not (some ...)) と同じです。
user=> (every? odd? '(1 3 5 7 9))
true
user=> (every? odd? '(1 2 3 5 7 9))
false
user=> (not-every? odd? '(1 3 5 7 9))
false
user=> (not-every? odd? '(1 2 3 5 7 9))
true
user=> (some even? '(1 2 3 5 7 9))
true
user=> (some even? '(1 3 5 7 9))
nil
user=> (not-any? even? '(1 2 3 5 7 9))
false
user=> (not-any? even? '(1 3 5 7 9))
true
user=> (every? (fn [[_ v]] (odd? v)) {:foo 1 :bar 3 :baz 5})
true
user=> (every? (fn [[_ v]] (odd? v)) {:foo 1 :bar 3 :baz 5 :oops 0})
false
distinct? は引数に重複がなければ true を返し、重複があれば false を返します。distinct は引数 coll から重複要素を取り除いた新しいコレクションを返します。
user=> (distinct? 1) true user=> (distinct? 1 2 3 4 5) true user=> (distinct? 1 2 3 4 5 1) false user=> (apply distinct? '(1 2 3 4 5)) true user=> (apply distinct? [1 2 3 4 5 1]) false user=> (distinct '(1 2 3 4 5)) (1 2 3 4 5) user=> (distinct '(1 2 3 4 5 1 2 3)) (1 2 3 4 5) user=> (distinct [1 2 3 4 5 3 2 1]) (1 2 3 4 5) user=> (distinct [1 2 3 4 5 5 5 5]) (1 2 3 4 5)
それでは簡単な例題として、3 次元空間の異なる点 [x y z] を n 個作る関数を作ります。要素 x, y, z は 0 から 99 までの整数値とし、乱数で生成することにします。ここでコンピュータで扱う乱数について簡単に説明しておきましょう。
私たちが適当な数字を決める場合、たとえばサイコロを使えば、1 から 6 までの数字を簡単に決めることができます。サイコロを振って出た目を記録したら、次のようになったとしましょう。
5, 2, 1, 2, 6, 3, 4, 3, 1, 5, .....
サイコロの目は、イカサマをしないかぎり、出る確率が 1/6 で規則性はまったくありません。いま 2 が出たから次は 1 が出るとか、3, 4 と続いたから次は 5 が出るといったように、前に出た数字から次に出る数字を予測することはできないのです。このように、でたらめに並んだ数列を「乱数列 (random sequence)」といい、乱数列の中のひとつひとつつの数字を「乱数 (random numbers)」といいます。
コンピュータは、決められた手順 (プログラム) を高速に実行することは得意ですが、まったくでたらめな数を作れといわれると、とたんに困ってしまいます。そこで、何かしらの数式をプログラムして、それを実行することで乱数を発生させます。厳密にいえば乱数ではありませんが、それを乱数としてみなして使うことにするのです。このような乱数を「疑似乱数 (pseudo-random numbers)」といいます。現在では、ほとんどのコンピュータが疑似乱数を使っています。
Clojure には乱数を生成する関数 rand と rand-int が用意されています。
rand は 0 以上 n 未満の乱数を浮動小数点数 (Double) で返します。n のデフォルト値は 1 です。rand-int は 0 以上 n 未満の整数値 (Long) を返します。簡単な例を示しましょう。
user=> (dotimes [_ 10] (println (rand))) 0.6811675639454468 0.18540296388881838 0.8650502047810206 0.8588169722883902 0.09849136371175271 0.6379084710720743 0.8042971913084749 0.808706734448539 0.22518763556343524 0.6962755054741891 nil user=> (dotimes [_ 10] (println (rand-int 100))) 2 95 57 72 53 40 51 77 65 96 nil
生成する点の個数が少なければ、マップやセットを使わなくても、ベクタを線形探索するだけで十分です。プログラムは次のようになります。
リスト : n 個の異なる点を作る
;; 点 [x y z] を作る
(defn make-point []
[(rand-int 100) (rand-int 100) (rand-int 100)])
;; 異なる点を N 個作る
(defn make-data [n]
(loop [n n zs []]
(if (zero? n)
zs
(let [xs (make-point)]
(if (neg? (.indexOf zs xs))
(recur (dec n) (conj zs xs))
(recur n zs))))))
関数 make-data は関数 make-point で点をひとつ生成し、それが今まで生成した点と異なることを .indexOf でチェックします。.indexOf の比較関数は compare です。.indexOf は線形探索なので、点の個数が増えると時間がかかるようになります。実際に 5000, 10000, 20000 個の点を作ったときの実行時間を示します。
| 5000 | 10000 | 20000 | |
|---|---|---|---|
| 線形探索 | 0.60 | 1.70 | 6.16 |
点の個数が増えると実行時間が大幅に増加することがわかります。それでは線形探索の代わりにセットを使ってみましょう。プログラムは次のようになります。
リスト : n 個の異なる点を作る (セット)
;; 異なる点を N 個作る
(defn make-data-fast [n]
(loop [n n zs (hash-set)]
(if (zero? n)
zs
(let [xs (make-point)]
(if (contains? zs xs)
(recur n zs)
(recur (dec n) (conj zs xs)))))))
(defn make-data-fast1 [n]
(loop [n n zs (sorted-set)]
(if (zero? n)
zs
(let [xs (make-point)]
(if (contains? zs xs)
(recur n zs)
(recur (dec n) (conj zs xs)))))))
関数 make-data-fast は生成したデータのチェックに Hash Set を使います。セットは累積変数 zs に用意します。そして、make-point でデータを生成したら、contains? で同一データがないかチェックします。contains? の返り値が偽ならば xs は新しいデータです。セット zs に xs を追加して loop / recur で繰り返します。make-data-fast1 は Hash Set のかわりに Sorted Set を使用したものです。
これでプログラムは完成です。実行時間は次のようになりました。
| 5000 | 10000 | 20000 | |
|---|---|---|---|
| 線形探索 | 0.60 | 1.70 | 6.16 |
| Hash Set | 0.008 | 0.016 | 0.023 |
| Sorted Set | 0.012 | 0.041 | 0.046 |
線形探索と比べて圧倒的にセットの方が速いですね。Hash Set と Sorted Set では、ハッシュ法を使った Hash Set の方が少し速いようです。興味のある方はいろいろ試してみてください。