7

関数型辞書を C で実装しようとしています。関数型リストまたは B ツリーを実装するのはかなり簡単ですが、辞書/連想配列に関する参照がほとんど見つかりません。

私は erlang の dict 実装を見てみました - ソースコードで彼らはこの論文を参照しています:
The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon .

誰かが erlang のアプローチやこの問題に対する別の解決策を簡単に説明できれば素晴らしいことです。

4

1 に答える 1

6

C での永続的なデータ構造の実装は、関数型言語での実装と基本的に同じように機能します。Chris Okasaki のPurely Functional Data Structuresは参考になります。

一般に、固定幅の整数をオブジェクトにマップするだけで十分です。これだけでは完全な辞書は得られませんが、その上に辞書を作成できます。実際のキーのハッシュをオブジェクトのキーとして使用します。基になるマップを作成し、葉が同じハッシュ値の (キー、値) ペアのリストを指すようにします。

注意が必要なのがメモリ管理です。通常、データ構造の一部がいつアクセス不能になるかはわかりません。幸いなことに、ほとんどの永続データ構造はツリーに基づいているため、通常は参照カウントがうまく機能します。データ構造によって参照されるオブジェクトを管理できるようにするために、リーフ ノードの参照カウントが 0 になったときに呼び出されるコールバックのフックを提供できます。

たとえば、ビットマップ化されたパトリシア ツリーの C 実装は、次の API を提供します。

// Querying
void *bpt_get(bpt_t bpt, bpt_key_t key);
bool bpt_has_key(bpt_t bpt, bpt_key_t key);

// Adding and Removing Entries
bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);

// Managing Memory
void bpt_retain(bpt_t bpt);
void bpt_release(bpt_t bpt);
void bpt_dealloc(bpt_t bpt);
void bpt_set_dealloc_hook(bpt_t bpt,
                          bpt_key_t key,
                          void (*hook)(bpt_key_t key,
                                       void* value));

// Iteration
void bpt_for_mappings(bpt_t bpt,
                      void (*thunk)(bpt_key_t, void*, void*),
                      void *user_data);

// Making a Map Persistent (you can elide this if you don't
// want to support transients)
void bpt_seal(bpt_t bpt);

実装によって、いくつかのアイデアも得られるかもしれません。

于 2012-04-22T11:39:11.373 に答える