質問: リテラル表記でのarray-mapとarray-map関数との違い

[minoru chikamune]

ちかむね といいます。

少し前から疑問に思っていたarray-mapの挙動について質問させてください。

以下はREPLでの操作例です。

user> {:a 1 :b 2 :c 3}

{:a 1, :c 3, :b 2}

user> (array-map :a 1 :b 2 :c 3)

{:a 1, :b 2, :c 3}

user> (type {:a 1 :b 2 :c 3})

clojure.lang.PersistentArrayMap

user> (type (array-map :a 1 :b 2 :c 3))

clojure.lang.PersistentArrayMap

最初のリテラル表記でのarray-mapは、順不同で表示されます。

最後に追加した要素である :c が真ん中に来ています。

リテラル表記のmapはPersistentArrayMapであることは、type関数で

表示されている通りです。ですが、array-map関数で作ると、

今度は引数の順序が守られます。

もともと、array-mapは投入したデータの順番が守られると思っていたので、

どうしてリテラル表記のmapがこのようになっているのか、疑問に思っていました。

特にとっても困っているわけではないのですが、ログ出力した際などに

順不同になっていると見づらいため、リテラル表記を避けております。

何かご存じの方がいらっしゃったら、コメント頂けると嬉しいです。

[Masakazu Takahashi]

2013/4/23 minoru chikamune <minor...@gmail.com>:
> もともと、array-mapは投入したデータの順番が守られると思っていたので、
> どうしてリテラル表記のmapがこのようになっているのか、疑問に思っていました。

面白いですね。少しバリエーションを試してみました。

user=> (clojure-version)
"1.5.1"
user=> {:a 1 :b 2 :c 3}

{:a 1, :c 3, :b 2}

read 系で読み込んだときは、順序が保たれるように見えます。

user=> (read-string "{:a 1 :b 2 :c 3}")

{:a 1, :b 2, :c 3}

また、定数だけじゃなく式が入っていると順序が保たれるように見えます。

user=> {:a 1 :b (+ 1 1) :c 3}

{:a 1, :b 2, :c 3}

Clojure のソースを追いかけきれていませんが、コード中に定数だけの map リ
テラルがあると、コンパイル時に特別扱いして内部的に PersitentHashMap を
持つような気がします。

確かなことがわかる方、補足をお願いします。

[jou4]

かみつかさと申します。

私も以前から気になっていたのでこの機会に調べてみました。

なぜそうなっているのかはわからなかったのですが

確かに Compiler.java の MapExpr.parse において

{:a 1 :b 2 :c 3} のような全てのkeyとvalueが定数のMapは

PersistentHashMapに詰めかえられていました。

他の例についても少し追ってみましたので書いてみます。誤りはご指摘ください。

まずClojureのコンパイラはざっくりと次のような順序で処理します。

1. read

  文字列を読み込んで form と呼ばれる Object を返します。

  例えば "abc" は String、(:a :b) は ISeq に変換されます。

2. analyze

  form Object を Expr へ変換します。

  例えば (println 123) というISeqのformは InvokeExprに変換されます。

  マクロ展開もここで実施されます。

3. eval

  Expr を評価して値を得ます。

それぞれの例がどのように変化するかですが…

user=> {:a 1 :b 2 :c 3} の場合

1. read

    PersistentArrayMapに変換。

2. analyze

    key, val全てが定数のMapの場合 PersistentHashMap に詰めなおされた後にConstantExprに包まれる。

    ここで順序が崩れる。

3. eval

    再度PersistentArrayMapに詰められる。

user=> (array-map :a 1 :b 2 :c 3) の場合

1. read

    ISeq に変換。

2. analyze

    InvokeExpr に変換。

3. eval

    array-map に引数(:a 1 :b 2 :c 3)が適用されて PersistentArrayMap が得られる。

user=> (read-string "{:a 1 :b 2 :c 3}")

1. read

    ISeq に変換。

2. analyze

    InvokeExpr に変換。

3. eval

    read-stringに引数("{:a 1 :b 2 :c 3}")が適用される。

    ただしread-stringにおいては read が呼ばれるのみ。そのため PersistentArrayMap が返却されて終了。

リテラル表記とそれ以外のケースではanalyzeに渡されるformに差があり

IPersistentMapのanalyzeにおいては全key/valが定数のMapが特別扱いされて

PersistentHashMapに詰め直され、その結果、順序が崩れてしまうようです。

[minoru chikamune]

質問者のちかむねです。

emasakaさん、かみつかささん、どうもありがとうございました！

「式が入っていると順序が保たれる」なんて、まったく気が付きませんでした。

かみつかささんが示された、Compiler.javaの2838行付近の以下の場所ですが、

確かにそうなってますね。面白いです。これがPersistentArrayMap.EMPTYだったら

順番が守られていたんですね。

else if(constant) {

IPersistentMap m = PersistentHashMap.EMPTY;

仕様なのか否かなどは分からないですが、理解できて個人的にはすっきりしました。

ありがとうございました！

[Yoshinori Kohyama]

以下実行例は Clojure 1.5.1 のものです.

マップには三種類あります.

  (class (sorted-map 1 1 2 2 3 3)) ; -> clojure.lang.PersistentTreeMap

  (class (hash-map 1 1 2 2 3 3)) ; -> clojure.lang.PersistentHashMap

  (class (array-map 1 1 2 2 3 3)) ; -> clojure.lang.PersistentArrayMap

sorted-map (PersistentTreeMap) はキーの昇順 (compare で比較した時の意味で) が保たれます.

hash-map (PersistentHashMap) は順序の保証はありません.

array-map (PersistentArrayMap) はキーを追加した順序が保たれます.

明確にどれかを使いたい場合は, リテラル {} ではなく, 上記三つの生成関数を使います.

リテラルで書いた場合は, 順序についての保証がありませんが,

(おそらく実行効率上の理由で)キーが 8個までは array-map, キー 9個以上は hash-map が使われます.

  (class {1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8}) ; -> clojure.lang.PersistentArrayMap

  (class {1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9}) ; -> clojure.lang.PersistentHashMap

array-map に assoc で要素を追加してキーが 9個以上になっても array-map のままです.

  (class (assoc {1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8} 9 9)) ; -> clojure.lang.PersistentArrayMap

into を使うと新たに hash-map が生成されるようです.

  (class (into {1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8} '([9 9]))) ; -> clojure.lang.PersistentHashMap

今後この実装は変わるかもしれませんので, これらの動作には依存しない方がよいでしょう.

光山

[minoru chikamune]

光山さん

質問者のちかむねです。

ゴールデンウィークに入ってしまい、お返事が非常に遅くなってしまいました。すみません。

リテラルで書いた場合は、要素数によっても挙動が変化するのですね。

私はもともと、リテラル表記では何かの型に固定されるのだとばかり考えていましたが、

そこがそもそも間違いの元だったようですね。確かにパフォーマンスを考えると

要素数によって実装を変える事は納得がいきます。

ちょっと、Clojureのバグの疑いを持っていました。浅はかでした。