Pythonシミュレーションスタックキューおよび優先キューの操作記録
13052 ワード
スタック:データは後進先出(LIFO)last in first out
キュー:データは先進先出(FIFO)first in first out
1つ目は、(スタックをシミュレートしたりキューをシミュレートしたりすることができます)良いことです.(もう一つの欠点は、簡単な方法で容器容量のスペースを設定できないことです.)
リストはコンテナシーケンスであり,スタック操作をシミュレートする際にも速度が比較的よい.
スタック操作をシミュレートする場合は、popにappendを使用する必要があります.(スタックをシミュレートする場合、性能が優れている)
次に示すのはシミュレーションキュー操作であり,シミュレーションスタック操作は簡単で,appendがpopにあるので示さない.
このようなシミュレーション操作キューの効率は非常に低いです.最初の要素を移動するたびに、後ろの要素インデックスが変化するためです.
専門的な言い方にかかる時間はO(n)
2つ目はcollectionsです.Deque、このシミュレーションスタックはキューに非常に優れたコンテナシーケンスです.(最大容量を超えると、最初に入った要素が容器から蹴り出されるように、容器容量を設定できます)
オブジェクトの中間にランダムにアクセスする要素のパフォーマンスが悪く、時間がかかるのはO(n)ですが、一般的にコンテナシーケンスを操作し、中間要素にアクセスすることはめったにありません.
スタック操作のシミュレーション:
シミュレーションキューアクション:
上の2つは、スタックをシミュレートしたり、キューをシミュレートしたりできるコンテナシーケンスです.次に、スタックまたはキューを単一にシミュレートすることしかできません.
queue.LifoQueueは文字通りアナログスタックであることがわかり,後進先出である.Queueモジュールの下のコンテナシーケンスは、複数の同時生産者を消費者にサポートするロック文を提供します.モジュールの下の多くのクラスの例は、一般的にオンラインスレッド間の通信を使用します.
このコンテナは、エレメントが取れない場合や、エレメントの数が設定容量を超えた場合にプログラムをブロックするためです.(だからこれは容量を設定できるのは明らかです)
スタックの私が知っているのは上の3つの形式で、一般的にcollectionsを優先しています.queue
後続の単一機能プライマリキューのシーケンスコンテナ.
queuq.Queueと前のLifoQueueの機能は操作が少なく,スレッド間のタスク通信で動作している.
最後にもう一つQueueはジョブキューを行います.
multiprocessing.Queueは主にプロセス間で作業通信を行うツールであり、具体的には基本的に
queue.Queueの差が少なく、コードをつけません.
最後に優先キューを簡単に記録します.
優先キューは、コンテナ内のキー値が最小または最大の要素に迅速にアクセスするために、フルシーケンス関係を持つキーを使用して要素を管理するコンテナデータ構造を示します.
1、リスト、手動で秩序あるキューを維持する.
bisectソートが完了した場合、インデックスの検索が非常に速いbisect.bisectはインデックスを検索できます.デフォルトよりindexは速すぎます.
Heapq--リストベースの二叉スタック.
Heaqpは二叉スタックであり,通常は通常のリストで実現され,O(logn)時間内に最小の要素を挿入して取得することができる.
HeapqモジュールはPythonで良い優先順位キューで実現されています.heapqの技術的には最小スタック実装のみが提供されるため、実際の優先キューに含まれる特性を得るために、ソートの安定性を確保するために追加のステップを追加する必要がある.
上にheapqの2つの方式のスタックリストを用いて二叉スタック操作を行った.1つ目は変数要素用heapqである.heappushはデータロードを行い、第2種は直接heapqを用いる.heapifyはリスト要素に対して二叉スタックを実行する.
heapq.nlargest,heapq.nsmallestは、key=関数を介して関数を伝達するコンテナ要素内の最大値範囲を最小値範囲と見出すことができる.
queue.PriorityQueue内部でもheapqが使用されており,時間的複雑度はheapqと同じ空間的複雑度であるが,PriorityQueueは同時生産者消費者を実行する.特定の条件でブロックできます.
Queueの3つのモジュールは、基本的にシミュレーションキュー、スタック、優先順位キューで使用されます.
それぞれqueue.LifoQueue,queue.Queue,queue.PriorityQueue.
Pythonの前に記録された3つの優先キューで、priorityQueueが優先で、オブジェクト向けのインタフェースが良好です.
PriorityQueueのロックオーバーヘッドを回避するには、heapqモジュールを直接使用することをお勧めします.
キュー:データは先進先出(FIFO)first in first out
1つ目は、(スタックをシミュレートしたりキューをシミュレートしたりすることができます)良いことです.(もう一つの欠点は、簡単な方法で容器容量のスペースを設定できないことです.)
リストはコンテナシーケンスであり,スタック操作をシミュレートする際にも速度が比較的よい.
スタック操作をシミュレートする場合は、popにappendを使用する必要があります.(スタックをシミュレートする場合、性能が優れている)
次に示すのはシミュレーションキュー操作であり,シミュレーションスタック操作は簡単で,appendがpopにあるので示さない.
In [228]: ll = list()
In [229]: ll.append(' 1')
In [230]: ll.append(' 2')
In [231]: ll.append(' 3')
In [232]: ll.pop(0)
Out[232]: ' 1'
In [233]: ll.pop(0)
Out[233]: ' 2'
In [234]: ll.pop(0)
Out[234]: ' 3'
このようなシミュレーション操作キューの効率は非常に低いです.最初の要素を移動するたびに、後ろの要素インデックスが変化するためです.
専門的な言い方にかかる時間はO(n)
2つ目はcollectionsです.Deque、このシミュレーションスタックはキューに非常に優れたコンテナシーケンスです.(最大容量を超えると、最初に入った要素が容器から蹴り出されるように、容器容量を設定できます)
オブジェクトの中間にランダムにアクセスする要素のパフォーマンスが悪く、時間がかかるのはO(n)ですが、一般的にコンテナシーケンスを操作し、中間要素にアクセスすることはめったにありません.
スタック操作のシミュレーション:
from collections import deque
In [34]: deque?
Init signature: deque(self, /, *args, **kwargs)
Docstring:
deque([iterable[, maxlen]]) --> deque object
A list-like sequence optimized for data accesses near its endpoints.
File: /usr/local/Cellar/python/3.7.4/Frameworks/Python.framework/Versions/3.7/lib/python3.7/collections/__init__.py
Type: type
Subclasses:
In [35]: d = deque(range(10),maxlen=5)
In [36]: d
Out[36]: deque([5, 6, 7, 8, 9])
In [37]: d.append(10)
In [38]: d
Out[38]: deque([6, 7, 8, 9, 10])
In [39]: d.pop()
Out[39]: 10
In [40]: d.pop()
Out[40]: 9
In [41]: d.pop()
Out[41]: 8
In [42]: d.pop()
Out[42]: 7
In [43]: d.pop()
Out[43]: 6
In [44]: d.pop()
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
in
----> 1 d.pop()
IndexError: pop from an empty deque
シミュレーションキューアクション:
d
Out[45]: deque([])
In [46]: d.append(1)
In [47]: d.append(2)
In [48]: d.append(3)
In [49]: a
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
in
----> 1 a
NameError: name 'a' is not defined
In [50]: d
Out[50]: deque([1, 2, 3])
In [51]: d.popleft()
Out[51]: 1
In [52]: d.popleft()
Out[52]: 2
In [53]: d.popleft()
Out[53]: 3
上の2つは、スタックをシミュレートしたり、キューをシミュレートしたりできるコンテナシーケンスです.次に、スタックまたはキューを単一にシミュレートすることしかできません.
queue.LifoQueueは文字通りアナログスタックであることがわかり,後進先出である.Queueモジュールの下のコンテナシーケンスは、複数の同時生産者を消費者にサポートするロック文を提供します.モジュールの下の多くのクラスの例は、一般的にオンラインスレッド間の通信を使用します.
このコンテナは、エレメントが取れない場合や、エレメントの数が設定容量を超えた場合にプログラムをブロックするためです.(だからこれは容量を設定できるのは明らかです)
In [54]: from queue import LifoQueue
In [55]: LifoQueue?
Init signature: LifoQueue(maxsize=0)
Docstring: Variant of Queue that retrieves most recently added entries first.
File: /usr/local/Cellar/python/3.7.4/Frameworks/Python.framework/Versions/3.7/lib/python3.7/queue.py
Type: type
Subclasses:
In [56]: q = LifoQueue()
In [57]: q = LifoQueue(maxsize=3)
In [58]: q.put(1)
In [59]: q.put(2)
In [60]: q.put(3)
In [61]: q.get()
Out[61]: 3
In [62]: q.get()
Out[62]: 2
In [63]: q.get()
Out[63]: 1
In [64]: q.get()
スタックの私が知っているのは上の3つの形式で、一般的にcollectionsを優先しています.queue
後続の単一機能プライマリキューのシーケンスコンテナ.
queuq.Queueと前のLifoQueueの機能は操作が少なく,スレッド間のタスク通信で動作している.
In [94]: q = Queue(maxsize=3)
In [95]: q.put(1)
In [96]: q.put(2)
In [97]: q.put(3)
In [98]: q.get()
Out[98]: 1
In [99]: q.get()
Out[99]: 2
In [100]: q.get()
Out[100]: 3
In [101]: q.get()
最後にもう一つQueueはジョブキューを行います.
multiprocessing.Queueは主にプロセス間で作業通信を行うツールであり、具体的には基本的に
queue.Queueの差が少なく、コードをつけません.
最後に優先キューを簡単に記録します.
優先キューは、コンテナ内のキー値が最小または最大の要素に迅速にアクセスするために、フルシーケンス関係を持つキーを使用して要素を管理するコンテナデータ構造を示します.
1、リスト、手動で秩序あるキューを維持する.
In [102]: q = []
In [103]: q.append((2, 'code'))
In [104]: q.append((1,'eat'))
In [105]: q.append((3,'sleep'))
In [106]: q.sort(reverse=True)
In [107]: q.pop()
Out[107]: (1, 'eat')
In [108]: q.pop()
Out[108]: (2, 'code')
In [109]: q.pop()
Out[109]: (3, 'sleep')
In [110]: import bisect
In [111]: bisect.insort(q,(2, 'code'))
In [112]: bisect.insort(q,(1, 'eat'))
In [113]: bisect.insort(q,(3, 'sleep'))
In [114]: q
Out[114]: [(1, 'eat'), (2, 'code'), (3, 'sleep')]
In [115]:
bisectソートが完了した場合、インデックスの検索が非常に速いbisect.bisectはインデックスを検索できます.デフォルトよりindexは速すぎます.
Heapq--リストベースの二叉スタック.
Heaqpは二叉スタックであり,通常は通常のリストで実現され,O(logn)時間内に最小の要素を挿入して取得することができる.
HeapqモジュールはPythonで良い優先順位キューで実現されています.heapqの技術的には最小スタック実装のみが提供されるため、実際の優先キューに含まれる特性を得るために、ソートの安定性を確保するために追加のステップを追加する必要がある.
In [140]:
...: q = [(2, 'code'), (3, 'sleep'), (1, 'eat'), (4,'drink')]
...:
In [141]: random.shuffle(q)
In [142]: h_q = []
In [143]: for i in q:
...: heapq.heappush(h_q, i)
...:
In [144]: heapq.heappop(h_q)
Out[144]: (1, 'eat')
In [145]: heapq.heappop(h_q)
Out[145]: (2, 'code')
In [146]: heapq.heappop(h_q)
Out[146]: (3, 'sleep')
In [147]: heapq.heappop(h_q)
Out[147]: (4, 'drink')
In [148]: q = [(2, 'code'), (3, 'sleep'), (1, 'eat'), (4,'drink')]
In [149]: random.shuffle(q)
In [150]: heapq.heapify(q)
In [151]: heapq.heappop(q)
Out[151]: (1, 'eat')
In [152]: heapq.heappop(q)
Out[152]: (2, 'code')
In [153]: heapq.heappop(q)
Out[153]: (3, 'sleep')
In [154]: heapq.heappop(q)
Out[154]: (4, 'drink')
上にheapqの2つの方式のスタックリストを用いて二叉スタック操作を行った.1つ目は変数要素用heapqである.heappushはデータロードを行い、第2種は直接heapqを用いる.heapifyはリスト要素に対して二叉スタックを実行する.
heapq.nlargest,heapq.nsmallestは、key=関数を介して関数を伝達するコンテナ要素内の最大値範囲を最小値範囲と見出すことができる.
from queue import PriorityQueue
In [163]: PriorityQueue?
Init signature: PriorityQueue(maxsize=0)
Docstring:
Variant of Queue that retrieves open entries in priority order (lowest first).
Entries are typically tuples of the form: (priority number, data).
File: /usr/local/Cellar/python/3.7.4/Frameworks/Python.framework/Versions/3.7/lib/python3.7/queue.py
Type: type
Subclasses:
In [164]: q = [(2, 'code'), (3, 'sleep'), (1, 'eat'), (4,'drink')]
In [165]: p_q = PriorityQueue()
In [166]: for i in q:
...: p_q.put(i)
...:
In [171]: p_q.empty
Out[171]: >
In [172]: p_q.empty()
Out[172]: False
In [173]: while not p_q.empty():
...: print(p_q.get())
...:
...:
(1, 'eat')
(2, 'code')
(3, 'sleep')
(4, 'drink')
In [174]:
queue.PriorityQueue内部でもheapqが使用されており,時間的複雑度はheapqと同じ空間的複雑度であるが,PriorityQueueは同時生産者消費者を実行する.特定の条件でブロックできます.
Queueの3つのモジュールは、基本的にシミュレーションキュー、スタック、優先順位キューで使用されます.
それぞれqueue.LifoQueue,queue.Queue,queue.PriorityQueue.
Pythonの前に記録された3つの優先キューで、priorityQueueが優先で、オブジェクト向けのインタフェースが良好です.
PriorityQueueのロックオーバーヘッドを回避するには、heapqモジュールを直接使用することをお勧めします.