10


7

http://ja.wikipedia.org/wiki/Judy_array[Judy array]は、疎な配列または一連の値を表す高速データ構造です。 C#などの管理言語用の実装はありますか? ありがとう

3 回答


15


あなたがそれらのためにグーグルしているならば、これらがしばしばジュディツリーまたはジュディトライと呼ばれることは注目に値します。

私はまた、.NETの実装を探しましたが、何も見つかりませんでした。 また注目に値する。

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

私が見ることができるそれにはいくつかの重要なハードルがあります(そして私の簡単なスキャンが逃したより多くのおそらくあります)

  • APIにはかなり反オブジェクト指向の側面がいくつかあります(たとえば、nullポインタは空のツリーとして表示されます)ので、状態ポインタをLHSに移動し、関数インスタンスメソッドをCに変換しても機能しません。

  • 私が見た部分構造の実装はポインタを多用しました。 これらが管理言語の参照に効率的に翻訳されているとは思えません。

  • 実装は、パブリックAPIの単純さを裏付ける、非常に複雑なアイデアをたくさん集めたものです。

  • コードベースは約20K行(ほとんどが複雑)ですが、これは私にとっては簡単な移植ではありません。

ライブラリを使用してCコードをC / CLIでラップすることができます(おそらく、単にc api trieであるポインターを内部的に保持し、すべてのc呼び出しがこれを指すようにする)。 これは単純化された実装を提供しますが、ネイティブ実装のためのリンクライブラリは問題があるかもしれません(メモリ割り当てかもしれないように)。 また、移行時にも.NET文字列を通常の古いバイト*に変換する必要があるでしょう(または単にバイトを直接処理する)。


12


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

私はPyJudyを書きました、そして私はPythonにうまく合うためにいくつかの自明でないAPI変更をしなければならなくなりました。 例えば、私はドキュメンテーションに書きました:

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

  • pyjudy.JudyLIntInt-符号なし整数キーを符号なし整数にマップする 値

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

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

  • pyjudy.JudyLObjObj - PythonオブジェクトキーをPythonオブジェクト値にマッピングする

私は数年間コードを見ていないので、それについての私の記憶はかなり漠然としています。 それは私の最初のPython拡張ライブラリでした、そして私はコード生成のための一種のテンプレートシステムを一緒にハックしたのを覚えています。 今日はげんしのようなものを使います。

私はJudyに代わるものを指すことはできません - それが私がStackoverflowを探している理由の一つです。

編集:Judyは64ビットキャッシュライン用に開発されたもので、PowerBookは32ビットしかなかったので、私のマニュアルのタイミング番号はJudyの文書が示唆しているものからずれていると言われました。

その他のリンク

  • パトリシアの試み (http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/)

  • Double-Arrayの試行(http://linux.thai.net/~thep/datrie/datrie.html)

  • HATトライ(http://members.optusnet.com.au/~askitisn / index.html)

最後は、さまざまな高性能トライ実装の比較番号です。


2


これは私が思っていたよりも難しいことを証明している。 PyJudyは一見の価値があるかもしれません。 Judy.pm [ネクタイ

Judy]。 Softpedia上に何か、そしてhttp://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/上に何かがあります。 ruby / ruby​​-talk / 48365 [Rubyっぽい]。 問題は、これらのどれも特に.NETではないということです。