Python数据结构与算法（一）列表和元组

拼搏现实的明天。 2022-12-19 03:58 217阅读 0赞

本系列总结了python常用的数据结构和算法，以及一些编程实现。
参考书籍：《数据结构与算法 Python语言实现》 【美】Michael T.Goodrich, Roberto Tamassia, Michael H.Goldwasser
更多文章可以移步楼主个人博客：一个算法工程师的修炼金字塔

文章目录

    • 1 算法分析
      • 1.1 常用的7种函数
      • 1.2 渐进分析
      • 1.3 简单的证明
    • 2 基于数组的序列
      • 2.1 动态数组
        • Python实现动态数组
      • 2.2 python序列类型的效率
        • python的列表和元组类
        • Python的字符串类

1 算法分析

关键词： 渐进分析、归纳、循环不变量

为了进行算法分析，把执行原子操作的数量描述为输入大小 n n n的函数 f ( n ) f(n) f(n)。
由于算法执行的原子操作数 t t t与算法的真实运行时间成正比，因此 f ( n ) f(n) f(n)可以用来比较不同算法的运行时间。

1.1 常用的7种函数

  • 常数函数
    表达式： f ( n ) = c f(n)=c f(n)=c
    最基本的常数函数是 g ( n ) = 1 g(n)=1 g(n)=1，
    任何其它函数都可以被写成常数 c g ( n ) cg(n) cg(n)，即 f ( n ) = c g ( n ) f(n)=cg(n) f(n)=cg(n)
  • 对数函数
    表达式： x = log ⁡ b n x=\log_bn x=logbn
    一般在计算机科学中，对数常见底数为2，此时经常会省略其符号，即：
    log ⁡ n = log ⁡ 2 n \log n = \log_2n logn=log2n
  • 线性函数
    表达式： f ( n ) = n f(n)=n f(n)=n
  • n log ⁡ n n\log n nlogn函数
    表达式： f ( n ) = n log ⁡ n f(n)=n\log n f(n)=nlogn
  • 二次函数
    表达式： f ( n ) = n 2 f(n)=n^2 f(n)=n2
    二次函数可能出现在嵌套循环中，如每次循环操作数加1，则总操作数：
    1 + 2 + 3 + . . . + ( n − 1 ) + n = n ( n + 1 ) 2 1+2+3+…+(n-1)+n = \frac{n(n+1)}{2} 1+2+3+…+(n−1)+n=2n(n+1)
  • 三次函数和其它多项式
    表达式： f ( n ) = n 3 f(n)=n^3 f(n)=n3
  • 指数函数
    表达式： f ( n ) = b n f(n)=b^n f(n)=bn
    指数函数与几何求和
    假如有一个循环，每次迭代需要一个比前一个更长时间的乘法因子。则总操作数可表示为：
    ∑ i = 0 n a i = 1 + a + a 2 + . . . + a n = a n + 1 − 1 a − 1 , n > = 0 , a > 0 , a ! = 1 \sum_{i=0}^n a^i=1+a+a^2+…+a^n=\frac{a^{n+1}-1}{a-1}, n>=0,a>0,a!=1 i=0∑nai=1+a+a2+…+an=a−1an+1−1,n>=0,a>0,a!=1

1.2 渐进分析

  • 大 O O O符号
    令 f ( n ) f(n) f(n)和 g ( n ) g(n) g(n)作为正实数映射正整数的函数。如果有实型常量 c > 0 c>0 c>0和整型常量 n 0 > = 1 n_0>=1 n0>=1满足 f ( n ) < = c g ( n ) , n > = n 0 f(n)<=cg(n),n>=n_0 f(n)<=cg(n),n>=n0我们就说 f ( n ) f(n) f(n)是 O ( g ( n ) ) O(g(n)) O(g(n))。
    例如：
    函数 8 n + 5 8n+5 8n+5 是 O ( n ) O(n) O(n)；函数 3 log ⁡ n + 2 3\log n+2 3logn+2 是 O ( log ⁡ n ) O(\log n) O(logn)等。
  • 大 Ω \Omega Ω符号
    令 f ( n ) f(n) f(n)和 g ( n ) g(n) g(n)作为正实数映射正整数的函数。如果 g ( n ) g(n) g(n)是 O ( f ( n ) ) O(f(n)) O(f(n))，即存在实型常量 c > 0 c>0 c>0和整型常量 n 0 > = 1 n_0>=1 n0>=1满足 f ( n ) > = c g ( n ) , n > = n 0 f(n)>=cg(n),n>=n_0 f(n)>=cg(n),n>=n0我们就说 f ( n ) f(n) f(n)是 Ω ( g ( n ) ) \Omega(g(n)) Ω(g(n))。
  • 大 Θ \Theta Θ符号
    如果 f ( n ) f(n) f(n)是 O ( g ( n ) ) O(g(n)) O(g(n))，且 f ( n ) f(n) f(n)是 Ω ( g ( n ) ) \Omega(g(n)) Ω(g(n))，即存在实型常数 c ′ > 0 、 c ′ ′ > 0 c’>0、c^{\prime\prime}>0 c′>0、c′′>0和整型常量 n 0 > = 1 n_0>=1 n0>=1满足 c ′ g ( n ) < = f ( n ) < = c ′ ′ g ( n ) , n > = n 0 c’g(n)<=f(n)<=c^{\prime\prime}g(n),n>=n_0 c′g(n)<=f(n)<=c′′g(n),n>=n0我们就说 f ( n ) f(n) f(n)是 Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))。

1.3 简单的证明

  • 反证
    为了证明命题“如果 p p p为真，那么 q q q为真”，我们使用其逆否命题命题“如果 q q q非真，那么 p p p非真”来代替。
    另一个反证法是通过矛盾来证明。即建立一个声明 q q q是真的，首先假设 q q q是假的，然后显示出由这个假设导致的矛盾。
  • 归纳
    对于任何特定的 n > = 1 n>=1 n>=1，有一个有限序列的证明，从已知为真的部分开始，最终得出 q ( n ) q(n) q(n)为真的结论。
    具体的说，通过证明当 n = 1 n=1 n=1时， q ( n ) q(n) q(n)为真，然后假设当 n = k n=k n=k时命题成立，以验证的条件和假设的条件作为论证的依据进行推导当 n = k + 1 n=k+1 n=k+1时命题也成立。
  • 循环不变量
    为了证明一些关于循环的语句 L L L是正确的，我们依据一系列较小的语句 L 0 , L 1 , . . . , L k L_0,L_1,…,L_k L0,L1,…,Lk来定义 L L L，其中：
    1）在循环开始之前，最初要求 L 0 L_0 L0为真。
    2）如果在迭代 j j j之前 L j − 1 L_{j-1} Lj−1为真，那么在迭代 j j j之后 L j L_j Lj也会为真。
    3）最后的语句 L k L_k Lk意味着要证明的语句 L L L为真。
    举例见书籍p91。

2 基于数组的序列

关键词： 引用数组、动态数组、元组

Python使用数组内部存储机制，即对象引用来表示序列或元组实例。
Python数组存储的是对象的地址，通过这种方式Python可以以常量时间访问元素列表或元组。

2.1 动态数组

本节主要介绍动态数组的原理和实现。
Python列表的大小没有限制，其依赖于动态数组。
简单理解动态数组就是，当数组元素到达当前数组的长度时，增加一个更大的数组并初始化，使其前面部分与之前数组一样，原来数组将被回收。
下面的代码可以用来探究列表长度和底层大小关系：

  1. import sys
  2. data = []
  3. for k in range(n):
  4.     a = len(data)
  5.     b = sys.getsizeof(data)
  6.     print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a,b))
  7.     data.append(None)
  9. # 样例输出
  10. Length: 0; Size in bytes: 72
  11. Length: 1; Size in bytes: 104
  12. Length: 2; Size in bytes: 104
  13. Length: 3; Size in bytes: 104
  14. Length: 4; Size in bytes: 104
  15. Length: 5; Size in bytes: 136
  16. Length: 6; Size in bytes: 136
  17. Length: 7; Size in bytes: 136
  18. Length: 8; Size in bytes: 136
  19. Length: 9; Size in bytes: 136
  20. Length: 10; Size in bytes: 200

Python实现动态数组

当底层数组已满，而有的元素要添入列表时，可以使用以下步骤实现动态数组“扩展”:
1）分配一个更大的数组 B B B。
2）设 B [ i ] = A [ i ] ( i = 0 , . . . , n − 1 ) B[i]=A[i](i=0,…,n-1) B[i]=A[i](i=0,…,n−1)， n n n表示当前数组的元素数量。
3）设 A = B A=B A=B，此后使用 B B B作为新的数组。
4）在 B B B中增添元素。
“扩展”时需要考虑一个问题：新的数组应该多大？通常做法是：新的数组大小是已满旧数组大小的2倍。
下面代码是动态数组的一种实现：

  1. # 使用ctypes模块提供的原始数组实现DynamicArray类
  2. import ctypes
  4. class DynamicArray:
  5.     '''
  6.     A dynamic array class akin to a samplified Python list.
  7.     '''
  9.     def __init__(self):
  10.         '''Create an empty array.'''
  11.         self._n = 0                 # count actual elements
  12.         self._capacity = 1          # default array capacity
  13.         self._A = self._make_array(self._capacity)  # low-level array
  15.     def __len__(self):
  16.         '''Return number of elements stored in the array.'''
  17.         return self._n
  19.     def __getitem__(self,k):
  20.         '''Return element at index k.'''
  21.         if not 0<=k<self._n:
  22.             raise IndexError('invalid index')
  23.         return self._A[k]
  25.     def append(slef,obj):
  26.         '''Add. object to end of the array.'''
  27.         if self._n == self._capacity:
  28.             self._resize(2*self._capacity)
  29.         self._A[self._n] = obj
  30.         self._n += 1
  32.     def _resize(self,c):
  33.         '''Resize internal array to capacity c.'''
  34.         B = self._make_array(c)
  35.         for k in range(self._n):
  36.             B[k] = self._A[k]
  37.         self._A = B
  38.         self._capacity = c
  40.     def _make_array(self,c):
  41.         '''Return new array with capacity c.'''
  42.         return (c*ctypes.py_object)()
  • 动态数组的摊销分析

命题2-1：
设 S S S是一个具有初始大小的动态数组实现的数组，实现策略为：当数组已满时，将此数组大小扩大为原来的2倍。 S S S最初为空，对 S S S连续执行 n n n个增添操作的运行时间为 O ( n ) O(n) O(n)。

命题2-2：
对初识为空的动态数组执行连续 n n n个增添操作，若每次调整数组大小时采用固定的增量，则运行时间为 Ω ( n 2 ) \Omega(n^2) Ω(n2)。

证明略。

  • python的列表类摊销实验分析
    python的list类的append方法实现了摊销常量时间的行为。下面代码可以验证这一结论：

    from time import time

    def compute_avg(n):

    1. '''Perform n appends to an empty list and return average time elapsed.'''
    2. data = []
    3. start = time()
    4. for k in range(n):
    5.     data.append(None)
    6. end = time()
    7. return (end-start)/n

随着n的增大，增添操作的平均运行时间如下表：(运行环境-macOS i5 2.3GHz)


























n 100 1000 10000 100000 1000000 10000000 100000000
µs 0.370 0.192 0.224 0.111 0.085 0.077 0.074

2.2 python序列类型的效率

python的列表和元组类

本节分析Python的列表和元组类的一些重要方法的运行时间性能。
Python的列表类使用动态数组的形式来存储内容，元组类比列表的内存利用率更高，这是因为元组是固定不变的，没有必要创建拥有剩余空间的动态数组。

下表是列表和元组类的nonmutating(不变)行为的渐近性能。(k表示被搜索值在最左边出现时的索引)














































操作 运行时间
len(data) O(1)
data[i] O(1)
data.count(value) O(n)
data.index(value) O(k+1)
value in data O(k+1)
data1==data2,(!=,<,>,<=,>=) O(k+1)
data[j:k] O(k-j+1)
data1+data2 O(n1+n2)
C*data O(cn)

下表是列表类的可变行为的渐近性能。














































操作 运行时间
data[j]=val O(1)
data.append(value) O(1)
data.insert(k,value) O(n-k+1)
data.pop() O(1)
data.pop(k), del data[k] O(n-k)
data.remove(value) O(n)
data1.extend(data2),data1 += data2 O(n2)
data.reverse() O(n)
data.sort() O(nlogn)

*摊销

  • 列表的insert方法性能分析
    list的insert方法的运行时间与插入位置有关。
    一般情况下，在列表的开始位置和接近中间位置进行插入操作的平均运行时间是 Ω ( n ) \Omega(n) Ω(n)，在结束位置插入操作的平均运行时间是 O ( 1 ) O(1) O(1)。
  • 列表的extend方法性能分析
    在实践中，相比于重复调用append方法，倾向于选择extend方法。
    extend方法的高效率主要缘于两个方面：
    1）与调用很多独立函数相比，调用一个函数完成所有工作的开销更小。
    2）extend在更新列表时能够提前计算出列表的最终大小。比如使用append方法，底层动态数组会有多次调整大小的风险，而extend方法最多执行一次调整操作。

Python的字符串类

Python字符串是不可变的。本节分析一些常用的字符串方法的运行时间性能。

  • 组成字符串性能分析
    假定有一个较大的字符串document，目标是生成一个新的字符串letters，该字符串仅包含原字符串的英文字母，一种实现代码如下：

    letters = ‘’
    for c in document:

    1. if c.isalpha():
    2.     letters += c

上面代码效率非常低，这是因为字符串大小固定，代码letters += c很可能计算串联部分letters+c，并把结果作为新的字符串重新分配给letters。因此构造新字符串所用时间与该字符串长度成正比，假如最终结果有n个字符，连续串联计算所花费时间为 Ω ( n 2 ) \Omega(n^2) Ω(n2)。

如何改善？
可以利用list，代码如下：

  1. temp = []
  2. for c in document:
  3.     if c.isalpha():
  4.         temp.append(c)
  5. letters = ''.join(temp)

该方法能确保运行时间为 O ( n ) O(n) O(n)。
进一步优化：

  1. letters = ''.join([c for c in document if c.isalpha()])

利用生成器再优化：

  1. letters = ''.join(c for c in document if c.isalpha())

下一篇文章：Python数据结构与算法（二）栈和队列

发表评论

表情：
评论列表 （有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读