「TreeDict」（またはツリーマップ）は実際に何に使用できますか？

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

質問

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

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

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

「TreeDict」の特定のアプリケーションについて考えてください。このデータ構造によって最もよく解決される現実の問題はありますか？これだけの価値があるかどうかを確認したいだけです。

役に立ちましたか？

解決

キーの順に辞書を調べる必要がある場合に便利です。時々出てきます。実際、特定のプログラミングコンテストでは他の何よりも無限に一般的です（ACMなどを考えてください）。

TreeMapの最も便利な機能は、最小または最大キーをすばやく見つけたい場合です。ソートされた辞書を使用すると、多くの場合、これは単一のメソッド呼び出しです。コレクションがソートされていない場合に最小/最大を探して各キーを反復処理するのではなく、O（log（n））時間でアルゴリズム的に実行できます。基本的に、はるかに使いやすいインターフェイスです。

私がよく目にするのは、特定の名前でオブジェクトが識別され、名前に従って順序付けられたオブジェクトを印刷したいときです。ディレクトリ名からディレクトリ内のファイル数へのマッピングを言います。

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

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

他のヒント

<！> quot;順番通りに歩く<！> quot;を指すいくつかの回答を見ました。確かに重要な機能ですが、他の大きな機能を強調するものはありません。それは、<！> quot;キーで最初のエントリを見つける<！> gt; = this <！> quot;です。 <！> quot; walk <！> quot;を実際に必要としない場合でも、これには多くの用途があります。そこから。

たとえば（これは最近のSOの回答で出てきました）、与えられた相対頻度で擬似乱数値を生成したいとします-つまり、たとえばdict d：

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

100のうち42の確率で「オオカミ」を生成する方法（100は与えられた相対頻度の合計であるため）、100から15の「羊」などを生成する方法が必要です。相対頻度と同様に、個別の値の数は非常に多くなる可能性があります。

次に、指定された値を（任意の順序で）値としてツリーマップに格納します。対応するキーは<！> quot; total累計frequency <！> quot;です。その時点まで。つまり：

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)))）になります：

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

where firstGTKeyは、キー<！> gtを持つ最初のエントリ（この仮想例では.keyおよび.value属性を含む）を返すメソッドです。指定された引数。たとえば、Bツリーとして保存された大きなファイルでこのアプローチを使用しました（例：bsddb.bt_openおよびset_locationメソッドを使用）。

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

工業プロセスのデータを扱う際によくDict<DateTime, someClassOrValue>を使用します- バルブの開閉、機械の起動/停止など。

キーをソートしておくと、適切な時間内の開始/停止または開閉イベント間の時間間隔を比較する必要がある場合に特に役立ちます。

ただし、C＃でlinqを使用できるようになったので、IEnumerablesを操作し、IQueryable拡張メソッドを使用して必要な情報を取得する方が簡単な場合が多いことがわかりました。

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

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

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

sorted関数呼び出しが機能しない場合、長い目で見れば時間を大幅に節約できます。

あなたはそれを見ましたか： http://code.activestate.com/recipes/576998/ ？

zuo

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

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