Apers' Blog

茶亦醉人何必酒,书能香我不须花

0%

算法精粹(一)

发表于 分类于 阅读次数： Valine：
本文字数： 3.5k 阅读时长 ≈ 3 分钟

算法精粹第一章的几个小问题，挺有意思的，写一写纪录一下。(迭代器、生成器、装饰器、元组解包、字符串直接对比、sum原理)

斐波那契数列

其数列是0,1,1,2,3,5,8,13….模样，除了前两个数字，后面的数字都是其前两个之和，即a(n)=a(n-1)+a(n-2).此种方程式显然可以用递归求解，那么如下看最初始的递归实现.

初始版递归求解：

如下，递归会不断的调用自身，直至达到基线条件(a0和a1)，但是递归的算法复杂度特别高，调用自身的次数近似和2^n呈正相关，输入0/1的时候只调用1次，2的时候调用1+2,3的时候调用1+2+2次，4的时候9次….用树状图可以不断的通过节点来表示，可以看出复杂度异常的高。

1
2
3
4
5
def Fibonacci(n:int)->int:
    if n<2 :
        return n
    return Fibonacci(n-1)+Fibonacci(n-2)
Fibonacci(20)

注:这里说一下n:int和->是什么意思，由于python中定义变量的时候是不需要指定类型的，所以可能会对别人造成勿扰，所以这里的n:int 代表n是int类型的，如a:int = 3，这一句其实是等价于a=3,int是告诉别这是int型。->代表函数返回值类型。值得注意的是，这种指定类型的方式没有强制性作用，a：int=3时候，解释器运行时，会自动把:int优化掉，->同理，所以其存在意义仅仅是加大代码可读性，你若不按规矩来，别人也没办法，比如a:int = “sagjsa”,完全可以，注意,冒号后和->是需要合法的数据类型，对于一些复杂的类型，python提供了typing包，举例如下，如下tup和lis就类似于int一样是一种数据类型了，如果不写前三行，那么a:lis=[(0,0,0)]会报错。

1
2
3
4
from typing import Tuple,List
tup=Tuple[int,int,int]
lis=List[tup]
a:lis = [(0,0,0)]

递归求解+结果缓存

当n为5的时候，树状图如下，我们知道加法运算，会从左往右算的，所以第一个递归完成的必然是如下图粉色笔圈出的函数块，其实观察一下就可以知道，这个粉色块已经计算出了整个树状图需要的所有结果，由于局部函数的数据是在栈中(先入后出)，所以会被系统自动释放，无法保存，所以这个树状图进行了很多很多的重复运算，如果加入一个全局堆区数据，保存下这些结果，用到时候直接读出，那么这样就会大大降低算法复杂度。

TeucgH.md.jpg

设计如下，就是定义了一个memo来存储计算得到的结果，就是为了重复利用这些值。

1
2
3
4
5
6
7
from typing import Dict
memo:Dict[int,int] = {0:0,1:1}
def Fibonacci2(n:int)->int:
    if n not in memo:
        memo[n]=Fibonacci2(n-1)+Fibonacci2(n-2)
    return memo[n]
Fibonacci2(50)

注：n in memo,这个式子是判断n是否是memo的key的，即键值，而不是用于判断value的。在python中，几乎所有的合法数据类型，都可以进行简单的in，==，>,<等，比如“abc”<”cds”就是True，其会自动从第一个开始比较，若相当则比较第二个，比如”abc”<”aac”就是False，之所以可以这样感觉<这个符号底层也是用了python的特色：迭代器，从第一个开始比较一直到最后一个，和for似的，不知道什么时候停止，反正next取不到值了，raiseerror就退出，而sum的本质也是在用迭代器，所以输入的数据不需要是完整的数据，完全可以只输入一个迭代器or生成器

递归求解+自动化结果缓存

上面的加入缓存后，极大的减少了运算复杂度，但还可以进一步简化，Python中自带了一个内置的装饰器(decorator),可以自动为如何函数缓存结果，如下，@functools.lru_caches()就是会把函数的返回值缓存起来，和上面的memo作用一致，当遇到相同的输入参数时，就可以直接用缓存中的数据。

代码如下：

1
2
3
4
5
6
7
from functools import lru_cache
@lru_cache(maxsize=None)
def Fibonacci2(n:int)->int:
    if n < 2:
        return n
    return Fibonacci2(n-1)+Fibonacci2(n-2)
Fibonacci2(50)

迭代求解

递归求解本质是反向进行，然后得到结果，然而除了反向求解，我们还可以正向求解，即迭代，只要是递归可以解决的问题，迭代也都可以解决。此处迭代求解复杂度比前面的几种方法都要低。

代码如下，就是从两个值推出下一步需要的两个值

1
2
3
4
5
6
7
8
9
def Fibonacci2(n:int)->int:
    if n == 0:
        return n
    last_data = 0
    next_data = 1
    for i in range(1,n):
        last_data,next_data=next_data,last_data+next_data
    return next_data
Fibonacci2(50)

注：这里用到了元组解包的操作，就是last_data,next_data=next_data,last_data+next_data这个赋值，一般来说，需要交换数据时候，往往需要引入中间变量，但是元组解包作为一个整体，可以在功能上展示出类似于verilog一样的并行结构，就是相当于last_data=next_data和next_data=last_data+next_data是并行完成的，所以不需要人为引入中间变量了，这样操作相当便利，十分常用。

生成器求解

首先介绍一下生成器的概念，看如下链接，讲的十分简洁明了。

(31条消息) python中yield的用法详解——最简单，最清晰的解释

所以说通过yield代替return就可以把函数变成一个生成器，生成器的本质还是迭代器，用next取值，仔细向来，现在pytorch中很多封装的读取batch数据的函数返回的一般都是生成器or迭代器or可迭代对象，这样的好处就是节约内存，而for中平时用的特别多的range也可以理解为一个迭代器/生成器。之前用过for循环实现列表生成式，其实还可以实现生成器，因为for本质也用到迭代器，如下:(i for i in range(10))就会得到一个生成器，sum的本质用的也是生成器进行累和的所以完全可以送一个生成器进去然后进行累和，可以节约内存，如下，两句，第一句在小内存的电脑上就容易卡死，而第二句就不会。

1
2
sum([i for i in xrange(10000000000)])
sum(i for i in xrange(10000000000))

也正是依赖于迭代器和生成器这一类巧妙的方式，可以使得文件打开+for可以很好的读取文本，但值得注意的是yield和return有所区别，yield一旦执行完毕了，就再也不会输出结果了。

1
2
3
4
5
6
7
8
def read(filename):
	with open(filename) as f:
		for line in f:
			yield int(line)
file=read("hhh.txt")
sum_file = sum(file)
for i in file:
    print(i)

如上代码，传给sum一个生成器，sum求和本质是next，所以会遍历完yield，没有下一个yield了，所以下面的for i in file不会有任何输出，所以需要注意，生成器只会遍历完一次就停止。

回到正题，此处的斐波那契数列代码编写如下，结合for自动使用next，可以得到每一步的斐波那契数列结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import Generator
def Fibonacci2(n:int)->int:
    yield 0
    if n > 0:
        yield 1
    last_data = 0
    next_data = 1
    for i in range(1,n):
        last_data,next_data=next_data,last_data+next_data
        yield next_data
if __name__ == "__main__":
    for i in Fibonacci2(50):
        print(i)
- - - - - - - - - - - - - - 本文结束啦，感谢您的观看 - - - - - - - - - - - - - -