18

問題仕様:

私は現在、非常に一般的であると思われる問題に対するエレガントで効率的な解決策を探しています。次の状況を考慮してください。

次のように (単純化された方法で) 定義されたBTreeに基づいてファイル形式を定義しました。

data FileTree = FileNode [Key] [FileOffset]
              | FileLeaf [Key] [Data]

これをファイルから遅延データ構造に読み書きする機能が実装されており、問題なく動作します。これにより、次のインスタンスが生成されます。

data MemTree = MemNode [Key] [MemTree]
             | MemLeaf [Key] [Data]

ここでの目標は、updateFile :: FilePath -> (MemTree -> MemTree) -> IO ()を読み取っFileTreeて MemTree に変換し、MemTree -> MemTree関数を適用して、変更をツリー構造に書き戻す汎用関数を作成することです。問題は、FileOffsets を何らかの方法で保存する必要があることです。

この問題には 2 つのアプローチがあります。どちらも優雅さや効率性に欠けています。

アプローチ 1: MemTree を拡張してオフセットを含める

このアプローチは、オフセットを含むように MemTree を拡張します。

data MemTree = MemNode [Key] [(MemTree, Maybe FileOffset)]
             | MemNode [Key] [Data]

read 関数は を読み込み、参照とともにFileTreeを保存します。書き込みは、参照に関連付けられたオフセットが既にあるかどうかをチェックし、関連付けられている場合はそれを使用するだけです。FileOffsetMemTree

長所：実装が簡単で、オフセットを見つけるためのオーバーヘッドがありません

短所：オフセットを設定する責任があるユーザーに内部を公開しますNothing

アプローチ 2: 二次構造にオフセットを格納する

この問題に対処する別の方法は、 を読み込み、を保持する をFileTree作成することです。そうすれば（およびのセマンティクスを正しく理解していれば）、最終的なものを取得して、の各ノードを検索できるはずです。エントリがある場合、ノードはクリーンであり、再度書き込む必要はありません。StableName.MapFileOffsetsStableNameMemTreeStableNameStableName.Map

長所：内部をユーザーに公開しません

短所: マップ内のルックアップにオーバーヘッドがかかる

結論

これらは私が考えることができる2つのアプローチです。前者の方が効率的で、後者の方が見栄えがします。私のアイデアについてコメントをお願いします。おそらく誰かがより良いアプローチを念頭に置いていますか?

[編集] 合理的

このようなソリューションを探している理由は 2 つあります。

一方では、型システムを使用して、エラーが発生する前にエラーを処理する必要があります。前述のユーザーはもちろん、システムの次の層の設計者 (つまり、私) です。純粋なツリー表現に取り組むことで、ある種のバグが発生しなくなります。ファイル内のツリーに対するすべての変更は、1 つの場所にある必要があります。これにより、推論が容易になるはずです。

一方、次のようなものを実装するだけinsert :: FilePath -> Key -> Value -> IO ()で完了できます。しかし、その後、ツリーを適切な場所に更新して (一種の) ログを保持すると、無料になる非常に優れた特性が失われます。トランザクション (つまり、いくつかの挿入のマージ) は、メモリ内の同じツリーで作業し、違いだけをファイルに書き戻すだけの問題です。

4

2 に答える 2

2

パッケージData.Generic.Diffはまさにあなたが望んでいたことをするかもしれないと思います。それがどのように機能するかについてのアイデアについて、誰かの論文を参照しています。

于 2015-12-26T04:18:34.487 に答える
1

私は Haskell で非常に新しいので、コードを表示しませんが、私の説明が解決策に役立つことを願っています.

まず、MemTree だけをユーザーに公開しないのはなぜですか。これはユーザーが更新するものであり、FileTree は完全に非表示のままにしておくことができるからです。そうすれば、後でこれをデータベースに移動するように変更したい場合、ユーザーは違いを認識しません。

したがって、FileTree は非表示になっているため、更新するときにそれを読み込むだけでなく、オフセットがあるので、更新を行い、ファイルを再度閉じます。

オフセットを保持することの1つの問題は、別のプログラムがファイルに変更を加えることを妨げることです。あなたの場合はそれで問題ないかもしれませんが、一般的なルールとしてそれは悪い設計だと思います.

私が見た主な変更点は、ファイルが開いたままにならないため、MemTree が遅延してはならないことです。

于 2012-10-15T10:39:45.160 に答える