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

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

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

### 文章目录 ###

*   *  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列表的大小没有限制，其依赖于动态数组。  
简单理解动态数组就是，当数组元素到达当前数组的长度时，增加一个更大的数组并初始化，使其前面部分与之前数组一样，原来数组将被回收。  
下面的代码可以用来探究列表长度和底层大小关系：

import sys
    data = []
    for k in range(n):
        a = len(data)
        b = sys.getsizeof(data)
        print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a,b))
        data.append(None)

# 样例输出
    Length: 0; Size in bytes: 72
    Length: 1; Size in bytes: 104
    Length: 2; Size in bytes: 104
    Length: 3; Size in bytes: 104
    Length: 4; Size in bytes: 104
    Length: 5; Size in bytes: 136
    Length: 6; Size in bytes: 136
    Length: 7; Size in bytes: 136
    Length: 8; Size in bytes: 136
    Length: 9; Size in bytes: 136
    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倍。  
下面代码是动态数组的一种实现：

# 使用ctypes模块提供的原始数组实现DynamicArray类
    import ctypes
    
    class DynamicArray:
        '''
        A dynamic array class akin to a samplified Python list.
        '''
    
        def __init__(self):
            '''Create an empty array.'''
            self._n = 0                 # count actual elements
            self._capacity = 1          # default array capacity
            self._A = self._make_array(self._capacity)  # low-level array
    
        def __len__(self):
            '''Return number of elements stored in the array.'''
            return self._n
    
        def __getitem__(self,k):
            '''Return element at index k.'''
            if not 0<=k<self._n:
                raise IndexError('invalid index')
            return self._A[k]
    
        def append(slef,obj):
            '''Add. object to end of the array.'''
            if self._n == self._capacity:
                self._resize(2*self._capacity)
            self._A[self._n] = obj
            self._n += 1
    
        def _resize(self,c):
            '''Resize internal array to capacity c.'''
            B = self._make_array(c)
            for k in range(self._n):
                B[k] = self._A[k]
            self._A = B
            self._capacity = c
    
        def _make_array(self,c):
            '''Return new array with capacity c.'''
            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):
        '''Perform n appends to an empty list and return average time elapsed.'''
        data = []
        start = time()
        for k in range(n):
            data.append(None)
        end = time()
        return (end-start)/n

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

### 2.2 python序列类型的效率 ###

#### python的列表和元组类 ####

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

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

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>运行时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>len(data)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>data[i]</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>data.count(value)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>data.index(value)</td> 
   <td>O(k+1)</td> 
  </tr> 
  <tr> 
   <td>value in data</td> 
   <td>O(k+1)</td> 
  </tr> 
  <tr> 
   <td>data1==data2,(!=,&lt;,&gt;,&lt;=,&gt;=)</td> 
   <td>O(k+1)</td> 
  </tr> 
  <tr> 
   <td>data[j:k]</td> 
   <td>O(k-j+1)</td> 
  </tr> 
  <tr> 
   <td>data1+data2</td> 
   <td>O(n1+n2)</td> 
  </tr> 
  <tr> 
   <td>C*data</td> 
   <td>O(cn)</td> 
  </tr> 
 </tbody> 
</table>

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

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>运行时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>data[j]=val</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>data.append(value)</td> 
   <td>O(1)*</td> 
  </tr> 
  <tr> 
   <td>data.insert(k,value)</td> 
   <td>O(n-k+1)*</td> 
  </tr> 
  <tr> 
   <td>data.pop()</td> 
   <td>O(1)*</td> 
  </tr> 
  <tr> 
   <td>data.pop(k), del data[k]</td> 
   <td>O(n-k)*</td> 
  </tr> 
  <tr> 
   <td>data.remove(value)</td> 
   <td>O(n)*</td> 
  </tr> 
  <tr> 
   <td>data1.extend(data2),data1 += data2</td> 
   <td>O(n2)*</td> 
  </tr> 
  <tr> 
   <td>data.reverse()</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>data.sort()</td> 
   <td>O(nlogn)</td> 
  </tr> 
 </tbody> 
</table>

\*摊销

*  列表的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:
        if c.isalpha():
            letters += c

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

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

temp = []
    for c in document:
        if c.isalpha():
            temp.append(c)
    letters = ''.join(temp)

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

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

利用生成器再优化：

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

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

[Link 1]: https://dygwyp.github.io/blog/
[Python]: https://blog.csdn.net/lingpy/article/details/109568507