python能干的东西有很多，这里不再过多叙述，直接重点干货。
Python算法入门
一、算法概念
1、什么是算法？
一个计算过程，解决问题的方法
2、时间复杂度
用来评估算法运行效率的一个东西
下面是三种常见的时间复杂度代码例子：
def func(): print('hello world')def func1(n): for i in range(n): print('hello world')def func2(n): for i in range(n): for j in range(n): print('hello world')def func3(n): for i in range(n): for j in range(n): for k in range(n): print('hello world')
他们时间复杂度分别为：O(1),O(n),O(n^2),O(n^3)
特殊的时间复杂度
def func4(n): while n >1: print(n) n = n//2
这种的时间复杂度叫O(logn)
小结：时间复杂度是用来估计算法运行时间的一个式子（单位）
一般来说，时间复杂度高的算法比复杂度低的算法慢
常见的时间复杂度（按效率排序）
O(1)<><><><><><>
通常简单的判断时间复杂度的方法：
循环减半的过程------O(logn)
基层循环就是n的几次方的复杂度
3、空间复杂度
用来评估算法内存占用大小的一个式子
二、二分查找
图解：从系列数字中找到3
转换为代码例子如下：
def bin_search(data,val): low = 0 high = len(data)-1 while low<= high:="" mid="(low+high)//2" if="" data[mid]="=" val:="" return="" mid="" elif="" data[mid]="">< val:="" low="mid+1" else:="" high="mid-1">
三、比较LOW的三种排序
冒泡、选择和插入排序
冒泡排序
代码例子如下：
def bubble_sort(li): for i in range(len(li)-1): for j in range(len(li)-i-1): if li[j] > li[j+1]: li[j],li[j+1] = li[j+1],li[j]
冒泡排序的时间复杂度为：O(n^2)
冒泡排序的优化版本：
def bubble_sort(li): for i in range(len(li)-1): exchange = False for j in range(len(li)-i-1): if li[j] > li[j+1]: li[j],li[j+1] = li[j+1],li[j] exchange = True if not exchange: return
这种情况是如果冒泡排序中执行一趟而没有交换，这样列表就是有序的，可以直接结束算法
选择排序
选择排序思路：
一趟遍历记录最小的数放到第一个位置
再遍历记录剩余列表中最小的数，继续放置
。。。。。。
选择排序的代码例子：
def select_sort(li): for i in range(len(li)-1): min_loc = i for j in range(i+1,len(li)): if li[j] < li[min_loc]:="" min_loc="j" li[i],li[min_loc]="">
选择排序的时间复杂度：O(n^2)
插入排序
列表被分为有序区和无序区两个部分。最初的有序区只有一个元素，默认为第一个元素
每次从无序区选择一个元素，插入到有序区的位置，直到无需去没有元素
代码例子：
def insert_sort(li): for i in range(1,len(li)): tmp = li[i] j = i-1 while j>=0 and li[j] > tmp: li[j+1] = li[j] j=j-1 li[j+1] = tmp
插入排序的时间复杂度：O(n^2)
四、快速排序简称快排
快排是好写的排序算法中最快的
快的排序算法里最好写的
快排的思路：
取一个元素p(第一个元素)，使元素归位
列表被p元素分为两部分，左边的都比p小，右边的都比p大
递归完成排序
代码例子如下：
def quick_sort(data,left,right): if left< right:="" while=""> tmp: right -=1 data[left] = data[right] while left< tmp:="" left+="1" data[right]="data[left]" data[left]="tmp" return="">
Python 之线程
常用用法
t.is_alive()
Python中线程会在一个单独的系统级别线程中执行（比如一个POSIX线程或者一个Windows线程）
这些线程将由操作系统来全权管理。线程一旦启动，将独立执行直到目标函数返回。可以通过查询
一个线程对象的状态，看它是否还在执行t.is_alive()
t.join()
可以把一个线程加入到当前线程，并等待它终止
Python 解释器在所有线程都终止后才继续执行代码剩余的部分
daemon
对于需要长时间运行的线程或者需要一直运行的后台任务，可以用后台线程（也称为守护线程）
例：
t = Thread(target = func, args(1,), daemon = True)
t.start()
后台线程无法等待，这些线程会在主线程终止时自动销毁
小结：
后台线程无法等待，不过，这些线程会在主线程终止时自动销毁。你无法结束一个线程，无法给它发送信
号，无法调整它的调度，也无法执行其他高级操作。如果需要这些特性，你需要自己添加。比如说，
如果你需要终止线程，那么这个线程必须通过编程在某个特定点轮询来退出
如果线程执行一些像 I/O 这样的阻塞操作，那么通过轮询来终止线程将使得线程之间的协调变得非常棘手。
比如，如果一个线程一直阻塞在一个 I/O 操作上，它就永远无法返回，也就无法检查自己是否已经被结束了。
要正确处理这些问题，需要利用超时循环来小心操作线程。
线程间通信
queue
一个线程向另外一个线程发送数据最安全的方式应该就是queue库中的队列
先看一下使用例子，这里是一个简单的生产者和消费者模型：
from queue import Queuefrom threading import Threadimport randomimport time_sentinel = object()def producer(out_q): n = 10 while n: time.sleep(1) data = random.randint(0, 10) out_q.put(data) print('生产者生产了数据{0}'.format(data)) n -= 1 out_q.put(_sentinel)def consumer(in_q): while True: data = in_q.get() print('消费者消费了{0}'.format(data)) if data is _sentinel: in_q.put(_sentinel) breakq = Queue()t1 = Thread(target=consumer, args=(q,))t2 = Thread(target=producer, args=(q,))t1.start()t2.start()
上述代码中设置了一个特殊值_sentinel用于当获取到这个值的时候终止执行
关于queue的功能有个需要注意的地方：
Queue对象虽然已经包含了必要的锁，主要有q.put和q.get
而q.size(),q.full(),q.empty()等方法不是线程安全的
使用队列进行线程通信是一个单向、不确定的过程。通常情况下，是没有办法知道接收数据的线程是什么时候接收到的数据并开始工作的。但是队列提供了一些基本的特性：q.task_done()和q.join()
如果一个线程需要在另外一个线程处理完特定的数据任务后立即得到通知，可以把要发送的数据和一个Event放到一起使用
关于线程中的Event
线程有一个非常关键的特性：每个线程都是独立运行的，且状态不可预测
如果程序中的其他线程需要通过判断每个线程的状态来确定自己下一步的操作，这时线程同步问题就会比较麻烦。
解决方法：
使用threading库中的Event
Event对象包含一个可由线程设置的信号标志，它允许线程等待某些事件的发生。
在初始化状态下，event对象中的信号标志被设置为假。
如果有线程等待一个event对象，而这个event的标志为假，这个线程将一直被阻塞知道该标志为真。
一个线程如果把event对象的标志设置为真，就会唤醒所有等待这个event对象的线程。
通过一个代码例子理解：
from threading import Thread, Eventimport timedef countdown(n, started_evt): print('countdown starting') # set将event的标识设置为True started_evt.set() while n > 0: print('T-mins', n) n -= 1 time.sleep(2)# 初始化的started_evt为Falsestarted_evt = Event()print('Launching countdown')t = Thread(target=countdown, args=(10, started_evt,))t.start()# 会一直等待直到event的标志为True的时候started_evt.wait()print('countdown is running')
而结果，我们也可以看出当线程执行了set之后，才打印running

实际用event对象最好是单次使用，创建一个event对象，让某个线程等待这个对象，一旦对象被设置为Tru，就应该丢弃它，我们虽然可以通过clear()方法重置event对象，但是这个没法确保安全的清理event对象并对它进行重新的赋值。会发生错过事件，死锁等各种问题。
event对象的一个重要特点是它被设置为True时会唤醒所有等待它的线程，如果唤醒单个线程的最好用Condition或信号量Semaphore
和event功能类似的线程中还有一个Condition
关于线程中的Condition
关于Condition官网的一段话：
A condition variable is always associated with some kind of lock; this can be passed in or one will be created by default. Passing one in is useful when several condition variables must share the same lock. The lock is part of the condition object: you don’t have to track it separately.
Other methods must be called with the associated lock held. The wait() method releases the lock, and then blocks until another thread awakens it by calling notify() or notify_all(). Once awakened, wait() re-acquires the lock and returns. It is also possible to specify a timeout.
但是需要注意的是：
notify() and notify_all()这两个方法，不会释放锁，这意味着线程或者被唤醒的线程不会立刻执行wait()
我们可以通过Conditon对象实现一个周期定时器的功能，每当定时器超时的时候，其他线程都可以检测到，代码例子如下：
import threadingimport timeclass PeriodicTimer: ''' 这里做了一个定时器 ''' def __init__(self, interval): self._interval = interval self._flag = 0 self._cv = threading.Condition() def start(self): t = threading.Thread(target=self.run) t.daemon = True t.start() def run(self): while True: time.sleep(self._interval) with self._cv: # 这个点还是非常有意思的^= self._flag ^= 1 self._cv.notify_all() def wait_for_tick(self): with self._cv: last_flag = self._flag while last_flag == self._flag: self._cv.wait()# 下面两个分别为两个需要定时执行的任务def countdown(nticks): while nticks > 0: ptimer.wait_for_tick() print('T-minus', nticks) nticks -= 1def countup(last): n = 0 while n < last:="" ptimer.wait_for_tick()="" print('counting',="" n)="" n="" +="1ptimer" =="" periodictimer(5)ptimer.start()threading.thread(target="countdown," args="(10,)).start()threading.Thread(target=countup," args="">
关于线程中锁的使用
要在多线程中安全使用可变对象，需要使用threading库中的Lock对象
先看一个关于锁的基本使用：
import threadingclass SharedCounter: def __init__(self, initial_value=0): self._value = initial_value self._value_lock = threading.Lock() def incr(self,delta = 1): with self._value_lock: self._value += delta def decr(self, delta=1): with self._value_lock: self._value -= delta
Lock对象和with语句块一起使用可以保证互斥执行，这样每次就只有一个线程可以执行with语句包含的代码块。with语句会在这个代码快执行前自动获取锁，在执行结束后自动释放所。
线程的调度本质上是不确定的，因此，在多线程程序中错误的使用锁机制可能会导致随机数据
损坏或者其他异常错误，我们称之为竞争条件
你可能看到有些“老python程序员”
还是通过_value_lock.acquire() 和_value_lock.release()，明显看来
还是with更加方便，不容易出错，毕竟你无法保证那次就忘记释放锁了
为了避免死锁，使用锁机制的程序应该设定每个线程一次只能获取一个锁
threading库中还提供了其他的同步原语：RLock,Semaphore对象。但是这两个使用场景相对来说比较特殊
RLock(可重入锁)可以被同一个线程多次获取，主要用来实现基于检测对象模式的锁定和同步。在使用这种锁的时候，当锁被持有时，只有一个线程可以使用完整的函数或者类中的方法，例子如下：
import threadingclass SharedCounter: _lock = threading.RLock() def __init__(self,initial_value=0): self._value = initial_value def incr(self,delta=1): with SharedCounter._lock: self._value += delta def decr(self,delta=1): with SharedCounter._lock: self.incr(-delta)
这个例子中的锁是一个类变量，也就是所有实例共享的类级锁，这样就保证了一次只有一个线程可以调用这个类的方法。与标准锁不同的是已经持有这个锁的方法再调用同样适用这个锁的方法时，无需再次获取锁，例如上面例子中的decr方法。
这种方法的特点是：无论这个类有多少实例都使用一个锁。因此在需要使用大量使用计数器的情况下内存效率更高。
缺点：在程序中使用大量线程并频繁更新计数器时会有竞争用锁的问题。
信号量对象是一个建立在共享计数器基础上的同步原语，如果计数器不为0,with语句讲计数器减1，
线程被允许执行。with语句执行结束后，计数器加1。如果计数器为0，线程将被阻塞，直到其他线程结束并将计数器加1。但是信号量不推荐使用，增加了复杂性，影响程序性能。
所以信号量更适用于哪些需要在线程之间引入信号或者限制的程序。例如限制一段代码的并发量
from threading import Semaphoreimport requests_fetch_url_sema = Semaphore(5)def fetch_url(url): with _fetch_url_sema: return requests.get(url)
关于防止死锁的加锁机制
在多线程程序中，死锁问题很大一部分是由于多线程同时获取多个锁造成的。
举个例子：一个线程获取一个第一个锁，在获取第二个锁的时候发生阻塞，那么这个线程就可能阻塞其他线程执行，从而导致整个程序假死。
一种解决方法：为程序中每一个锁分配一个唯一的id，然后只允许按照升序规则来使用多个锁。
import threadingfrom contextlib import contextmanager# 存储已经请求锁的信息_local = threading.local()@contextmanagerdef acquire(*locks): # 把锁通过id进行排序 locks = sorted(locks, key=lambda x: id(x)) acquired = getattr(_local, 'acquired', []) if acquired and max(id(lock) for lock in acquired) >= id(locks[0]): raise RuntimeError('Lock order Violation') acquired.extend(locks) _local.acquired = acquired try: for lock in locks: lock.acquire() yield finally: for lock in reversed(locks): lock.release() del acquired[-len(locks):]x_lock = threading.Lock()y_lock = threading.Lock()def thread_1(): while True: with acquire(x_lock,y_lock): print('Thread-1')def thread_2(): while True: with acquire(y_lock,x_lock): print('Thread-2')t1 = threading.Thread(target=thread_1)t1.daemon = Truet1.start()t2 = threading.Thread(target=thread_2)t2.daemon = Truet2.start()
通过排序，不管以什么样的顺序来请求锁，这些锁都会按照固定的顺序被获取。
这里也用了thread.local()来保存请求锁的信息
同样的这个东西也可以用来保存线程的信息，而这个线程对其他的线程是不可见的。
以上是全部代码，只是善于分享，不足之处请包涵！爬虫基本的原理就是，获取源码，进而获取网页内容。一般来说，只要你给一个入口，通过分析，可以找到无限个其他相关的你需要的资源，进而进行爬取。
我也写了很多其他的非常简单的入门级的爬虫详细教程，关注后，点击我的头像，就可以查看到。
欢迎大家一起留言讨论和交流，谢谢！
