本文目錄一覽：
Python數據結構-隊列與廣度優先搜索（Queue）
隊列（Queue） ：簡稱為隊，一種線性表數據結構，是一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。
我們把隊列中允許插入的一端稱為 「隊尾（rear）」 ；把允許刪除的另一端稱為 「隊頭（front）」 。當表中沒有任何數據元素時，稱之為 「空隊」 。
廣度優先搜索演算法（Breadth First Search） ：簡稱為 BFS，又譯作寬度優先搜索 / 橫向優先搜索。是一種用於遍歷或搜索樹或圖的演算法。該演算法從根節點開始，沿著樹的寬度遍歷樹或圖的節點。如果所有節點均被訪問，則演算法中止。
廣度優先遍歷 類似於樹的層次遍歷過程 。呈現出一層一層向外擴張的特點。先看到的節點先訪問，後看到的節點後訪問。遍歷到的節點順序符合「先進先出」的特點，所以廣度優先搜索可以通過「隊列」來實現。
力扣933
遊戲時，隊首始終是持有土豆的人
模擬遊戲開始，隊首的人出隊，之後再到隊尾（類似於循環隊列）
傳遞了num次之後，將隊首的人移除
如此反覆，直到隊列中剩餘一人
多人共用一台印表機，採取「先到先服務」的隊列策略來執行列印任務
需要解決的問題：1 列印系統的容量是多少？2 在能夠接受的等待時間內，系統可容納多少用戶以多高的頻率提交列印任務？
輸入：abba
輸出：False
思路：1 先將需要判定的詞從隊尾加入 deque; 2從兩端同時移除字元並判斷是否相同，直到deque中剩餘0個（偶數）或1個字元（奇數）
內容參考：
python多進程中隊列不空時阻塞，求解為什麼
最近接觸一個項目，要在多個虛擬機中運行任務，參考別人之前項目的代碼，採用了多進程來處理，於是上網查了查python中的多進程
一、先說說Queue（隊列對象）
Queue是python中的標準庫，可以直接import 引用，之前學習的時候有聽過著名的「先吃先拉」與「後吃先吐」，其實就是這裡說的隊列，隊列的構造的時候可以定義它的容量，別吃撐了，吃多了，就會報錯,構造的時候不寫或者寫個小於1的數則表示無限多
import Queue
q = Queue.Queue(10)
向隊列中放值(put)
q.put(『yang’)
q.put(4)
q.put([『yan’,’xing’])
在隊列中取值get()
默認的隊列是先進先出的
q.get()
『yang’
q.get()
4
q.get()
[『yan’, 『xing’]
當一個隊列為空的時候如果再用get取則會堵塞，所以取隊列的時候一般是用到
get_nowait()方法，這種方法在向一個空隊列取值的時候會拋一個Empty異常
所以更常用的方法是先判斷一個隊列是否為空，如果不為空則取值
隊列中常用的方法
Queue.qsize() 返回隊列的大小
Queue.empty() 如果隊列為空，返回True,反之False
Queue.full() 如果隊列滿了，返回True,反之False
Queue.get([block[, timeout]]) 獲取隊列，timeout等待時間
Queue.get_nowait() 相當Queue.get(False)
非阻塞 Queue.put(item) 寫入隊列，timeout等待時間
Queue.put_nowait(item) 相當Queue.put(item, False)
二、multiprocessing中使用子進程概念
from multiprocessing import Process
可以通過Process來構造一個子進程
p = Process(target=fun,args=(args))
再通過p.start()來啟動子進程
再通過p.join()方法來使得子進程運行結束後再執行父進程
from multiprocessing import Process
import os
# 子進程要執行的代碼
def run_proc(name):
print ‘Run child process %s (%s)…’ % (name, os.getpid())
if __name__==’__main__’:
print ‘Parent process %s.’ % os.getpid()
p = Process(target=run_proc, args=(‘test’,))
print ‘Process will start.’
p.start()
p.join()
print ‘Process end.’
三、在multiprocessing中使用pool
如果需要多個子進程時可以考慮使用進程池(pool)來管理
from multiprocessing import Pool
from multiprocessing import Pool
import os, time
def long_time_task(name):
print ‘Run task %s (%s)…’ % (name, os.getpid())
start = time.time()
time.sleep(3)
end = time.time()
print ‘Task %s runs %0.2f seconds.’ % (name, (end – start))
if __name__==’__main__’:
print ‘Parent process %s.’ % os.getpid()
p = Pool()
for i in range(5):
p.apply_async(long_time_task, args=(i,))
print ‘Waiting for all subprocesses done…’
p.close()
p.join()
print ‘All subprocesses done.’
pool創建子進程的方法與Process不同，是通過
p.apply_async(func,args=(args))實現，一個池子里能同時運行的任務是取決你電腦的cpu數量，如我的電腦現在是有4個cpu，那會子進程task0,task1,task2,task3可以同時啟動，task4則在之前的一個某個進程結束後才開始
上面的程序運行後的結果其實是按照上圖中1，2，3分開進行的，先列印1，3秒後列印2，再3秒後列印3
代碼中的p.close()是關掉進程池子，是不再向裡面添加進程了，對Pool對象調用join()方法會等待所有子進程執行完畢，調用join()之前必須先調用close()，調用close()之後就不能繼續添加新的Process了。
當時也可以是實例pool的時候給它定義一個進程的多少
如果上面的代碼中p=Pool(5)那麼所有的子進程就可以同時進行
三、多個子進程間的通信
多個子進程間的通信就要採用第一步中說到的Queue，比如有以下的需求，一個子進程向隊列中寫數據，另外一個進程從隊列中取數據，
#coding:gbk
from multiprocessing import Process, Queue
import os, time, random
# 寫數據進程執行的代碼:
def write(q):
for value in [‘A’, ‘B’, ‘C’]:
print ‘Put %s to queue…’ % value
q.put(value)
time.sleep(random.random())
# 讀數據進程執行的代碼:
def read(q):
while True:
if not q.empty():
value = q.get(True)
print ‘Get %s from queue.’ % value
time.sleep(random.random())
else:
break
if __name__==’__main__’:
# 父進程創建Queue，並傳給各個子進程：
q = Queue()
pw = Process(target=write, args=(q,))
pr = Process(target=read, args=(q,))
# 啟動子進程pw，寫入:
pw.start()
# 等待pw結束:
pw.join()
# 啟動子進程pr，讀取:
pr.start()
pr.join()
# pr進程里是死循環，無法等待其結束，只能強行終止:
print ‘所有數據都寫入並且讀完’
四、關於上面代碼的幾個有趣的問題
if __name__==’__main__’:
# 父進程創建Queue，並傳給各個子進程：
q = Queue()
p = Pool()
pw = p.apply_async(write,args=(q,))
pr = p.apply_async(read,args=(q,))
p.close()
p.join()
print ‘所有數據都寫入並且讀完’
如果main函數寫成上面的樣本，本來我想要的是將會得到一個隊列，將其作為參數傳入進程池子里的每個子進程，但是卻得到
RuntimeError: Queue objects should only be shared between processes through inheritance
的錯誤，查了下，大意是隊列對象不能在父進程與子進程間通信，這個如果想要使用進程池中使用隊列則要使用multiprocess的Manager類
if __name__==’__main__’:
manager = multiprocessing.Manager()
# 父進程創建Queue，並傳給各個子進程：
q = manager.Queue()
p = Pool()
pw = p.apply_async(write,args=(q,))
time.sleep(0.5)
pr = p.apply_async(read,args=(q,))
p.close()
p.join()
print ‘所有數據都寫入並且讀完’
這樣這個隊列對象就可以在父進程與子進程間通信，不用池則不需要Manager，以後再擴展multiprocess中的Manager類吧
關於鎖的應用，在不同程序間如果有同時對同一個隊列操作的時候，為了避免錯誤，可以在某個函數操作隊列的時候給它加把鎖，這樣在同一個時間內則只能有一個子進程對隊列進行操作，鎖也要在manager對象中的鎖
#coding:gbk
from multiprocessing import Process,Queue,Pool
import multiprocessing
import os, time, random
# 寫數據進程執行的代碼:
def write(q,lock):
lock.acquire() #加上鎖
for value in [‘A’, ‘B’, ‘C’]:
print ‘Put %s to queue…’ % value
q.put(value)
lock.release() #釋放鎖
# 讀數據進程執行的代碼:
def read(q):
while True:
if not q.empty():
value = q.get(False)
print ‘Get %s from queue.’ % value
time.sleep(random.random())
else:
break
if __name__==’__main__’:
manager = multiprocessing.Manager()
# 父進程創建Queue，並傳給各個子進程：
q = manager.Queue()
lock = manager.Lock() #初始化一把鎖
p = Pool()
pw = p.apply_async(write,args=(q,lock))
pr = p.apply_async(read,args=(q,))
p.close()
p.join()
print ‘所有數據都寫入並且讀完’
Python協程之asyncio
asyncio 是 Python 中的非同步IO庫，用來編寫並發協程，適用於IO阻塞且需要大量並發的場景，例如爬蟲、文件讀寫。
asyncio 在 Python3.4 被引入，經過幾個版本的迭代，特性、語法糖均有了不同程度的改進，這也使得不同版本的 Python 在 asyncio 的用法上各不相同，顯得有些雜亂，以前使用的時候也是本著能用就行的原則，在寫法上走了一些彎路，現在對 Python3.7+ 和 Python3.6 中 asyncio 的用法做一個梳理，以便以後能更好的使用。
協程，又稱微線程，它不被操作系統內核所管理，而完全是由程序控制，協程切換花銷小，因而有更高的性能。
協程可以比作子程序，不同的是，執行過程中協程可以掛起當前狀態，轉而執行其他協程，在適當的時候返回來接著執行，協程間的切換不需要涉及任何系統調用或任何阻塞調用，完全由協程調度器進行調度。
Python 中以 asyncio 為依賴，使用 async/await 語法進行協程的創建和使用，如下 async 語法創建一個協程函數：
在協程中除了普通函數的功能外最主要的作用就是：使用 await 語法等待另一個協程結束，這將掛起當前協程，直到另一個協程產生結果再繼續執行：
asyncio.sleep() 是 asyncio 包內置的協程函數，這裡模擬耗時的IO操作，上面這個協程執行到這一句會掛起當前協程而去執行其他協程，直到sleep結束，當有多個協程任務時，這種切換會讓它們的IO操作並行處理。
注意，執行一個協程函數並不會真正的運行它，而是會返回一個協程對象，要使協程真正的運行，需要將它們加入到事件循環中運行，官方建議 asyncio 程序應當有一個主入口協程，用來管理所有其他的協程任務：
在 Python3.7+ 中，運行這個 asyncio 程序只需要一句： asyncio.run(main()) ，而在 Python3.6 中，需要手動獲取事件循環並加入協程任務：
事件循環就是一個循環隊列，對其中的協程進行調度執行，當把一個協程加入循環，這個協程創建的其他協程都會自動加入到當前事件循環中。
其實協程對象也不是直接運行，而是被封裝成一個個待執行的 Task ，大多數情況下 asyncio 會幫我們進行封裝，我們也可以提前自行封裝 Task 來獲得對協程更多的控制權，注意，封裝 Task 需要 當前線程有正在運行的事件循環 ，否則將引 RuntimeError，這也就是官方建議使用主入口協程的原因，如果在主入口協程之外創建任務就需要先手動獲取事件循環然後使用底層方法 loop.create_task() ，而在主入口協程之內是一定有正在運行的循環的。任務創建後便有了狀態，可以查看運行情況，查看結果，取消任務等：
asyncio.create_task() 是 Python3.7 加入的高層級API，在 Python3.6，需要使用低層級API asyncio.ensure_future() 來創建 Future，Future 也是一個管理協程運行狀態的對象，與 Task 沒有本質上的區別。
通常，一個含有一系列並發協程的程序寫法如下（Python3.7+）：
並發運行多個協程任務的關鍵就是 asyncio.gather(*tasks) ，它接受多個協程任務並將它們加入到事件循環，所有任務都運行完成後會返回結果列表，這裡我們也沒有手動封裝 Task，因為 gather 函數會自動封裝。
並發運行還有另一個方法 asyncio.wait(tasks) ，它們的區別是：
python中有哪些簡單的演算法？
你好：
跟你詳細說一下python的常用8大演算法：
1、插入排序
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入演算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。
2、希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
3、冒泡排序
它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
4、快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5、直接選擇排序
基本思想：第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。
6、堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] = A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
7、歸併排序
歸併排序是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。
歸併過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]複製到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]複製到r[k]中，並令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素複製到r中從下標k到下標t的單元。歸併排序的演算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸併操作合併成有序的區間[s,t]。
8、基數排序
基數排序(radix sort)屬於「分配式排序」(distribution sort)，又稱「桶子法」(bucket sort)或bin sort，顧名思義，它是透過鍵值的部分資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/306637.html
微信掃一掃 
支付寶掃一掃 