-6

以下のタプルを与える：

({15: None}, 
{7: None}, 
{2: None, 3: None, 4: None, 7: None, 13: None, 15: None}, 
{13: None}, 
{4: None}, 
{7: None}, 
{15: None}, 
{15: None, 4: None, 13: None, 7: None}, 
{15: None, 4: None, 7: None}, 
{7: None}, 
{4: None}, 
{4: None}, 
{4: None, 7: None}, 
{4: None})

アルゴリズム：

for tail in xrange(len(tupe_above), -1, -1):
   for _ in tuple_above[tail].iteritems():
      for head in xrange(0, tail):         
         if _[0] in head:
            print 'got one ...'

質問：

私の心に強い気持ちがあり、線形時間でこの作業を行う方法が存在するに違いありません（上位層の辞書を使用すると仮定します）、誰かが私に提案を与えることができますか？ありがとう。

4

2 に答える 2

1

あなたの質問を理解するために最善を尽くします。このタプルからdict特定のキー ( など) を含むすべての を見つけようとしていますか?18

私が考える解決策は、最もPythonicであり、この特定のレベルのネストに対して線形時間である必要があります。

def getDictsWithKey(dictTuple, key):
    return [d for d in dictTuple if key in d]
于 2013-09-16T01:55:31.917 に答える
1

あなたの「仕事の説明」を理解しているかどうかわかりませんが、あなたはこれを望んでいると思います：

def find_matches(tuple_of_dicts, key_to_find):
    return [d for d in tuple_of_dicts if key_to_find in d]

そう：

>>> tuple_of_dicts = ({18: None}, {10: None}, {16: None, 18: None, 5: None, 6: None, 7: None, 10: None}, {16: None}, {7: None}, {10: None}, {18: None}, {16: None, 10: None, 18: None, 7: None}, {10: None, 18: None, 7: None}, {10: None}, {7: None}, {7: None}, {10: None, 7: None}, {7: None})
>>> find_matches(tuple_of_dicts, 18)
[{18: None},
 {5: None, 6: None, 7: None, 10: None, 16: None, 18: None},
 {18: None},
 {7: None, 10: None, 16: None, 18: None},
 {7: None, 10: None, 18: None}]

それは線形時間で機能します。タプルに N 個のディクテーションがあり、それぞれ平均して M メンバーである場合、タプルをたどって、反復ごとに一定時間のディクテーション ルックアップを実行し、合計 O(N) になります。

しかし、このような検索を多数行う場合は、線形時間よりもさらに優れた結果を得ることができます。

秘訣は (ご想像のとおり) インデックス ディクショナリを作成し、各キーをそれが含まれるディクショナリのインデックス、または単にディクショナリ自体にマッピングすることです。例えば：

>>> dict_of_dicts = {}
>>> for d in tuple_of_dicts:
...     for key in d:
...         dict_of_dicts.setdefault(key, []).append(d)
>>> def find_matches(dict_of_dicts, key_to_find):
...     return dict_of_dicts[key_to_find]

これには、セットアップ作業を行うのに O(N*M) の時間が必要であり、O(N*M) スペースの辞書を作成します*。ただし、検索ごとに単純な O(1) 辞書検索になります。したがって、M 回以上の検索を行っていて、余分なスペースを確保できる限り、それは大きな利益になります。

* 正確に言うと、L 個の個別のキー、合計 M 個のキーがある場合、dict で N*M 回のルックアップを行い、dict に N*M/L 回追加し、M/L の長さのリストに N*M 回追加します。 . リストの追加は一定時間償却されるため、O(N*M + N*M/L + N*M) = O(N*M) セットアップ時間です。一方、dict は O(N*L) スペースであり、各メンバーは長さ O(M/L) のリストであるため、リストに使用される合計スペースは O(N*L * M/L) = O( N*M) であり、dict とそのリストの合計スペースは O(N*L + N*M) = O(N*M) です。最後に、検索は値をハッシュし、それを dict で検索し、M/L 長リストへの参照を返します。これらはすべて一定時間の操作であるため、各検索は O(1) です。

于 2013-09-16T01:55:49.683 に答える