Pythonの技法:heapqモジュールによる優先順位付きキューの実装

文:Nick Gibson(Builder AU)  翻訳校正:原井彰弘
2008-01-08 12:00:00
  • このエントリーをはてなブックマークに追加

from random import randint
def minheap(n, Print=True):
    numbers = [randint(0,100) for i in range(n)]
    heapify(numbers)
    if Print:
        print "Original: %s" % (numbers)
    for i in range(n):
        newint = randint(0,100)
        heappush(numbers, newint)
        oldint = heappop(numbers)
        if Print:
            print "new number: %s, minimum: %s, heap: %s" % (newint, oldint, numbers)

>>> minheap(10)
Original: [8, 33, 59, 48, 46, 74, 70, 97, 54, 78]
new number: 59, minimum: 8, heap: [33, 46, 59, 48, 59, 74, 70, 97, 54, 78]
new number: 58, minimum: 33, heap: [46, 48, 59, 54, 58, 74, 70, 97, 59, 78]
new number: 30, minimum: 30, heap: [46, 48, 59, 54, 58, 74, 70, 97, 59, 78]
new number: 66, minimum: 46, heap: [48, 54, 59, 59, 58, 74, 70, 97, 66, 78]
new number: 54, minimum: 48, heap: [54, 54, 59, 59, 58, 74, 70, 97, 66, 78]
new number: 12, minimum: 12, heap: [54, 54, 59, 59, 58, 74, 70, 97, 66, 78]
new number: 13, minimum: 13, heap: [54, 54, 59, 59, 58, 74, 70, 97, 66, 78]
new number: 91, minimum: 54, heap: [54, 58, 59, 59, 78, 74, 70, 97, 66, 91]
new number: 31, minimum: 31, heap: [54, 58, 59, 59, 78, 74, 70, 97, 66, 91]
new number: 17, minimum: 17, heap: [54, 58, 59, 59, 78, 74, 70, 97, 66, 91]

 ヒープを使用した方がずっと高速であることを実際に示すために、挿入ソートを用いてリストをソート済みの状態に保つバージョンを、以下のように作成した。

def minlist(n, Print=True):
numbers = sorted([randint(0,100) for i in range(n)])
if Print:
print "Original: %s" % (numbers)
for i in range(n):
newint = randint(0,100)
if newint >= numbers[n-1]:
numbers.append(newint)
else:
for j in range(n):
if newint < numbers[j]:
numbers = numbers[:j] + [newint] + numbers[j:]
break
oldint = numbers.pop(0)
if Print:
print "new number: %s, minimum: %s, heap: %s" % (newint, oldint, numbers)

 それでは、要素数を増やした場合にお互いの結果がどのように変化するかを見てみよう。

>>> i = time(); minlist(10000, False); print time()-i
11.6881940365
>>> i = time(); minheap(10000, False); print time()-i
0.142065048218
>>> i = time(); minheap(50000, False); print time()-i
0.621912002563
>>> i = time(); minheap(100000, False); print time()-i
1.33778500557
>>> i = time(); minheap(1000000, False); print time()-i
14.6926519871

 これを見れば、同じ速度ではヒープを利用したバージョンの方が、リストを用いたバージョンよりも100倍多い要素数を扱えることが分かるだろう。

 自分でより細かな制御を行いたい場合やより多くの機能が欲しい場合で、古典的なアルゴリズムがそれを必要とする場合は、自分でヒープを実装しなければならない。しかし、heapqモジュールの少数の関数を学べば、基本的にはそれでことが足りるだろう。

この記事は海外CNET Networks発のニュースをシーネットネットワークスジャパン編集部が日本向けに編集したものです。海外CNET Networksの記事へ

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]