1

まず、この質問は、Pythonについて尋ねられた質問者の辞書で値のキーを取得するための最も効率的な方法の複製ではありません。問題。

それで、私が次のデータ構造に従っていると仮定しましょう：

{ 
   "one" : "1",
   "two" : "2",
   .
   .
   "hundred thousand" : "100000"
}

ここで、特定の値に対してキーを取得できるようにします（異なるキーに対して同じ値を持たないことを前提としています）。1つの解決策は、データを反復処理してキーを取得することですが、データを次のように構造化すると、コードがどれほど効率的になるかを示します。

 data = [
    { 
       "one" : "1",
       "two" : "2",
       .
       .
       "hundred thousand" : "100000"
    },
    { 
       "1" : "one",
       "2" : "two",
       .
       .
       "100000" : "hundred thousand"
    }
   ]

したがって、nowdata[0]."two"を使用して2の値を取得できます。しかし、999という値を知っていて、そのキーを知りたいので、そのキーを取得するシナリオがあるとします。data[1]."999"つまり、data[1]で逆データを使用します。

このソリューションは、データを反復処理して適切なキーを見つけるよりもおそらく高速です。どう思いますか？

4

2 に答える 2

2

すべてのキーを反復処理するのは非効率的であることは間違いありません。また、逆引き参照ハッシュを維持するために提案する方法は、この問題を解決するために私が見た中で最も一般的な方法です。もちろん、最善の解決策は、逆引きを実行する必要のない設計にすることです。

少数のキーを保存していて、このルックアップを頻繁に実行しない場合は、おそらく O(n) コストで問題ありません (もちろん、その場合、逆ルックアップ ハッシュを維持してもそれほど問題はありません)。 . 反対に、何百万ものキーがあり、逆ルックアップ ハッシュによるメモリ ヒットを許容できない場合は、ブルーム フィルターなどを使用してルックアップのコストを削減できます。

于 2012-07-09T12:45:38.097 に答える
0

複数のキーが同じ値を持つ可能性があるため、問題に対する一般的な解決策はありません。特定の例では、速度の観点から効率について話している場合、はい、逆マップを使用する現在のソリューションが最速の方法です(逆マップを保存するための追加スペースを犠牲にして)。

于 2012-07-09T12:44:16.253 に答える