1

優先度/タスクタプルのリストの最小値と最大値を比較し、優先度を変更するいくつかの操作を実行してから、それらをリストに再挿入し、リストを適切に更新するスケジューリングアルゴリズムがあります。heapqはこれに最適なデータ構造でしょうか？ポップせずに最初の比較（基本的には、優先度の値が十分に離れていて、さらに操作が必要かどうかを判断します。そうでない場合、関数は停止します）を行うにはどうすればよいですか？比較が行われたら、heapqは最小値のみをポップするように設計されているので、最小値とともに最大値をどのように取得しますか？

4

2 に答える 2

3

heapq最小ヒープのみを提供します。つまり、min値をO（log N）時間でポップできますが、値をポップすることはできませんmax。

のような両面データ構造が必要なheapq場合は、いくつかの基本的なオプションがあります。

まず、通常の最小ヒープの問題は何ですか？APIだけではありません。最大値を見つけるには時間ではO(n)なくO(1)時間がかかるため、ポップするO(n)のではなく時間がかかりO(log n)ます。これが改善したい重要なことです。

単純なハックでは、2つのヒープを保持します。1つは通常の値を使用し、もう1つは通常の値を装飾して逆方向にソートします。擬似コードでの実装は次のとおりです。

def push(self, value):
    insert into both normal and reversed heaps
def minpop(self):
    check that the min value of normal hasn't reached the min value of reversed
    pop and return the min value of normal
def maxpop(self):
    check that the min value of reversed hasn't reached the min value of normal
    pop and return the min value of reversed

一見すると、すべての操作の最悪の場合の動作は、minheapの2倍になるはずですが、そうではありません。特に、最悪の場合のスペースは、これまでに挿入された要素の数であり、挿入された数の2倍（削除された数）よりもはるかに多くなる可能性があります。（たとえば、1000個のアイテムを挿入し、100、900 >> 200を削除した場合。）

これが機能しないユースケースはたくさんありますが、ユースケースで機能しないかどうかは明らかです。しかし、それが適切である場合、それは非常に単純です。

適切でない場合は、実際の最小-最大ヒープを使用できます。これは基本的に、最小ヒープのバージョンnormalとreversedバージョンを単一の構造にインターリーブするだけであり、上記の「チェック」の場合に（値を残すのではなく）正しいことを簡単に実行できるようにします。

ただし、両端優先キューの対称的なパフォーマンスが必要な場合は、実際には、バランスの取れたツリーまたはスキップリストよりも優れた方法はありません。（まあ、一般的な目的ではありません。特定の動作特性がある場合、それは当てはまらない可能性があります。）そして、最小-最大バイナリヒープよりも多くのAVLツリー、赤黒木、およびスキップリストの実装があります。したがって、PyPIとActiveStateレシピで「バランスツリー」、「赤黒木」、「AVLツリー」、「スキップリスト」などを検索するbintreesとskiplist、とのようなものが見つかります。これらはすべて機能するはずです。

ただし、お勧めしblistます。十分に研究されたデータ構造ではなく、バランスの取れたツリーと配列の特別なハイブリッドを使用しているため、一見信頼性が低いと思われるかもしれません。ただし、競合するどのモジュールよりもはるかに多くの使用法と実際のテストが行​​われていると思います。また、かなり大幅に最適化されています。A * log Bn + C（パフォーマンスを扱っている場合、変更するAかC、通常は変更よりもはるかに大きな影響がありBます。）また、優れたインターフェイスも備えています。実際には、それらのいくつかです。を使用する場合は、、、、、、およびを、期待どおりに実行できますblist.sortedlist。sl[0]sl[-1]sl.pop(0)sl.pop(-1)sl.add(x)

したがって、コードは次のようになります（英語の説明を理解している場合）。

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
    def add(self, priority, task):
        self.sl.add((priority, task))
    def step(self):
        if self.sl[-1][0] - self.sl[0][0] < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)

これらの方法のいずれかの問題は、両側を覗くための最悪のケースがではO(log N)なくであるということO(1)です。ただし、これらが必要な操作だけである場合は、これを回避する簡単な方法があります。これらの値をキャッシュしておくだけです。

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
        self.minprio, self.maxprio = None, None
    def add(self, priority, task):
        self.sl.add((priority, task))
        if prio < self.minprio: self.minprio = prio
        elif prio > self.maxprio: self.maxprio = prio
    def step(self):
        if self.maxprio - self.minprio < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)
        self.minprio, self.maxprio = sl[0][0], sl[-1][0]

これにより、のstep O(1)代わりに高速パスが作成され、O(log n)既存のすべてのO(log n)操作がそのまま残りO(log n)ます。

ここで関連する可能性のあるバイナリヒープを置き換えることができる他の種類のヒープの説明については、ウィキペディアも参照してください。

最後に、igorrsのコメントが私に思い出させたメモ：

ここでは、同じ最悪の場合のアルゴリズムの複雑さをもたらすさまざまな異なるデータ構造があります。場合によっては、回避するものでO(n)十分な場合もあるため、最も単純な実装を使用して、それを実行する必要があります。ただし、場合によっては（特に、多くの操作で小さいn、または非定型のデータの場合）、定数係数、最良のケースなどが大きな違いを生む可能性があります。その場合、正しいことは、複数の実装を構築し、実際のデータでテストして、何が最も速いかを確認することです。

于 2013-01-10T01:37:01.927 に答える
1

ヒープを検討していることを考えると、（n要素の総数である）期待は次のとおりであると推測できます。

  1. 時間内に最小のキーと最大のキーを見つけますO(1)。
  2. 最小のキーを持つ要素と最大のキーを持つ要素をO(log(n))時間内に（変更されたキーで）再挿入します。

これは、最小-最大ヒープで実現できます。残念ながら、これはPythonの標準ライブラリでは利用できないと思います。

最初の要件を緩和すると、バランスの取れたツリー（たとえば、赤黒）でうまくいきO(log(n))、必要なすべての操作に時間がかかります。

Pythonの標準ライブラリもバランスの取れたツリーを提供しないため、独自のツリーを作成するか、実装を探す必要があります。

于 2013-01-10T01:15:00.490 に答える