

連想配列のようですが  
連想配列なら`map`やすでにSTLで用意されているで十分に足りると思うのですが  
なぜ、Judy arrayというものが生まれたのですか  
`map`や`set`と比べてそちらで用意されているものは何が大きく違うのですか？


CC BY-SA 3.0
2015-02-21T17:01:10.643
6877
2015-02-22T07:33:07.973
2015-02-22T07:33:07.973
7978
question
c++ アルゴリズム データ構造
Judy arrayとは何ですか？


簡単に言えば、「CPUのキャッシュ効率を重視した木構造」です。

質問は、機能としてのレイヤと実装としてのレイヤが混ざっているようなので、分けて説明します。

**機能レイヤ**

キーを与えられて、それに関連付けられた値を取り出せるデータ構造は一般的にマップと呼びます。マップには様々な実装があり得ます。単に機能としての「マップ」の話をしている場合は、操作(値の検索、挿入、削除等)の処理時間やメモリ効率のことはあまり考えません。言語やライブラリによっては、マップのことを(実装に関わらず)「配列」と呼んでいる場合もあります。

機能としての意味では、実装がリストだろうが配列だろうが木だろうが、マップとして使うことができるので、「十分に足りる」と言えます。しかし例えば100万要素のマップがO(n)では実用に難があります。そのため具体的なデータ構造として色々なものが考えられています。

C++の`std::map`は具体的な実装が規定されていないので、その意味ではこのレイヤでの「マップ」です。但し計算量についての制限があるので、現実的には木やハッシュテーブルで実装されていることが多いでしょう。

**実装レイヤ:配列**

実装としての配列は、キーを整数みなせる場合に、値をただべたっと並べておいてキーを直接インデックスとして使うデータ構造です。

取り得るキーの範囲があらかじめある程度限られていて、キーの分布が十分に密である場合には、速度もメモリ効率もベストです。

しかしその条件が満たされない場合、例えばキーは0から2^32までのどれかだけど実際に使われているのはそのうち1000個のみ、なんてことになると、配列は膨大なメモリを無駄にすることになります。

一般にリストはこの意味での「配列」ではありません。「連想配列」と言う場合も、実装がべたな配列になっていることは少ないので、機能レイヤでの話と考えた方が良いでしょう。機能レイヤで「配列」という用語を使っている場合、実装レイヤでの配列を「ベクタ」と呼んで区別することもあります。

**実装レイヤ:木**

キーの分布が疎であったり、キーの範囲が限定されていない場合によく使われるのが木構造です。基本的に参照O(log
n)なデータ構造になりますが、さらに細かい性能向上のために色々なバリエーションがあります。

  * バランス: 木の平均的な深さはO(log n)となりますが、データに偏りがあって全てのノードが一本の枝に集中すると深さO(n)になってしまいます。そうならないようにバランスを取る仕組みがアルゴリズムに組み込まれていますが、そこに様々な違いがあります。
  * アリティ: ノードから何本枝が出ているか。一番簡単な二分木では、葉以外のノードは最大2つの子を持ちます。アルゴリズムは単純ですが、要素が増えるとノードの総数も増えてしまい、その分メモリのあちこちを触らないとならないので空間効率も時間効率も悪くなります。逆にノードにたくさんの枝を生やせるようにして、ディスクの1ブロックを丸々一つのノードとして使えるようにしたものは、ディスクに大量のデータを格納するのに相性が良いです。データが疎だと空間効率が悪くなりがちです。

Judy arrayでは、ノードの構造を適応的に変えることで、データが密でも疎でもなるべくCPUのキャッシュを有効活用できるように工夫したものです。

質問にある`map`がC++の`std::map`のことであるなら、`std::map`の実装にJudy
arrayを使う、ということももちろん可能です。名前に"array"がついているのが紛らわしいですが、この"array"は機能レイヤの意味であって、実装レイヤの意味の配列ではありません。


CC BY-SA 3.0
2015-02-21T22:52:53.690
6893
2015-02-21T22:52:53.690
5258
6877
answer