Python優先キュー：ガイド

Python優先キュー：ガイド

Python優先キューは、データを特定の順序で格納します。 Pythonで優先度付きキューを実装するには、キュークラスを使用する方法とheapqモジュールを使用する方法の2つがあります。

リスト内の各アイテムの値に基づいてデータを並べ替えることができます。たとえば、最大値をリストの最初に表示し、最小値をリストの最後に表示したい場合があります。

そこで優先キューが登場します。優先キューは、キーの値に基づいて昇順でデータを格納するデータ構造です。これにより、キュー内の最小値と最大値に簡単にアクセスできます。

このチュートリアルでは、リストを使用して優先キューを作成しない理由について説明します。 Python優先キューを作成するために使用できる2つのより効率的なアプローチを紹介します。

Python優先キューとは何ですか？

優先度付きキューは、優先度が最も高い要素の順にデータを格納するキューの修正バージョンです。優先度キュー内の各要素の優先度は、要素の値に応じて決定されます。

コンピュータサイエンスでは、キューは先入れ先出し（FIFO）の順序でアイテムを格納するデータ構造です。この構造を使用すると役立つシナリオがいくつかあります。

たとえば、レストランの注文追跡アプリを作成しているとします。最初に注文した人は、次に注文した人よりも先にサービスを受ける必要があります。注文を追跡するには、キューを使用する必要があります。

Pythonで優先キューを定義する方法は2つあります。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

• PriorityQueueキュークラスの使用
• heapqモジュールの使用

リスト構造を使用して優先キューを定義できます。ただし、この戦略は、PriorityQueueキュークラスまたはheapqモジュールを使用するよりも効率的ではありません。

優先キューPython：queue.PriorityQueue

queue.PriorityQueue クラスはPython優先キューを作成します。このクラスはPythonキューライブラリの一部です。このクラスを使用するには、キューライブラリをインポートする必要があります。 PriorityQueueからアイテムを取得するには、get（）メソッドを使用できます。

PriorityQueueクラスにアクセスするには、コードにインポートする必要があります。これは、次のPythonインポートステートメントを使用して実行できます。

from queue import PriorityQueue

地元のコンサートでチケット所有者の優先キューを作成するとします。このコードを使用してこれを行うことができます：

from queue import PriorityQueue

ticket_holders = PriorityQueue()

ticket_holders.put((3, 'Paul'))
ticket_holders.put((1, 'Miles'))
ticket_holders.put((2, 'Dani'))

while not ticket_holders.empty():
	item = ticket_holders.get()
	print(item)

コードは次のようになります：

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

このコードでは、最初にPriorityQueueクラスをキューからインポートします。 ライブラリの場合、 ticket_holdersという優先キューを初期化します。 。次に、優先キューに3つのタプルを挿入します。これらのタプルには、チケットに関連付けられたチケット番号と名前が格納されます。

Pythonのwhileループを使用して、 ticket_holdersの各アイテムを実行します。 優先キュー。次に、 get（）を使用してそのアイテムを取得します 。

queue.PriorityQueue この方法は効率的で使いやすいため、優先キューを作成する必要がある場合に最適です。

優先キューPythonヒープモジュール

heapqモジュールを使用すると、Python優先キューを定義できます。 heapqデータ構造は、優先度の高い順に項目を削除します。 heapq構造では、最も低い値が最も低い優先度を持ち、最も高い値が最も高い優先度を持ちます。

heapqモジュールを使用する前に、まず次のインポートステートメントを使用してコードにインポートする必要があります。

import heapq

前の例に戻りましょう。コンサートのチケット所有者に関する情報を格納するための優先キューを作成するとします。 heapqモジュールとこのプログラムを使用してこれを行うことができます：

import heapq

ticket_holders = []

heapq.heappush(ticket_holders, (3, 'Paul'))
heapq.heappush(ticket_holders, (1, 'Miles'))
heapq.heappush(ticket_holders, (2, 'Dani'))

while ticket_holders:
	item = heapq.heappop(ticket_holders)
	print(item)

コードは次のようになります：

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

まず、heapqライブラリをインポートしてから、 ticket_holdersというPython変数を初期化しました。 。 heappush（）を使用しました 3つのタプルを優先キューにプッシュするメソッド。このキューには、各チケット所有者のチケット番号と各チケット所有者の名前が格納されます。

次に、優先キュー内の各アイテムをループするwhileループを作成しました。このループは、 heappop（）を使用してキューの一番上にあるアイテムを削除します 。次に、削除されたアイテムがコンソールに出力されます。ご覧のとおり、キュー内のすべてのアイテムは優先度の高い順に印刷されます。

リストを保持してはいけない理由

技術的には、Pythonリストデータ構造を使用して優先キューを作成できます。これを行うには、リストを作成してから、昇順で並べ替えます。

ただし、これは優先キューを維持するための比較的非効率的な方法です。リスト内のアイテムを変更すると、リストを並べ替える必要があり、時間がかかります。

いくつかの値を格納するだけでよい場合は、従来のリストを優先キューとして使用できます。ただし、より大きなキューを作成する場合は、リストは適切なオプションではありません。

参考までに、リストを使用した優先度付きキューの例を見ていきましょう。最初にコンサートに参加する必要があるチケット所有者の順序を格納する優先キューを作成するとします。次のコードを使用して、このキューを作成できます。

ticket_holders = []

ticket_holders.append((3, 'Paul'))
ticket_holders.append((1, 'Miles'))
ticket_holders.append((2, 'Dani'))

ticket_holders.sort(reverse=True)

while ticket_holders:
	item = ticket_holders.pop()
	print(item)

コードは次のようになります：

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

ticket_holdersというリストを作成しました 、次に3つのタプルをリストに追加しました。各タプルには、チケット所有者のチケット番号とその名前が含まれていました。次に、Python sort（）を使用しました チケット所有者のリストを逆の順序で並べ替える機能。

ticket_holders内のすべてのアイテムを反復処理するwhileループを作成しました リストとリストの一番上にあるアイテム。次に、コードは削除されたアイテムをコンソールに出力します。

結論

優先キューを作成するための最も一般的な2つは、heapqモジュールまたは queue.PriorityQueueを使用することです。 クラス。技術的にはリストを優先キューとして使用できますが、このアプローチは適切に拡張できません。

このチュートリアルでは、例を参照して、Pythonで優先度付きキューを作成する方法について説明しました。これで、Pythonプロフェッショナルのように独自の優先度付きキューの作成を開始するために必要な知識を身に付けることができます。

Pythonの学習方法の詳細については、Pythonの完全な学習方法ガイドをご覧ください。