python数据结构教程 Day2
本节重点
- 抽象、接口、实现
- ADT
- 评价算法的指标
- python原始数据类型的性能
一、抽象、实现
1、概念：
从“ 逻辑Logical ” 或者“ 物理Physical”的不同层次上看待问题及解决方案。抽象取决于你所处于的级别，在调用math.sqrt(16)时，这是典型的过程抽象，是不关心sqrt函数内部操作的，sqrt函数的源码构成了具体对求平方根功能的实现。
2、举例解释：
对于一辆汽车：
从司机观点看来，汽车是一台可以带人去往目的地的代步工具。
对于抽象角度：司机看到汽车的“逻辑”层次，司机可以通过操作各个机构来达到运输的目的。
这些操纵机构（方向盘、油门、档位）就称为“接口 Interface”。
从汽车修理工的角度来看同一辆汽车，就会相当不同，他还需要清楚每项功能是如何实现的。如发动机工作原理，档位操作的机械结构，发动机舱内各 处温度如何测量和控制等等。这些内部构造构成了汽车的“ 物理 ”层次。内部构造的工作过程就称为“实现Implementation”
3、总结
一句话：抽象不关心实现，直接使用接口调用实现
二、ADT
定义：
Abstract Data Type：抽象数据类型，是对数据进行处理的一种逻辑描述，并不涉及如何实 现这些处理。
其建立了对数据的封装：封装技术将可能的处理实现细节隐蔽起来 能有效控制算法的复杂度。
ADT工作过程
具体实现：
同一个ADT可以采用不同的数据结构类实现：
比如实现树结构：可以通过嵌套列表，也可以通过其他方式实现。重点是要采用程序设计语言的控制结构和基本数据 类型来实现ADT所提供的逻辑接口。比如对于BST（二叉搜索树）来说，重要的是实现树节点的插入、删除、等操作，这是前面所讲的物理层次。
总的来说，ADT对数据实现“逻辑”层次和“物理”层次的分离，可以定义复杂的数据模型来解决问题，而不需要立即考虑此模型如何实现。这里的数据模型，让底层开发程序员专注于实现和优化数据处理， 又不改变数据的使用接口，让用户专注于用数据接口来进行问题的解决，而无需考虑如何具体实现这些接口。
ADT就是一个层层抽象的过程，来降低问题的复杂度。还不清楚ADT没有关系，后续具体数据模型介绍的过程中，都会采用ADT的形式，熟悉了就明确了。
三、算法评判标准
时间复杂度、空间复杂度，一般采用big O notation来衡量这两个指标的数量级。
时间复杂度：衡量算法的执行时间。
空间复杂度：衡量算法解决需要的存储空间。
计算资源 = 时间+空间
我们的理想情况是：二者都向尽量小的方向进行优化。
举例分析：
变位词问题：所谓“变位词”是指两个词之间存在组成字母的重新排列关系，如：heart和earth，python和typhon 为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等。
解题目标：写一个bool函数，以两个词作 为参数，返回这两个词是否变位词。
解法一：
将两个字符串都按照字母顺序排好序 再逐个字符对比是否相同，如果相同则是变位词 有任何不同就不是变位词。
def isChangePositionWords(s1,s2):
alist1 = list(s1).sort()
alist2 = list(s2).sort()
index = 0
isMatch = True
while index < len(s1) and isMatch:
if alist1[index] == alist2[index]:
index += 1
else:
isMatch = False
return matches
这里的时间复杂度为排序算法的时间复杂度，因为相比于单个循环的O(n)来说，排序算法的时间开销会大一些，python中列表的sort方法采用的是快速排序的实现，所以数量级为O(nlogn)。
能不能向O(n)进行优化？
解法二：
对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同的 话，这两个字符串就一定是变位词。为每个词设置一个26位的计数器列表，先检查每个词，在计数器中设定好每个字母出现的次数。
def isChangePositionWords(s1,s2):
count1 = [0]*26
count2 = [0]*26
for i in range(len(s1)):
pos = ord(s1[i]) - ord('a')
count1[pos] += 1
for i in range(len(s2)):
pos = ord(s2[i]) - ord('a')
count2[pos] += 1
index = 0
isMatch = True
while index < 26 and isMatch:
if count1[index] == count2[index]:
index += 1
else:
isMatch = False
return matches
算法存在三个并列的循环，时间复杂度最长的一个是O(n)，同时count1和count2是额外使用的空间，空间复杂度为O(n)。这里牺牲存储空间来换取运行时间，或者相反 ，这种在时间空间之间的取舍和权衡，在 选择问题解法的过程中经常会出现。
四、python原始数据类型的性能
讨论列表、字典上各个操作的大O数量级。
| 类型 | list | dict |
|---|---|---|
| 索引 | 下标 | key |
| 添加 | append、extend、insert | d[key] = value |
| 删除 | pop、remove | pop |
| 修改 | a[index] = value | d[key] = value |
| 正查 | a[i]、a[i:j] | d[key]、copy |
| 反查 | index(value)、count(value) | 无 |
| 其他 | reverse、sort | has_key、update |
各个方法的实现原则：让最常用的操作性能最好 ，牺牲不太常用的操作。(遵循二八定律)
List列表类型
1、索引取值、赋值
由于列表的随机访问特性，这两个操作执行时间 与列表大小无关，均为O(1)
2、列表增长
- lst.append(v)，执行时间是O(1)
- lst= lst+ [v]，执行时间是O(n+k)，其中k是被加的列表长度
（列表能使用公用运算符+号，是因为实现class LIst的时候实现了又一个魔法方法：__ add __()）
3、pop
- pop()从列表末尾移除元素，O(1)
- pop(i)从列表中部移除元素，O(n)
从中部移除元素的话，要把移除元素后面的元素全部向前挪位复制一遍，这个看起来有点笨拙，但这种实现方法能够保证列表按索引取值和赋值 的操作很快，达到O(1)。
4、list基本操作数量级
list基本操作时间复杂度
5、对比dict字典类型
最常用的取值get和赋值set，其性能为O(1)，另一个重要操作contains(in)是判断字典中是否存在某个关键码（key），这个性能也是O(1)。
dict常用操作复杂度
上一篇：python数据结构教程 Day1
下一篇：python数据结构教程 Day3
