进程 && 线程

进程:进程是操作系统中执行的一个程序,操作系统以进程为单位分配存储空间,每个进程都有自己的地址空间、数据栈以及其他用于跟踪进程执行的辅助数据,操作系统管理所有进程的执行,为它们合理的分配资源。进程可以通过fork或者wpawn的方式来创建新的进程执行其他任务,不过新的进程有自己独立的内存空间和数据栈,所以必须通过进程间的通信机制(IPC,Inter Process Communication)来实现数据共享,具体的方式包括管道、信号、套接字、共享内存等。

线程:进程的一个执行单元。线程在同一个进程中执行,共享程序的上下文。一个进程中的各个线程与主线程共享同一片数据空间,因而相比与独立的进程,线程间的信息共享和通信更为容易。线程一般是以并发的方式执行的。注意在单核CPU系统中,真正的并发是不可能的,所以新城的执行实际上是这样规划的:每个线程执行一小会,然后让步给其他线程的任务(再次排队等候更多的CPU执行时间)。在整个线程的执行过程中,每个线程执行它自己的特定的任务,在必要时和其他进程进行结果通信。

Python多进程(使用multiprocessing)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from time import time, sleep
from random import randint
from multiprocessing import Process

def my_task(name):
sleep_time = randint(1,10)
sleep(sleep_time)
print("你叫了一声%s,它鸟你用了%d秒" % (name, sleep_time))


def main():
start = time()
process_1 = Process(target=my_task, args=["yeshan", ])
process_2 = Process(target=my_task, args=["foel", ])
# 启动进程
process_1.start()
process_2.start()
# 等待进程执行结束
process_1.join()
process_2.join()
end = time()
print("一共花费了%f秒" % (end-start))


if __name__ == '__main__':
main()

二分查找算法

二分查找的基本思想: 将 n 个元素分成大致相等的两部分,取 a[n/2] 与 x(查找目标值) 做比较,如果x == a[n/2] ,则找到 x,算法中止;否则,如果x < a[n/2],则只要在数组 a 的左半部分继续搜索 x,如果x > a[n/2], 则只要在数组 a 的右半部搜索 x。

使用二分查找算法的前提:待查找序列是有序的

时间复杂度分析

由算法核心思想可知:每次对比都将下一步的比对范围缩小一半。每次比对后剩余数据项如下表:

剩余数据项表

最好情况

即要找的元素正好在初始查找序列的中间一次比较出结果,时间复杂度为 $ O(1) $。

最坏情况

即比对范围只剩下 1 个数据项的情况这个数据项即为正要找的元素。这时,可求解如下方程组($ i $ 为比较次数):

$$ \frac{n}{2^i}=1 $$

时间复杂度为 $ O(log(n)) $

平均时间复杂度

进行平均时间复杂度分析时需要讨论:随着元素个数n的增多,需要几步算法才能终止?查找成功有多少种情况?查找失败有多少种情况?

设 $ n=2^k-1 $, $ k $ 为比较次数。易知,对于 $$ t=1,2,…, \lfloor log(n) \rfloor + 1 $$, 会有 $ 2^{t-1} $ 个元素在 $ t $ 步之后使算法成功终止。总共有 $ (2n+1) $ 种情况,$ n $ 种情况为成功结束,$ (n+1) $ 种情况为失败终止。

由此可得二分搜索的平均比较次数为 $ (k = \lfloor log(n) \rfloor + 1) $:
$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
根据初等数学等差乘等比数列求和的错位相减法/裂项相消法。易知,
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$

使用裂项相消法
由 $ \sum_{i=1}^{k}i2^{i-1} $,设 $ a_i=i2^{i-1},(i=1,…,k) $。注意到,$ a_i=(k-1)2^k-(k-2)2^{k-1} $。
$$ \sum_{i=1}^{k}i2^{i-1}=0\times2^1+1+1\times2^2-0\times2^1+2\times2^3-1\times2^2+…+(k-1)2^k-(k-2)2^{k-1}=2^k(k-1)+1 $$

$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$
综上可得,$$ A(n) = \frac{1}{2n+1}((k-1)2^{k}+1+k2^k) $$

当 $ n $ 非常大时,可得
$$ A(n) \approx \frac{1}{2^{k+1}}((k-1)2^{k}+k2^k)=\frac{(k-1)}{2}+\frac{k}{2}=k-\frac{1}{2} $$
所以 $ A(n)<k=O(log(n)) $ ,平均时间复杂度为$ O(log(n)) $。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# -*- coding: utf-8 -*-
# binary_search

def binary_search(list_1, item):

low = 0
high = len(list_1)-1

while low <= high:
'''使用 // 整除运算符可以不用int进行类型转换'''
#每次都检查中间的元素
mid = (low + high)/2
guess = list_1[int(mid)]

if guess == item:
return int(mid)#返回所在位置的索引
if guess < item: #猜的数字小了,修改low
low = mid+1
if guess > item: #猜的数字大了,修改high
high = mid-1
return None

def main():

list_2 = [1,2,3,4,5,6,7,8,9]

print(binary_search(list_2, 8))
print(binary_search(list_2, 10))

main()

运行效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<typeinfo>
using namespace std;

int binary_search(int a[9],int n,int x)//n为元素个数
{
int mid;
int high,low=0;
int guess;

high = n-1;//数组下标从0开始

while(low <= high)
{
mid = (high+low)/2;
guess = a[mid];
if(guess == x)
return mid;
if(guess > x)
high = mid-1;
if(guess < x)
low = mid+1;
}
return -1;
}

int main()
{
int temp;
int a[9] = {1,2,3,4,5,6,7,8,9};

cout<<sizeof(a)/sizeof(int)<<endl;
cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
temp = binary_search(a,sizeof(a)/sizeof(int),5);
cout<<temp<<endl;

return 0;
}

运行效果

附:C++ 使用头文件typeinfo下的typeid(parameter).name()可获取参数获取类型名

示例

python生成器(generator)

  • 生成器是一种使用普通函数语法定义的迭代器
  • 包含yield语句的函数都是生成器,它是一个不断产生值的函数
  • 生成器每次使用yield产生一个值后,函数都将冻结,即在此处停止执行,等待重新被唤醒。被唤醒后从停止的地方开始继续执行

生成器推导(生成器表达式)

* 使用圆括号()创建一个生成器推导 *,它创建了一个可迭代的对象
使用next()函数可以获得生成器推导的下一个返回值

g = (i**2 for i in range(10))

网络爬虫框架scrapy

(配置型爬虫)

什么是爬虫框架?

  • 爬虫框架是实现爬虫功能的一个软件结构和功能组件集合
  • 爬虫框架是个半成品,帮助用户实现专业网络爬虫

scrapy框架结构(“5+2”结构)

  1. spider:
  • 解析downloader返回的响应(Response)
  • 产生爬取项(scraped item)
  • 产生额外的爬去请求(Request)
    需要用户编写配置代码
  1. engine(引擎):
  • 控制所有模块之间的数据流
  • 根据条件触发事件
    不需要用户修改
  1. scheduler(调度器):
  • 对所有爬取请求进行调度处理
    不需要用户修改
  1. downloader(下载器):
  • 根据请求下载网页
    不需要用户修改
  1. item pipelines():
  • 以流水线处理spider产生的爬取项
  • 由一组操作顺序组成,类似流水线,每个操作是一个Item Pipeline类型
  • 可能操作包括:清理、检验和查重爬取项中的HTML数据,将数据存储到数据库中
    需要用户编写配置代码
  1. downloader middleware(中间件):
  • 目的:实施engine、scheduler和downloader之间进行用户可配置的控制
  • 功能:修改、丢弃、新增请求或响应
    用户可以编写配置代码
  1. spider middleware(中间件):
  • 目的:对请求和爬去项的再处理
  • 功能:修改、丢弃、新增请求或爬取项
    用户可以编写配置代码

数据流

  • 1.Engine从Spider处获得爬取请求(Request)
  • 2.Engine将爬取请求转发给Scheduler,用于调度
  • 3.Engine从Scheduler处获得下一个爬取的请求
  • 4.Engine将爬取请求通过中间件发送给Downloader
  • 5.爬取网页后,Downloader形成响应(Response),通过中间件(Middleware)发给Engine
  • 6.Engine将收到的响应通过中间件发送给Spider处理
  • 7.Spider处理响应后产生爬取项(scraped item)和新的爬取请求(Requests)给Engine
  • 8.Engine将爬取项发送给Item Pipeline(框架出口)
  • 9.Engine将爬取请求发送给Scheduler

  • Engine控制各模块数据流,不间断从Scheduler处获得爬取请求,直到请求为空
  • 框架入口:Spider的初始爬取请求
  • 框架出口:Item Pipeline

scrapy命令行

格式

scrapy <command> [options] [args]

** 常用命令 **

命令 说明 格式
startproject 创建一个新工程 scrapy startproject [dir]
genspider 创建一个爬虫 scrapy genspider [options] [domain]
settings 获得爬虫配置信息 scrapy settings [options]
crawl 运行一个爬虫 scrapy crawl
list 列出工程中所有的爬虫 scrapy list
shell 启动URL调试命令行 scrapy shell [url]

demohttps://python123.io/ws/demo.html

创建工程

scrapy startproject python123demo


创建爬虫

scrapy genspider demo python123.io
//生成了一个名为demo的spider
//在spider目录下增加代码文件demo.py(该文件也可以手工生成)    

** demo.py文件 **

1
2
3
4
5
6
7
8
9
10
11
# -*- coding: utf-8 -*-
import scrapy


class DemoSpider(scrapy.Spider):
name = 'demo'
allowed_domains = ['python123.io']
start_urls = ['http://python123.io/']

def parse(self, response):
pass

配置产生的spider爬虫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding: utf-8 -*-
import scrapy


class DemoSpider(scrapy.Spider):
name = 'demo'
#allowed_domains = ['python123.io']
start_urls = ['http://python123.io/ws/demo.html']

def parse(self, response):
#存储文件名demo.html
file_name = response.url.split('/')[-1]
with open(file_name,"wb") as f:
f.write(response.body)
self.log('Saved file %s' % file_name)#日志

*** 另一个版本 **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
import scrapy


class DemoSpider(scrapy.Spider):
name = 'demo'
#allowed_domains = ['python123.io']
#start_urls = ['http://python123.io/ws/demo.html']
def start_requests(self):
urls = [
'http://python123.io/ws/demo.html'
]
for url in urls:
yield scrapy.Request(url=url, callback=self.parse)

def parse(self, response):
#存储文件名demo.html
file_name = response.url.split('/')[-1]
with open(file_name,"wb") as f:
f.write(response.body)
self.log('Saved file %s' % file_name)#日志

运行爬虫

scrapy crawl demo

Scrapy爬虫数据类型

  • Request类
  • Response类
  • Item类

Request类

class scrapy.http.Request()
  • Request对象表示一个HTTP请求
  • 由Spider生成,由Downloader执行
属性 方法
.url Requests对应的请求URL地址
.method 对应的请求方法,’GEt’、’POST’等
.headers 字典类型风格的请求头
.body 请求内容主体,字符串类型
.meta 用户添加的扩展信息,在Scrapy内部模块间传递信息使用
.copy 复制该请求

Response类

class scrapy.http.Response()
  • Response对象表示一个HTTp响应
  • 由Downloader生成,由Spider处理
属性或方法 说明
.url Response对应的URL地址
.status HTTP状态码,默认是200
.headers Response对应的头部信息
.body Response对应的内容信息,字符串类型
.flags 一组标记
.request 产生Response类型对应的Request对象
.copy() 复制该响应

Item类

class scrapy.item.Item()
  • Item对象表示一个从HTML页面中提取的信息内容
  • 由Spider生成,由Item Pipeline处理
  • Item类似字典类型,可以按照字典类型操作

Scrapy爬虫的使用步骤

  1. 创建一个工程和Spider模板
  2. 编写Spider
  3. 编写Item Pipeline
  4. 优化配置策略

scrapy爬虫信息提取方法

  • Beautifui Soup
  • lxml
  • re
  • XPath Selector
  • CSS Selector