マネージ言語用の Judy 配列

StackOverflow https://stackoverflow.com/questions/550204

質問

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

役に立ちましたか？

解決

グーグルで検索すると、これらはしばしば Judy Trees または Judy Tries と呼ばれることに注意してください。

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

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

私が確認した限り、それにはいくつかの重要なハードルがあります (そして、おそらく私が簡単にスキャンしただけで見逃したハードルがさらにあるでしょう)

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

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

他のヒント

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

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

ジュディルアレイ機の単語をマシンワードにマップします。実際には、単語は署名されていない整数またはポインターを保存します。Pyjudyは、4つのマッピングすべてを異なるクラスとしてサポートしています。

  • pyjudy.judylintint -unsigned integerキーを符号なし整数値にマップ
  • pyjudy.judylintobj -pythonオブジェクト値への符号なし整数キーをマップ
  • pyjudy.judylobjint -map pythonオブジェクトキーは符号なし整数値へ
  • pyjudy.judylobjobj-マップPythonオブジェクトキーへのPythonオブジェクト値へ

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

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

編集：Judy は 64 ビット キャッシュ ライン用に開発されており、私の PowerBook は 32 ビットしかなかったので、ドキュメントにある私のタイミング数値は Judy のドキュメントが示唆するものと異なっていると言われました。

その他のリンク:

最後には、さまざまな高性能トライ実装の比較番号が含まれています。

これは思ったよりも難しいことがわかりました。 パイジュディ 一見の価値があるかもしれません。 ネクタイ::ジュディ. 。何か付いてるよ ソフトペディア, 、そして何か ルビーっぽい. 。問題は、これらはいずれも .NET 専用ではないことです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top