本文目录一览：
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为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
