第十三天 函数编程和正则表达式
今天计划学习Python的高阶函数及函数编程，学习项目及练习源码地址：
GitHub源码
高阶函数
在Python中，函数名其实也是变量，既然变量可以指向函数，函数的参数能接收变量，那么一个函数就可以接收另一个函数作为参数，这种函数就称之为高阶函数。
一个最简单的高阶函数：
def add(x, y, f):
return f(x) + f(y)
add(5,6,abs)# abs是系统自带的函数
常用内置高阶函数介绍
-
map()
map()函数接收两个参数，一个是函数，一个是Iterable(可迭代的，如：序列)，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterator返回。
举例说明，比如我们有一个函数f(x)=x*x，要把这个函数作用在一个list [1, 2, 3, 4, 5, 6, 7, 8, 9]上，就可以用map()实现如下:
def fn(x): return x**2 res = map(fn,[1,2,3,4,5]) print(list(res))map()传入的第一个参数是fn，即函数对象本身。由于结果res是一个Iterator，Iterator是惰性序列，因此通过list()函数让它把整个序列都计算出来并返回一个list。
所以，map()作为高阶函数，事实上它把运算规则抽象了，因此，我们不但可以计算简单的f(x)=x2，还可以计算任意复杂的函数，比如，把这个list所有数字转为字符串：
a = [1,2,3,4,5] b = list(map(str,a)) #['1','2','3','4','5'] -
reduce()
reduce把一个函数作用在一个序列[x1, x2, x3, ...]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算，其效果就是:
reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)举例一个序列求和：
from functools import reduce def fn(x,y): return x+y res = reduce(fn,[1,2,3,4,5]) print(res) # 1+2+3+4+5的值 和sum()一样 -
filter()
和map()类似，filter()也接收一个函数和一个序列。和map()不同的是，filter()把传入的函数依次作用于每个元素，然后根据返回值是True还是False决定保留还是丢弃该元素。
在一个list中，删掉偶数，只保留奇数，可以这么写:def is_odd(n): return n % 2 == 1 list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15])) # 结果: [1, 5, 9, 15]注意到filter()函数返回的是一个Iterator，也就是一个惰性序列，所以要强迫filter()完成计算结果，需要用list()函数获得所有结果并返回list。
-
sorted()
排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序，排序的核心是比较两个元素的大小。如果是数字，我们可以直接比较，但如果是字符串或者两个dict呢？直接比较数学上的大小是没有意义的，因此，比较的过程必须通过函数抽象出来。Python内置的sorted()函数就可以对list进行排序：
sorted([36, 5, -12, 9, -21]) # [-21, -12, 5, 9, 36]此外，sorted()函数也是一个高阶函数，它还可以接收一个key函数来实现自定义的排序，例如按绝对值大小排序:
sorted([36, 5, -12, 9, -21], key=abs) # [5, 9, -12, -21, 36]默认情况下，对字符串排序，是按照ASCII的大小比较的，由于'Z' < 'a'，结果，大写字母Z会排在小写字母a的前面。
要进行反向排序，不必改动key函数，可以传入第三个参数reverse=True'
小结
从上述例子可以看出，高阶函数的抽象能力是非常强大的，而且，核心代码可以保持得非常简洁。
函数作为返回值
高阶函数除了可以接受函数作为参数外，还可以把函数作为结果值返回。
def lazy_sum(*args): def sum(): ax = 0 for n in args: ax = ax + n return ax return sum f = lazy_sum(1, 3, 5, 7, 9) f() f1 = lazy_sum(1, 3) f2 = lazy_sum(1, 3) f1 == f2 # False 每次调用都是返回的一个新函数 -
闭包
相关参数和变量都保存在返回的函数中，这种称为“闭包（Closure）”的程序结构拥有极大的威力。
返回闭包时牢记一点：返回函数不要引用任何循环变量，或者后续会发生变化的变量。
如果一定要引用循环变量怎么办？方法是再创建一个函数，用该函数的参数绑定循环变量当前的值，无论该循环变量后续如何更改，已绑定到函数参数的值不变：def count(): def f(j): def g(): return j*j return g fs = [] for i in range(1, 4): fs.append(f(i)) # f(i)立刻被执行，因此i的当前值被传入f() return fs缺点是代码较长，可利用lambda函数缩短代码。
匿名函数
就是lambda函数
装饰器
由于函数也是一个对象，而且函数对象可以被赋值给变量，所以，通过变量也能调用该函数。
函数对象有一个name属性，可以拿到函数的名字：now.__name__。在代码运行期间动态增加功能的方式，称之为“装饰器”（Decorator）。本质上，decorator就是一个返回函数的高阶函数。所以，我们要定义一个能打印日志的decorator，可以定义如下：
def log(func): def wrapper(*args, **kw): print('call %s():' % func.__name__) return func(*args, **kw) return wrapper @log def now(): print('Now time is 00:00')观察上面的log，因为它是一个decorator，所以接受一个函数作为参数，并返回一个函数。借助Python的@语法，把decorator置于函数now()的定义处.
如果decorator本身需要传入参数，那就需要编写一个返回decorator的高阶函数，写出来会更复杂。比如，要自定义log的文本：
def log(text): def decorator(func): def wrapper(*args, **kw): print('%s %s():' % (text, func.__name__)) return func(*args, **kw) return wrapper return decorator @log("debug") def now(): print('Now time is 00:00')
在面向对象（OOP）的设计模式中，decorator被称为装饰模式。OOP的装饰模式需要通过继承和组合来实现，而Python除了能支持OOP的decorator外，直接从语法层次支持decorator。Python的decorator可以用函数实现，也可以用类实现。
decorator可以增强函数的功能，定义起来虽然有点复杂，但使用起来非常灵活和方便。
再次强调arg与*kwargs参数的用法
在python中，当*和**符号出现在函数定义的参数中时，表示任意数目参数收集。*arg表示任意多个无名参数，类型为tuple;**kwargs表示关键字参数，为dict，使用时需将*arg放在**kwargs之前，否则会有“SyntaxError: non-keyword arg after keyword arg”的语法错误.
- *允许你传入0个或任意个参数，这些可变参数在函数调用时自动组装为一个tuple。
- **关键字参数允许你传入0个或任意个含参数名的参数,这些关键字参数在函数内部自动组装为一个dict。
- 在函数混合使用以及*，命名参数进入**, 其他进入*
上面是在函数定义的时候写的*和**形式，那反过来，如果*和**语法出现在函数调用中又会如何呢？
他会解包参数的集合。例如，我们在调用函数时能够使用*语法，在这种情况下，它与函数定义的意思相反，他会解包参数的集合，而不是创建参数的集合。
#通过一个元组给一个函数传递四个参数，并且让python将它们解包成不同的参数。
def func(a,b,c,d):
print(a,b,c,d)
a = (1,2,3,4)
func(*a)
# 如果已经有一个元祖，在参数前加*，函数会把元祖中的元素一个一个传到函数里面
def calc(*numbers):
sum = 0
for n in numbers:
sum = sum + n * n
print(sum)
num = (1,2,3,4)
calc(*num)
#如果已经有一个dict,在参数前面加**，函数会把dict中所有键值对转换为关键字参数传进去
def person(name,age,**kw):
print('name:',name,'age:',age,'other:',kw)
extra = {'city': 'Beijing', 'job': 'Engineer'}
person('Jack', 24, **extra)
知识点：
在函数调用时，*会以单个元素的形式解包一个元祖，使其成为独立的参数。
在函数调用时，**会以键/值对的形式解包一个字典，使其成为独立的关键字参数。
偏函数
Python的functools模块提供了很多有用的功能，其中一个就是偏函数（Partial function）。要注意，这里的偏函数和数学意义上的偏函数不一样。
在介绍函数参数的时候，我们讲到，通过设定参数的默认值，可以降低函数调用的难度。而偏函数也可以做到这一点。举例如下：
int()函数可以把字符串转换为整数，当仅传入字符串时，int()函数默认按十进制转换：
int('12345')
但int()函数还提供额外的base参数，默认值为10。如果传入base参数，就可以做N进制的转换：
int('12345', base=8)
int('12345', 16)
假设要转换大量的二进制字符串，每次都传入int(x, base=2)非常麻烦，于是，我们想到，可以定义一个int2()的函数，默认把base=2传进去：
def int2(x, base=2):
return int(x, base)
int2(111)
functools.partial就是帮助我们创建一个偏函数的，不需要我们自己定义int2()，可以直接使用下面的代码创建一个新的函数int2：
import functools
int2 = functools.partial(int, base=2)
int2('1000000')
int2('1010101'
简单总结functools.partial的作用就是，把一个函数的某些参数给固定住（也就是设置默认值），返回一个新的函数，调用这个新函数会更简单。
正则表达式
这个不得不说下，因为使用的时候太多了。
正则表达式是一种用来匹配字符串的强有力的武器。它的设计思想是用一种描述性的语言来给字符串定义一个规则，凡是符合规则的字符串，我们就认为它“匹配”了，否则，该字符串就是不合法的。
re模块
Python提供re模块，包含所有正则表达式的功能。
s = 'ABC\\-001' # Python的字符串
# 对应的正则表达式字符串变成：
# 'ABC\-001'
因此我们强烈建议使用Python的r前缀，就不用考虑转义的问题了：
s = r'ABC\-001' # Python的字符串
# 对应的正则表达式字符串不变：
# 'ABC\-001'
如何判断正则表达式是否匹配：
import re
re.match(r'^\d{3}\-\d{3,8}$', '010-12345')
re.match(r'^\d{3}\-\d{3,8}$', '010 12345')
match()方法判断是否匹配，如果匹配成功，返回一个Match对象，否则返回None。常见的判断方法就是：
test = '用户输入的字符串'
if re.match(r'正则表达式', test):
print('ok')
else:
print('failed')
切分字符串
re.split(r'\s+', 'a b c')
分组
除了简单地判断是否匹配之外，正则表达式还有提取子串的强大功能。用()表示的就是要提取的分组（Group）。
^(\d{3})-(\d{3,8})$分别定义了两个组，可以直接从匹配的字符串中提取出区号和本地号码：
m = re.match(r'^(\d{3})-(\d{3,8})$', '010-12345')
m.group(0)
m.group(1)
m.group(2)
编译
当我们在Python中使用正则表达式时，re模块内部会干两件事情：
编译正则表达式，如果正则表达式的字符串本身不合法，会报错；
用编译后的正则表达式去匹配字符串。
如果一个正则表达式要重复使用几千次，出于效率的考虑，我们可以预编译该正则表达式，接下来重复使用时就不需要编译这个步骤了，直接匹配：
import re
re_telephone = re.compile(r'^(\d{3})-(\d{3,8})$') # 编译
re_telephone.match('010-12345').groups() #('010','12345')
re_telephone.match('010-8086').groups()
Python的web编程
WSGI接口
最简单的Web应用就是先把HTML用文件保存好，用一个现成的HTTP服务器软件，接收用户请求，从文件中读取HTML，返回。Apache、Nginx、Lighttpd等这些常见的静态服务器就是干这件事情的。
如果要动态生成HTML，就需要把上述步骤自己来实现。不过，接受HTTP请求、解析HTTP请求、发送HTTP响应都是苦力活，如果我们自己来写这些底层代码，还没开始写动态HTML呢，就得花个把月去读HTTP规范。
正确的做法是底层代码由专门的服务器软件实现，我们用Python专注于生成HTML文档。因为我们不希望接触到TCP连接、HTTP原始请求和响应格式，所以，需要一个统一的接口，让我们专心用Python编写Web业务。
这个接口就是WSGI：Web Server Gateway Interface。
def application(environ, start_response):
start_response('200 OK', [('Content-Type', 'text/html')])
return [b'<h1>Hello, web!</h1>']
上面的application()函数就是符合WSGI标准的一个HTTP处理函数，它接收两个参数：
- environ：一个包含所有HTTP请求信息的dict对象；
- start_response：一个发送HTTP响应的函数。
在application()函数中，调用：
start_response('200 OK', [('Content-Type', 'text/html')])
就发送了HTTP响应的Header，注意Header只能发送一次，也就是只能调用一次start_response()函数。start_response()函数接收两个参数，一个是HTTP响应码，一个是一组list表示的HTTP Header，每个Header用一个包含两个str的tuple表示。
通常情况下，都应该把Content-Type头发送给浏览器。其他很多常用的HTTP Header也应该发送。
然后，函数的返回值b'<h1>Hello, web!</h1>'将作为HTTP响应的Body发送给浏览器。
有了WSGI，我们关心的就是如何从environ这个dict对象拿到HTTP请求信息，然后构造HTML，通过start_response()发送Header，最后返回Body。
整个application()函数本身没有涉及到任何解析HTTP的部分，也就是说，底层代码不需要我们自己编写，我们只负责在更高层次上考虑如何响应请求就可以了。
不过，等等，这个application()函数怎么调用？如果我们自己调用，两个参数environ和start_response我们没法提供，返回的bytes也没法发给浏览器。
所以application()函数必须由WSGI服务器来调用。有很多符合WSGI规范的服务器，我们可以挑选一个来用。但是现在，我们只想尽快测试一下我们编写的application()函数真的可以把HTML输出到浏览器，所以，要赶紧找一个最简单的WSGI服务器，把我们的Web应用程序跑起来。
好消息是Python内置了一个WSGI服务器，这个模块叫wsgiref，它是用纯Python编写的WSGI服务器的参考实现。所谓“参考实现”是指该实现完全符合WSGI标准，但是不考虑任何运行效率，仅供开发和测试使用。
运行WSGI服务
我们先编写hello.py，实现Web应用程序的WSGI处理函数：
# hello.py
def application(environ, start_response):
start_response('200 OK', [('Content-Type', 'text/html')])
return [b'<h1>Hello, web!</h1>']
然后，再编写一个server.py，负责启动WSGI服务器，加载application()函数：
# server.py
# 从wsgiref模块导入:
from wsgiref.simple_server import make_server
# 导入我们自己编写的application函数:
from hello import application
# 创建一个服务器，IP地址为空，端口是8000，处理函数是application:
httpd = make_server('', 8000, application)
print('Serving HTTP on port 8000...')
# 开始监听HTTP请求:
httpd.serve_forever()
确保以上两个文件在同一个目录下，然后在命令行输入python server.py来启动WSGI服务器：
wsgiref-start
注意：如果8000端口已被其他程序占用，启动将失败，请修改成其他端口。
启动成功后，打开浏览器，输入http://localhost:8000/，就可以看到结果了：
hello-web
在命令行可以看到wsgiref打印的log信息：
wsgiref-log
按Ctrl+C终止服务器。
如果你觉得这个Web应用太简单了，可以稍微改造一下，从environ里读取PATH_INFO，这样可以显示更加动态的内容：
# hello.py
def application(environ, start_response):
start_response('200 OK', [('Content-Type', 'text/html')])
body = '<h1>Hello, %s!</h1>' % (environ['PATH_INFO'][1:] or 'web')
return [body.encode('utf-8')]
你可以在地址栏输入用户名作为URL的一部分，将返回Hello, xxx!：
小结
无论多么复杂的Web应用程序，入口都是一个WSGI处理函数。HTTP请求的所有输入信息都可以通过environ获得，HTTP响应的输出都可以通过start_response()加上函数返回值作为Body。
复杂的Web应用程序，光靠一个WSGI函数来处理还是太底层了，我们需要在WSGI之上再抽象出Web框架，进一步简化Web开发。
Web框架
因为WSGI提供的接口虽然比HTTP接口高级了不少，但和Web App的处理逻辑比，还是比较低级，我们需要在WSGI接口之上能进一步抽象，让我们专注于用一个函数处理一个URL，至于URL到函数的映射，就需要交给Web框架来做。
Python开发一个Web框架十分容易，所以Python有上百个开源的Web框架。
常见的web框架有：
Flask:
Django：全能型Web框架；
web.py：一个小巧的Web框架；
Bottle：和Flask类似的Web框架；
Tornado：Facebook的开源异步Web框架。
使用模板
Web框架把我们从WSGI中拯救出来了。现在，我们只需要不断地编写函数，带上URL，就可以继续Web App的开发了。
但是，Web App不仅仅是处理逻辑，展示给用户的页面也非常重要。在函数中返回一个包含HTML的字符串，简单的页面还可以，但是，想想新浪首页的6000多行的HTML，你确信能在Python的字符串中正确地写出来么？反正我是做不到。
俗话说得好，不懂前端的Python工程师不是好的产品经理。有Web开发经验的同学都明白，Web App最复杂的部分就在HTML页面。HTML不仅要正确，还要通过CSS美化，再加上复杂的JavaScript脚本来实现各种交互和动画效果。总之，生成HTML页面的难度很大。
由于在Python代码里拼字符串是不现实的，所以，模板技术出现了。
使用模板，我们需要预先准备一个HTML文档，这个HTML文档不是普通的HTML，而是嵌入了一些变量和指令，然后，根据我们传入的数据，替换后，得到最终的HTML，发送给用户。
至此整个从框架到模板就是MVC：Model-View-Controller，中文名“模型-视图-控制器”。
Python处理URL的函数就是C：Controller，Controller负责业务逻辑，比如检查用户名是否存在，取出用户信息等等；
包含变量{{ name }}的模板就是V：View，View负责显示逻辑，通过简单地替换一些变量，View最终输出的就是用户看到的HTML。
MVC中的Model在哪？Model是用来传给View的，这样View在替换变量的时候，就可以从Model中取出相应的数据。
Python 常用模板处理工具有：
Jinja2：
Mako：用<% ... %>和${xxx}的一个模板；
Cheetah：也是用<% ... %>和${xxx}的一个模板；
Django：Django是一站式框架，内置一个用{% ... %}和{{ xxx }}的模板。
用Python做一些算法和数据结构的练习
算法
算法的五大特征：
(1) 输入性:有零个或多个外部量作为算法的输入
(2) 输出性: 算法至少有一个量作为输出
(3) 确定性:算法中每条指令清晰，无歧义
(4) 有穷性:算法中每条指令的执行次数有限，执行每条指令时间也有限
(5) 可行性:算法原则上能够精确的运行，而且人们用纸和笔做有限次运算后即可
完成
算法有时间复杂度和空间复杂度
时间复杂度的大小关系：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
