11

Judy 配列は、スパース配列または値のセットを表す高速なデータ構造です。C# などのマネージ言語の実装はありますか? ありがとう

4

3 に答える 3

16

グーグルで調べている場合、これらはJudy TreesまたはJudy Triesと呼ばれることが多いことに注意してください。

.Net 実装も探しましたが、何も見つかりませんでした。また、次の点にも注意してください。

このような実装の詳細は、サブ構造内で使用される特定の構造のサイズに大きく依存する可能性があるため、実装は効率的なキャッシュの使用を中心に大きく設計されています。.Net マネージ実装は、この点で多少異なる場合があります。

私が見ることができるいくつかの重要なハードルがあります（そして、私の簡単なスキャンが見逃したものはおそらくもっとあります）

  • API にはかなりアンチ OO の側面があり (たとえば、ヌル ポインターは空のツリーとして表示される)、単純化されているため、状態ポインターを LHS に移動し、関数のインスタンス メソッドを C++ に変換することはできません。
  • 私が調べたサブ構造の実装では、ポインターが多用されていました。これらがマネージ言語の参照に効率的に翻訳されているのがわかりません。
  • 実装は、パブリック API の単純さに反する多くの非常に複雑なアイデアの蒸留です。
  • コード ベースは約 20,000 行 (ほとんどが複雑) で、簡単に移植できるとは思えません。

ライブラリを使用して、C コードを C++/CLI でラップすることもできます (おそらく、c API トライであるポインターを内部的に保持し、すべての c 呼び出しがこれを指すようにするだけです)。これにより単純化された実装が提供されますが、ネイティブ実装のリンクされたライブラリが問題になる可能性があります (メモリ割り当てなど)。また、移行時に .Net 文字列を単純な古いバイト * に変換する必要がある場合もあります (または、バイトを直接操作するだけです)。

于 2009-02-16T15:12:05.730 に答える
12

Judy は、マネージ言語にはあまり適していません。SWIG のようなものを使用して、最初のレイヤーを自動的に完成させることはできないと思います。

私は PyJudy を書きましたが、結局、Python にうまく適合させるために重要な API の変更をいくつか行う必要がありました。たとえば、ドキュメントに次のように書いています。

JudyL 配列は、機械語を機械語にマップします。実際には、単語は符号なし整数またはポインターを格納します。PyJudy は、4 つのマッピングすべてを別個のクラスとしてサポートします。

  • pyjudy.JudyLIntInt - 符号なし整数キーを符号なし整数値にマップする
  • pyjudy.JudyLIntObj - 符号なし整数キーを Python オブジェクト値にマップする
  • pyjudy.JudyLObjInt - Python オブジェクト キーを符号なし整数値にマップする
  • pyjudy.JudyLObjObj - Python オブジェクト キーを Python オブジェクト値にマップする

私は数年間コードを見ていないので、それについての私の記憶はかなり曖昧です. これは私にとって初めての Python 拡張ライブラリであり、コード生成用の一種のテンプレート システムをハッキングしたことを覚えています。最近はげんしのようなものを使います。

Judy に代わるものを指摘することはできません。これが、私が Stackoverflow を検索している理由の 1 つです。

編集: Judy は 64 ビット キャッシュ ライン用に開発されており、私の PowerBook は 32 ビットのみだったため、ドキュメントに記載されているタイミングの数値は、Judy のドキュメントが示唆するものとはずれていると言われました。

その他のリンク:

最後には、さまざまな高性能トライ実装の比較数値があります。

于 2009-02-18T18:37:11.430 に答える
2

これは私が思っていたよりもトリッキーであることが証明されています。Tie::Judyと同様に、 PyJudyは一見の価値があるかもしれません。Softpediaには何かがあり、Rubyっぽいものもあります。問題は、これらのいずれも .NET に特化していないことです。

于 2009-02-15T07:23:01.980 に答える