3

キーが非順次整数である辞書「vcomments」があります。キーをループするときは、ソート済みまたは逆ソートの順序でループする必要があります。現在使用しています

for key_pt in sorted(self.view.vcomments.iterkeys()):

しかし、特定の数を超えている、または前にあるキー（または次のキー）も見つける必要があります。

    if direction == 'down':
        sorted_pts = (key_pt for key_pt in sorted(self.view.vcomments.iterkeys()) if key_pt > curr_pt)
    else:
        sorted_pts = (key_pt for key_pt in reversed(sorted(self.view.vcomments.iterkeys())) if key_pt < curr_pt)
    try:
        next_pt = sorted_pts.next()
    except StopIteration:

  1. ディクショナリを格納し、順方向または逆方向のいずれかでループできるようにするイテレータクラスを（イテレータプロトコルを使用して）作成することは可能ですか？次のループを順方向/逆方向にするかどうかを示す属性値を最初に割り当てる必要があるかもしれないと想定/推測しています。

  2. 次のキーを取得できるようにするジェネレーター関数（ネストされた）をイテレータークラスに含めることはできますか？つまり、指定された整数を超えているか、またはその前ですか？

  3. 同様に、開始点と終了点を指定して、これらの値の間にあるすべてのキーを（ソートされた順序で）取得する方法はありますか？

私は3つの（関連はあるが）質問をしたことをお詫びします-最初の答えは私にスタートを与えるでしょう。そして、私は完全な解決策を期待するほど失礼ではありません。これらが私にとって実行可能な目標であるかどうかを示すだけです。

追加：そして、キーによって単一の特定の辞書アイテムを取得できる必要があります。

4

4 に答える 4

4

ここでのニーズに最適なデータ構造はスキップリストだと思います。私はこれを実装したことはありません-常にしたかった-しかし、これはあなたが必要とするすべてのものを持っているように私には見えます。

  1. スキップリストは、そのアイテムをソートされた順序で格納します。ベースリストを二重にリンクされたリストにすると、O（n）で順方向と逆方向の反復が可能になります。

  2. スキップリストでは、O（log n）の挿入、変更、削除、および検索が可能です。これは辞書ほど高速ではありませんが、並べ替えられた順序でアイテムを保存する必要がある場合、キーを追加することがめったにOrderedDictない場合を除いて、辞書で問題が発生するようです。

  3. 上記のウィキペディアの記事で説明されているいくつかの変更により、インデックス付きアクセスでさえO（log n）で実装できます。

ここにPythonの実装が1つあります-おそらく他の実装があります。

ただし、コメントの中には、ソートされた辞書のコピーを単純に反復処理するだけで満足している可能性があり、上記のコードをクリーンアップしようとしていることを示唆しているものもあります。それで、これはそれについて行く一つの方法です。これはかなり素朴ですが、出発点です。これは、O（n）の検索時間とO（n log n）の反復時間で完全に問題がないことを前提としていますが、どちらも最適ではありません...

>>> class SortIterDict(dict):
...     def __iter__(self):
...         return iter(sorted(super(SortIterDict, self).__iter__()))
...     def __reversed__(self):
...         return reversed(tuple(iter(self)))
...     def get_next(self, n):
...         return next((x for x in iter(self) if x > n), None)
...     def get_prev(self, n):
...         return next((x for x in reversed(self) if x < n), None)
... 
>>> d = SortIterDict({'d':6, 'a':5, 'c':2})
>>> list(d)
['a', 'c', 'd']
>>> list(reversed(d))
['d', 'c', 'a']
>>> d.get_next('b')
'c'
>>> d.get_prev('b')
'a'
于 2012-04-26T23:02:20.753 に答える
2

まず第一に、より良いデータ構造が必要であることに注意する必要があります。Python dictには順序がまったくなくOrderedDict、挿入順序が保持されるだけです（したがって、キーが変更されるたびに並べ替える必要があります）。のようなソートされた辞書、blist.sorteddictまたはのようなソートされたリストでさえ、blist.sortedlistおそらくあなたのニーズにはるかに適しています。

ディクショナリを格納し、順方向または逆方向のいずれかでループできるようにするイテレータクラスを（イテレータプロトコルを使用して）作成することは可能ですか？次のループを順方向/逆方向にするかどうかを示す属性値を最初に割り当てる必要があるかもしれないと想定/推測しています。

ここでは、個別のイテレータクラスは必要ありません。reversed組み込み関数を介して、無料の順方向反復と逆方向反復を取得します。

for key in mydict:
  # do something

for key in reversed(mydict.keys()):
  # do something

次のキーを取得できるようにするジェネレーター関数（ネストされた）をイテレータークラスに含めることはできますか？つまり、指定された整数を超えているか、またはその前ですか？

確かに、itertools次のようなことを可能にする多くの機能があります。

from itertools import dropwhile, takewhile
# find next key beyond 4
next(dropwhile(lambda x: x <= 4, mydict))
# find last key before 20
next(dropwhile(lambda x: x >= 20, reversed(mydict.keys()))

これを関数にパッケージ化することもできます。

def first_beyond(pivot, seq):
  next(dropwhile(lambda x: x <= pivot, seq))

first_beyond(4, mydict)
first_beyond(20, reversed(mydict.keys()))

同様に、開始点と終了点を指定して、これらの値の間にあるすべてのキーを（ソートされた順序で）取得する方法はありますか？

そのための一般的なツールを簡単に作成できます。

from itertools import dropwhile, takewhile
def between(begin, end, seq):
  return takewhile(lambda x: x <= end, 
                   dropwhile(lambda x: x < begin, seq))

このように使用するには：

>>> list(between(4, 30, [1,2,4,8,16,32]))
[4, 8, 16]

編集：時々ソートされたキーを調べる必要がある場合は、それらをソートされたリストに変換して操作することができます。イディオムは上記と同じです。

keys = sorted(mydict)

# forward and backward iteration
for k in keys:
  # ...
for k in reversed(keys):
  # ...

# function that returns a forward or backward iterator based on an argument
def forward_or_backward(seq, forward=True):
  for x in (iter if forward else reversed)(seq):
    yield x

# random access inside a loop
for i, key in enumerate(keys):
  # next element
  key[i+1]

# the between and first_beyond functions above also work for lists

残りの機能は、これらの部分から接着することができます。キーのリストだけでなく、反復可能な関数で機能するのに十分な一般的な方法で関数を記述できるため、特別なクラスを作成することは賢明ではないことに注意してください。

于 2012-04-26T22:26:42.267 に答える
1

このようなとき、私はデータの一部を2つの異なる方法で保存する傾向があります。

dictを維持しながら、dictのキー（r値？）を表示するintでインデックス付けされたリストを追加した場合はどうなりますか？これにより、おそらく必要なランダムアクセス（理由があると思います）と、追加する必要があると思われる前後の動作が得られます。

このルートを使用する場合は、すべてをクラスにまとめることができるため、コード全体に二重更新が散在することはありません。

Treapまたは赤黒木を実装し、それを変更してキーを指定し、次または前のキーでキーと値のペアを取得できるようにすることは、おそらく実行可能です。値を頻繁に挿入または削除する場合は、これらのいずれかが適している可能性があります。

于 2012-04-26T22:17:03.523 に答える
0

順序付けられたdictはおそらくあなたが望むものを与えるようです。ドキュメントはこちらです。

于 2012-04-26T22:33:24.907 に答える