2

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

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

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

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

4

7 に答える 7

5

確かに重要な「順序付けられた順序で歩く」機能を指すいくつかの回答を見てきましたが、「キー>=thisで最初のエントリを見つける」という他の大きな機能を強調するものはありません。そこから「歩く」必要がない場合でも、これには多くの用途があります。

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

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

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

次に、指定された値を（任意の順序で）ツリーマップの値として保存します。対応するキーは、その時点までの「合計累積度数」です。すなわち：

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

ここで、は、キー>指定された引数を持つ最初のエントリ（この架空の例では、属性を含む）firstGTKeyを返すメソッドです。たとえば、Bツリーとして保存された大きなファイルでこのアプローチを使用しました（たとえば、メソッドを使用）。.key.valuebsddb.bt_openset_location

于 2009-06-19T00:38:22.863 に答える
2

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

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

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

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

また、キーの比較関係を簡単に定義できるが、HashMap で必要なハッシュ関数であるとは限らない場合にも役立ちます。私が考えることができる最良の (弱い) 例は、大文字と小文字を区別しない文字列キーです。

于 2009-06-18T19:04:30.053 に答える
2

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

于 2009-06-18T18:08:03.890 に答える
1

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

ズオ

于 2010-04-10T11:17:33.807 に答える
1

ほとんどすべての「GROUP BY」レポートには、ソートされたディクショナリが必要です。

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

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

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

于 2009-06-18T18:31:13.570 に答える
1

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

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

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

于 2009-06-18T18:06:45.560 に答える
0

それらは、さまざまなアルゴリズムの実装を容易にすることができます。

于 2009-06-18T18:08:11.533 に答える