python中的数据结构与算法(1):列表、元组与字符串

列表是 python 中最常用、最重要的数据结构之一。

一般来说,我们用列表来管理一组数据对象,这些对象可能是同一类型,也可能是不同类型。列表不仅记录了这些数据对象,而且也记录了它们之间的一种顺序关系。

在 python 中,与列表非常类似的数据结构还有元组和字符串等,它们所支持的操作,及其底层实现,都有非常类似的地方,可以一起讨论、相互比较。


1. 列表是什么

对于一种数据结构,我们一般需要考虑两个基本问题,一个是如何在存储空间保存数据,一个是要支持哪些操作。而需要支持的操作,往往也决定了我们存储数据的具体方式,不同存储方式,可能导致完全不同的操作效率。

从我们使用者的角度看,列表应该支持哪些操作呢?

1.1 首先,当然是创建列表

我们可以使用多种方式来创建一个列表:

# 1. 使用中括号
a_list = []
b_list = ['a', 'b', 'c']

# 2. 使用列表推导式
c_list = [x for x in iterable]

# 3. 使用类型构造函数
d_list = list()
e_list = list(iterable)

1.2 其次,是检查一个列表,如它的长度,是否为空,是否包含某个元素等

这类操作不会改变列表的内容:

# 1. 判断长度
length = len(a_list)

# 2. 当且仅当列表为空,在if条件中被判断为False
if a_list: pass

# 3. 是否包含某个元素
if a in a_list: pass
if a not in a_list: pass

# 4. 取值和切片
a = min(a_list)  # 取最小值
b = max(a_list)  # 取最大值

c = a_list[i]  # 按下标取值
index = a_list.index(x)  # x在列表中首次出现的下标
count = a_list.count(x)  # x在列表中出现的次数

b_list = a_list[i:j]  # 切片

其中的许多操作都支持一些附加参数,具体可以参考官方文档


1.3 再次,是改变列表内容,如增加、减少元素等

这些操作会改变列表的内容或顺序:

# 1. 增加、减少、修改元素
a_list.append(x)
a_list.pop()

a_list[i] = x  # 按下标赋值
a_list.insert(i, x)  # 按下标插入,原数据按顺序后移

a_list.pop(i)  # 按下标弹出并删除
a_list.remove(x)  # 按数据删除

# 2. 整体操作
a_list.clear()  # 清除所有元素
a_list.sort()  # 排序
a_list.reverse()  # 逆序

1.4 另外,可能需要支持两个列表之间的操作,如合并等

# 拼接
a_list *= n
b_list = a_list * n  # n次拼接
c_list = a_list + b_list

# 合并
a_list.extend(b_list)
a_list += b_list

# 浅拷贝
b_list = a_list.copy()

1.5 最后,需要支持对列表中的元素进行遍历

我们可以直接遍历列表内容或通过下标进行遍历,当然,有时更推荐使用 enumerate() 函数:

for x in a_list: pass

for i in range(len(a_list)): pass

for i, x in enumerate(a_list): pass

显然,在设计列表时,必须考虑到这些操作,尤其是其中一些常用操作的效率问题,有时不得不在一些问题上有权衡取舍。

下面,我们简单看一下列表的具体实现技术。


2. 列表的实现技术

2.1 连续表与链表

通常来说,实现列表有两种基本方式:

  • 一种是将列表内容按顺序存放在一大块连续的存储区里,这种实现形式也称 顺序表连续表

  • 另一种是将元素存放在通过链接构造起来的一系列存储块中,上一个元素记录了下一个元素的存储位置,这样实现的表也称 链接表链表

这两种基本实现方式各有特点,在具体实现时也还有一些细节考虑。

python 中的列表是采用顺序表实现的,其主要操作逻辑如下:

  1. 创建空表时,会分配一块存储区,并记录存储区总共可以存储的元素数量和当前元素数量。当我们检查列表长度,或者判断列表是否为空时,程序只需要根据当前元素数量返回结果就行了,这两种操作显然是 O(1) 复杂度。另外,当我们根据下标操作列表中的元素时,也会判断这个下标是否在当前元素数量范围内,否则就会抛出越界错误;

  2. 列表分配的存储区保存的是数据对象的引用信息,因此是大小一致的。只要知道下标,就可以计算出引用信息的存储位置,进而可以找到数据对象,因此,根据下标取值或者赋值也是 O(1) 复杂度;

  3. 根据对象的值查找它在列表中的位置时,只能用线性检索,因此复杂度是 O(n)

  4. 容易想到,在列表尾部增加或删除元素时,复杂度是 O(1),而在其它位置插入或删除元素则需要 O(n) 复杂度;


2.2 分离式实现

如我们所知,python 列表中保存的是元素的引用信息。保存引用信息的问题是,每次查找元素都要多走一步,先找到引用信息,再进一步找到数据对象。而它的好处也是很明显的:

首先是对不同数据对象的支持。因为这些数据对象的大小是不确定的,往往是不一致的,而根据下标计算其具体位置时,需要一个确定的数值,那么,如果不使用统一的引用信息,就必须使用尽可能大的固定空间作为每个元素的存储区,可能造成比较严重的空间浪费。

其次是便于分配存储空间。由于顺序表方式需要一整块连续的存储空间,显然,这个存储空间越小,就越容易分配,而不需要在分配前进行存储空间的整理。

第三个优点是容易扩展。当随着列表元素的增加,原来分配的存储空间不够的时候,必须分配一个新的、更大的存储空间给它——也就是下面要讨论的动态增长策略。分配新的存储空间后,需要将原有数据复制到新的空间,这时,复制数据对象的工程量要比复制引用信息大得多。


2.3 动态存储策略

目前,python 在创建空列表时,会分配一块能存储 8 个元素的存储区,当存储区不足时,就换一块 4 倍大的区域。当然,如果区块已经很大,目前来说是达到 50000 个之后,新存储区的容量会是原存储区的两倍。

存储区的扩展策略是一个充满不确定性的话题。

显然,扩展存储区时会出现性能问题,因为必须把原有数据复制到新的存储区,因此,我们希望尽可能少地执行扩展动作。但是,减少扩展动作也即意味着一开始就分配更大的存储空间,会造成空间的浪费。

值得注意的是,对于操作时间要求特别高的应用,必须注意到存储空间扩展带来的性能不稳定问题。通常来说,我们可以通过占位的方式,在创建列表的时候直接设定一个容量:

a_list = [None] * 100

和空间扩展相关的一个列表操作是 clear() 方法。执行这个方法时,程序可以有两种处理逻辑:

  • 直接将现有元素数量设为 0 ,等于抛弃了原有记录;

  • 重新创建一个新的空列表,之后通过垃圾回收机制回收原来的存储空间;

python 使用的是第二种处理逻辑,原因很简单,如果采用第一种处理逻辑,原列表有可能会成为一个规模很大的空列表,造成空间的浪费。


2.4 链表实现的优势和问题

如果采用链表实现,会有什么不一样呢?

链表是由一个个节点组成的,每个节点保存着下一个节点的引用信息。那么,用链表实现的列表将不会有分配整块存储空间带来的问题,即上面讨论的分离式实现和动态存储策略,这是一个重要优势。

当然,这个优势也不是没有代价,由于每个节点都要存储下一个节点的链接,因此会占用更多的空间。

对于列表需要支持的主要操作来说,在链表中,除了头部节点,一般性的增加和删除元素都需要线性时间。事实上,增加和删除操作本身只需要常量时间,因为不需要像顺序表那样移动其它元素,但找到需要增加和删除元素的位置却需要线性时间。通过给链表增加一个尾指针,可以实现尾部增加元素的 O(1) 复杂度,但删除元素依然需要线性时间。

或许链表最大的问题在于,根据下标取值需要线性时间。考虑到根据下标取值和切片操作的频率,python 不使用链表实现列表,理由是很充分的。


3. 元组和列表的区别

元组除了是不可变类型外,支持的操作与列表非常相似。

显然,作为不可变类型,元组没有存储空间扩展的问题。它也不需要在创建的时候提前分配充足的空间,有几个元素就分配几个空间即可。

其次,同样由于它的不可变性质,它的内容是确定的(至少其引用信息不会变化),因此,可以支持 __hash__ 函数,进一步地,也就可以作为字典的 key 或集合中的元素(它们本质上也是一样的)。


4. 字符串和列表的区别

如我们所知,字符串和列表也非常接近。

从实现技术上说,字符串中保存的数据对象都是一致的,因此不需要采用上面讨论的分离式实现,这是它与列表的主要区别。

而从应用需求来说,字符串需要支持很多独特的操作,比如 replace() 等。总的来说,这些操作都涉及线性表中值的查找和匹配问题,关于这个问题,有专门的算法研究,也由此产生了正则表达式这样的,另一种维度上的语言,这里就不多讨论了。


END

公众号:ReadingPython


发表评论

评论列表,共 0 条评论