実際には 'TreeDict'（またはTreemap）を使用することはできますか？

Question

私はPythonで 'TreeDict'クラスを開発しています。基本的には、JavaのTreemapコレクションクラスのように、キーと値のペアをソート順に取り出すことができる辞書です。

リレーショナルデータベースの一意のインデックスを使用する方法に基づいて、いくつかの機能を実装しました。ソートされた順番で特定の値以上のキー、特定の値以下のキー、ソートされた順序で特定の接頭辞を持つ文字列またはタプルなどに対応する値を取得できるようにする関数。

残念ながら、このようなクラスを必要とする実際の生活の問題を考えることはできません。私は、Pythonで辞書をソートしていない理由は、実際には価値があるほど頻繁に必要とされるわけではないが、私は間違っていると証明したいと思う。

「TreeDict」の特定のアプリケーションについて考えることはできますか？このデータ構造によって最もよく解決される実際の生活の問題はどれですか？私はちょうどこれがそれに値するかどうかを確かめたいと思う。ソートなど バルブのオープン/クローズ、機械のスタート/ストップdata--工業プロセス、キーを備え

で作業するとき

Answer 1

これは、キーの順に辞書を通過する必要がある場合に便利です。これは機会に現れます。私は実際に特定のプログラミングコンテストで無限により一般的なものを見つけました（ACMなど）。

TreeMapの最も有用な機能は、最小または最大のキーを素早く探したいときです。ソートされた辞書を使用すると、これはしばしば単一のメソッド呼び出しです。コレクションがソートされていない場合は、各キーを反復してmin/maxを検索するのではなく、アルゴリズム的にO（log（n））時間で行うことができます。基本的には、もっと親しみやすいインターフェースです。

私が実行するのは、オブジェクトが特定の名前で識別され、その名前に従って注文されたオブジェクトをプリントアウトしたいときです。ディレクトリ名からディレクトリ内のファイル数へのマッピングを言う。

私が使っている他の場所は、Excelスプレッドシートのラッパーです。行番号から行オブジェクトへのマッピング。これにより、各行をループすることなく、最後の行インデックスをすばやく見つけることができます。

また、HashMapsの必要に応じて、キーで比較関係を簡単に定義できますが、必ずしもハッシュ関数である必要はありません。私が考えることができる最良の（しかし弱い）例は、大文字と小文字を区別しない文字列キーです。

Answer 2

は、私は頻繁に私が開始の間の時間間隔を比較する必要がある場合に特に便利ですDict<DateTime, someClassOrValue>を使用/停止または開/閉のイベントを発生させることができます。

しかし、私はlinqをC＃で使うことができたので、IEnumerablesを使って作業し、IQueryable拡張メソッドを使用して必要な情報を取得するほうが簡単だと分かりました。

Answer 3

要素をソート順に保持する理由は、検索を高速化するためです。辞書内のすべての値をソートされた範囲に入れたいとします。これは、TreeDictと通常のハッシュマップの方がはるかに高速です。基本的には、辞書のすべてをソート順に並べることができます。私は現在、基本的にデータ構造を照会するためにこのようなクラスを使用しているアプリケーションで知っています。

Answer 4

さまざまなアルゴリズムを実装しやすくすることができます。

Answer 5

ほとんどすべての "GROUP BY"レポートにはソートされた辞書が必要です。

これは、データウェアハウジングアプリケーションで頻繁に行われるため、これがどの程度重要であるかを表現するのは難しいです。

sorted関数呼び出しが機能しない場合、長い時間が節約されます。

Answer 6

私は「順序付けられたシーケンスで歩く」機能を指していますが、これは本当に重要ですが、他の大きな機能を強調するものはありません。実際にそこから歩く必要がない場合でも、多くの用途があります。

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5} 

： - たとえば

は（これはSO答える最近で思い付いた）、あなたが与えられた相対的な周波数の擬似ランダム値を生成したいと言うつまり、あなたは、たとえば、辞書dを与えられています

そして、100のうち42の確率で（100は相対的な頻度の合計であるため）、 'sheep' 100のうち15など、 'wolf'を生成する方法が必要です。相対的な頻度がそうであるように、明確な値の数はかなり大きくなる可能性があります。

次に、与えられた値を（すべての順序で）ツリーマップの値として保存します。対応するキーはその時点までの「合計累積頻度」です。すなわち：firstGTKeyが.keyと.value属性を持つ最初のエントリを（返すメソッドである

def generate(tot, treemap, r=random): 
    n = r.randrange(tot) 
    return treemap.firstGTkey(n).value 

には、次のように今

def preprocess(d): 
    tot = 0 
    for v in d: 
     tot += d[v] 
     treemap.insert(key=tot, value=v) 
    return tot, treemap 

は、値を生成すること、（O(log(len(d)))）かなり速いことができますこの仮説的な例）を指定します。私は、例えば、Bツリーとして保存された大きなファイル（例えば、bsddb.bt_openとset_locationメソッドを使用して）でこの方法を使用しました。

Answer 7

あなたはそれを見たことがありますか：http://code.activestate.com/recipes/576998/？

zuo