10

Sorting a million 32-bit integers in 2MB of RAM using Pythonという質問に対する Guido の悪名高い回答を読んで、モジュールheapqを発見しました。

また、私はそれについてジャックを理解していなかったし、それで何ができるかも知らなかった.

ヒープ キュー アルゴリズムとは何か、そしてそれで何ができるのか (ことわざの 6 歳のターゲットで) 説明してもらえますか?

それを (モジュールと一緒に) 使用することで問題が解決され、他の何かではなく、それを使用するとよりよく解決される簡単なPython スニペットを提供できますか?heapq

4

2 に答える 2

10

heapq部分的にソートされたデータ構造であるバイナリ ヒープを実装します。特に、これらには 3 つの興味深い操作があります。

  • heapifyO( n ) 時間でリストをインプレースのヒープに変換します。
  • heappushO(lg n ) 時間で要素をヒープに追加します。
  • heappopO(lg n ) 時間でヒープから最小の要素を取得します。

多くの興味深いアルゴリズムは、パフォーマンスのためにヒープに依存しています。最も単純なものは、おそらく部分的な並べ替えです。リスト全体を並べ替えずに、リストのk 個の最小 (または最大) 要素を取得します。heapq.nsmallest( nlargest) はそうします。の実装は、nlargest次のように言い換えることができます。

def nlargest(n, l):
    # make a heap of the first n elements
    heap = l[:n]
    heapify(heap)

    # loop over the other len(l)-n elements of l
    for i in xrange(n, len(l)):
        # push the current element onto the heap, so its size becomes n+1
        heappush(heap, l[i])
        # pop the smallest element off, so that the heap will contain
        # the largest n elements of l seen so far
        heappop(heap)

    return sorted(heap, reverse=True)

分析: の要素数を N としlます。heapifyO(n) のコストで 1 回実行されます。それはごくわずかです。次に、Nn = O(N) 回実行するループで、aheappopと aheappushをそれぞれ O(lg n) コストで実行し、合計実行時間を O(N lg n) とします。sorted(l)[:n]N >> n の場合、 O(N lg N) 時間かかる他の明白なアルゴリズム と比較して、これは大きな勝利です。

于 2012-12-09T15:17:44.340 に答える
2

例: 1000 の浮動小数点数のセットがあります。セットから最小のアイテムを繰り返し削除し、0 から 1 の間の乱数に置き換えたいとします。これを行う最も速い方法は、heapq モジュールを使用することです。

heap = [0.0] * 1000
# heapify(heap)   # usually you need this, but not if the list is initially sorted
while True:
    x = heappop(heap)
    heappush(head, random.random())

これには、反復ごとに、ヒープの長さの対数に相当する時間がかかります (つまり、長さ 1000 のリストの場合、約 7 単位)。他のソリューションは、直線的な時間を要します (つまり、約 1000 単位で、140 倍遅くなり、長さが増加するとますます遅くなります)。

lst = [0.0] * 1000
while True:
    x = min(lst)    # linear
    lst.remove(x)   # linear
    lst.append(random.random())

また：

lst = [0.0] * 1000
while True:
    x = lst.pop()   # get the largest one in this example
    lst.append(random.random())
    lst.sort()      # linear (in this case)

あるいは：

lst = [0.0] * 1000
while True:
    x = lst.pop()   # get the largest one in this example
    bisect.insort(lst, random.random())   # linear
于 2012-12-09T15:09:57.307 に答える