3

関数がヒープリストの要素を変更するたびにコールバック通知を取得したいとheapq.heapify思います (これは、リスト内のオブジェクトとそのインデックスがどのように変更されるかを追跡するために必要です)。

私の計画は、リスト内の変更を追跡するメソッドからサブクラス化し、メソッドlistをオーバーライドすることでした。__setitem__したがって、ここにサブクラスがあります： 

class List2(list):

    def __setitem__(self, key, value):
        print 'setitem: key=',key,' value=',value
        list.__setitem__(self, key, value)

    def __getitem__(self, key):
        print 'getitem: key=',key
        return list.__getitem__(self, key)

次に、インスタンスを作成し、List2heapify を呼び出します。

h = List2([12, -3, 0, 5, 1, 7])
heapq.heapify(h)

問題は、オーバーライドさ__setitem__れた が 内から呼び出されないことheapq.heapifyです。heapq.heapifyList2 のインスタンスをデフォルトのリストであるかのように扱っているようです。それが組み込み関数であるという事実と関係があると思いますが、heapq.heapifyまだわかりません。

オーバーライドさ__setitem__れたものが呼び出されないのはなぜheapq.heapifyですか?

ここで興味深いのは、heapq のコードをローカル モジュールにコピー アンド ペーストすると (つまり、組み込み関数ではなくなります)、期待どおりに動作し、 へList2.__settiem__の呼び出しが発生しますが、デフォルトでは動作しません (内蔵) heapq.

問題がある場合はPython 2.7

4

3 に答える 3

4

Python 3.0 プロジェクトの一部として、また 3.3 についても、何かがlist一般的なsequence typeorに対してとられる場合にそれをより明確にするドキュメントを調べ、3.3で間違いなく述べています。これは、2.7 でも同じことが当てはまることを意味します。mutable sequence typeiterableheapqlist

コードを追跡すると、C 実装がある場合、 in_heapqmodule.cはheapify明示的に呼び出して、型が のようなシーケンスではなくPyList_Check実数であることを確認します。これは のサブクラスをキャッチしませんが、 and を ( 内で) andを直接呼び出していることがわかります。そのため、サブクラスをベースオブジェクトとして扱います。(そして、これは現在のトランクの時点では変更されていません。)listlistlistPyList_GETSIZE_siftupPyList_GET_ITEMPyList_SET_ITEMlistlist

したがって、これを回避する方法はいくつかあります。

まず、@FogleBird が示唆するように、純粋な Python 実装をフォークするだけでheapq済みます。まったく同じものをプロジェクトにコピーし、別の名前を付けて、from _heapq import *318 ～ 321 行のビットを削除します。

ただし、これはかなり遅くなる可能性があります。

CPython からPyPyに切り替えると、それが自動的に解決される可能性があります (また、必要かどうかにかかわらず、純粋な Python 実装を取得できることも意味します)。

実際、私は 1,000,000 項目のリストで簡単なテストを実行しました。PyPy が実際にこのList2クラスを使用していることを確認した後、文字列を出力する代わりにグローバル変数に格納するように変更しました。(そうしないと、Mac では実際の作業よりも 3 倍長く、Windows では 40 倍長く印刷に時間がかかりました…) 次に、さまざまな異なる Python で実行しました。

  • CPython 2.7.2 64 ビット Mac: 2.079 秒
  • CPython 3.3.0 64 ビット Mac: 1.997 秒
  • CPython 3.3.0 32 ビット Mac: 2.197 秒

  • PyPy 2.7.2/1.9.0 64 ビット Mac: 1.619 秒

  • CPython 2.7.3 32 ビット Win: 3.997 秒

  • PyPy 2.7.21.9.0 32 ビット Win: 2.334 秒

そのため、実際に Python リストのオーバーライドを呼び出したにもかかわらず、PyPy は他のすべてを吹き飛ばしました。(私は Jython や IronPython をテストしませんでした。JVM や .NET の起動とウォームアップ時間が非常に長いため、公平性を保つためにはもっと長いテストが必要になるためです…しかし、純粋な Pythonheapqモジュールも使用する必要があります。 .)

しかし、それはあなたが望んでいるよりも劇的な変化かもしれません。もう 1 つの方法は、フォーク_heapqmodule.cすることです。C API をまったく知らなくても、これは実際には単なる検索と置換の仕事です。関数ごとに、対応する関数 ( -> 、->など)PyList_FOOに置き換えます。そして、モジュール名が表示される両方の場所を置き換えます。それでおしまい。次に、モジュールをビルドし、フォークに. これはまだ組み込み実装ほど高速ではありませんが、それはメソッドとメソッドを何度も呼び出すためです。これはまさにあなたが望んでいることです。PySequence_FooPyList_SIZEPySequence_SizePyList_GETITEMPySequence->GetItemmyheapq.pyimport _myheapqimport _heapq__getitem____setitem__

于 2012-12-18T02:21:51.133 に答える
3

heapq可能な場合はC実装を使用し_heapqます。

heapqモジュールをローカルパッケージにコピーする_heapqと、が見つかりません。また、Python implementation使用されます。これは、実際にを使用__setitem__し、のようなステートメントを__getitem__見つけることができます。heap[pos] = heap[childpos]_siftup

于 2012-12-18T00:47:45.390 に答える
1

heapq は、お使いのプラットフォームで利用可能な場合はネイティブ コードを使用します。これが問題だと思いますが、その理由は完全にはわかりません。

おそらく、別のアプローチを取り、リスト項目の元の指標を追跡することができます。

>>> n = [12, -3, 0, 5, 1, 7]
>>> m = [(v, i) for i, v in enumerate(x)]
>>> heapq.heapify(m)
>>> m
[(-3, 1), (1, 4), (0, 2), (5, 3), (12, 0), (7, 5)]

次に、ヒープ化後に値とインデックスを抽出できます...

>>> values, indicies = zip(*m)
>>> values
(-3, 1, 0, 5, 12, 7)
>>> indicies
(1, 4, 2, 3, 0, 5)

編集：リストから派生していないクラスのインスタンスを提供することにより、ヒープを「だます」ことを試みました。おそらくネイティブコードがパフォーマンス上の理由からそれを前提として使用しているため、リストが必要です。

>>> class List(object):
...     def __init__(self, data):
...         self.data = data
...     def __getitem__(self, key):
...         print 'getitem', key
...         return self.data[key]
...     def __setitem__(self, key, value):
...         print 'setitem', key, value
...         self.data[key] = value
... 
>>> x = List([12, -3, 0, 5, 1, 7])
>>> heapq.heapify(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: heap argument must be a list

編集 2 : heapq.py のこのコードに注意してください。これは Python の実装をオーバーライドします。

# If available, use C implementation
try:
    from _heapq import *
except ImportError:
    pass

編集 3 : Python のドキュメントでは、根本的な問題について説明しています。つまり、「保留中のタスクを削除する必要がある場合、どのようにそれを見つけてキューから削除しますか?」

http://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes

アイデアは、単にエントリを削除済みとしてマークすることです。これらのアイテムが優先キューの一番上にある場合は、それらを無視します。ドキュメントにはサンプルコードがあります。

于 2012-12-18T00:44:37.697 に答える