Python中列表与元组、字典与集合、字符串

列表与元组

基础

1. 相同点：
   • 列表和元组都是一个可以放置任意数据类型的有序集合；
   • 列表和元组都支持负数索引；
   • 列表和元组都支持切片操作；
   • 列表和元组都可以随意嵌套。
2. 不同点：

• 列表是动态的(mutable)：长度大小不固定，可以随意地增加、删减或者改变元素。

• 元组是静态的（immutable）：长度大小固定，无法增加删减或者改变，对任何改变只有创建一个新的元组。

# 创建列表
l = [1, 2, 3, 4,'a','b','c',['g','h','j']]
# 修改列表
l[3] = 30 # l = [1, 2, 3, 30,'a','b','c',['g','h','j']]

# 创建元组
tup = (1,2,3,4,'a','b','c',['g','h','j'])
# 修改元组，只有新建一个元组
new_tup = tup + (5, ) #new_tup = (1,2,3,4,'a','b','c',['g','h','j'],5)

• 两者存储方式的差异:

l = [1, 2, 3, 4,'a','b','c',['g','h','j']]
l.__sizeof__()
104
tup = (1,2,3,4,'a','b','c',['g','h','j'])
tup.__sizeof__()
88

存储相同的元素，元组的存贮空间要比列表少16字节，因为列表是动态的，需要存储指针(int型，8字节)和需要额外存储已经分配的长度大小（8字节）（over-allocating）达到实时追踪列表空间使用情况，当空间不足时及时分配额外空间，保证增加 / 删除的时间复杂度均为 O(1)。而元组长度大小固定，元素不可变，所以存储空间固定。

# 列表增加元素时空间大小变化
l = []
l.__sizeof__() // 空列表的存储空间为 40 字节
40
l.append(1)
l.__sizeof__()
72 // 加入了元素 1 之后，列表为其分配了可以存储 4 个元素的空间 (72 - 40)/8 = 4
l.append(2)
l.__sizeof__()
72 // 由于之前分配了空间，所以加入元素 2，列表空间不变
l.append(3)
l.__sizeof__()
72 // 同上
l.append(4)
l.__sizeof__()
72 // 同上
l.append(5)
l.__sizeof__()
104 // 加入元素 5 之后，列表的空间不足，所以又额外分配了可以存储 4 个元素的空间

性能

元组要比列表更加轻量级一些，所以总体上来说，元组的性能速度要略优于列表，得益于Python的垃圾回收机制，对静态数据做一些资源缓存，元组的性能优势会更明显。

两者初始化时间比较：

python3 -m timeit 'x=(1,2,3,4,5,6)'
20000000 loops, best of 5: 9.97 nsec per loop
python3 -m timeit 'x=[1,2,3,4,5,6]'
5000000 loops, best of 5: 50.1 nsec per loop

一般来看，元组的初始化时间比列表快5倍。

两者元素索引时间比较：

python3 -m timeit -s 'x=[1,2,3,4,5,6]' 'y=x[3]'
10000000 loops, best of 5: 22.2 nsec per loop
python3 -m timeit -s 'x=(1,2,3,4,5,6)' 'y=x[3]'
10000000 loops, best of 5: 21.9 nsec per loop

两者性能基本一致。

使用场景

具体情况具体分析

1. 存储对象的数据和数量保持不变，使用元组最合适。
2. 存储对象的数据和数量是可变的，使用列表更合适。

总结

• 列表是动态的数据结构：长度可变，可以随意的增加、删除或改变元素；列表的存储空间略大于元组，性能略逊于元组。

• 元组是静态的数据结构：长度固定，不能对元素进行增加、删减或者改变操作。元组存储空间略小于列表，性能稍优。

# 创建空列表
# option A
empty_list = list()

# option B
empty_list = []

# option B的性能稍优

字典与集合

python3.7中字典被确认为有序

• 相比于列表和元组，字典的性能更优：字典的查找、添加和删除操作的时间复杂度为O(1)。

• 集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

创建

1. 字典的创建方法：

d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])
d4 = dict(name='jason', age=20, gender='male')
d1 == d2 == d3 ==d4
True

2. 集合的创建方法：

s1 = {1, 2, 3}
s2 = set([1, 2, 3])
s1 == s2
True

Python中的字典和集合，无论是键还是值，都可以是混合类型

元素的访问

1. 字典中的元素的访问：

d = {'name': 'jason', 'age': 20}
d['name']
'jason'
d['location'] # 键不存在就会抛出异常
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'location'

# 使用 get(key, default) 函数来进行索引。如果键不存在，调用 get() 函数可以返回一个默认值。
d = {'name': 'jason', 'age': 20}
d.get('name')
'jason'
d.get('location', 'null')
'null'

2. 集合中的元素访问：

集合的本质是一个哈希表，所以并不支持索引操作

s = {1, 2, 3}
s[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing

使用value in dict/set判断一个元素在不在字典或者集合内：

s = {1, 2, 3}
1 in s
True
10 in s
False

d = {'name': 'jason', 'age': 20}
'name' in d
True
'location' in d
False

元素的增加、删除、更改

d = {'name': 'jason', 'age': 20}
d['gender'] = 'male' # 增加元素对'gender': 'male'
d['dob'] = '1999-02-01' # 增加元素对'dob': '1999-02-01'
d
{'name': 'jason', 'age': 20, 'gender': 'male', 'dob': '1999-02-01'}
d['dob'] = '1998-01-01' # 更新键'dob'对应的值
d.pop('dob') # 删除键为'dob'的元素对
'1998-01-01'
d
{'name': 'jason', 'age': 20, 'gender': 'male'}

s = {1, 2, 3}
s.add(4) # 增加元素 4 到集合
s
{1, 2, 3, 4}
s.remove(4) # 从集合中删除元素 4
s
{1, 2, 3}

注意：集合中的pop()操作是删除最后一个元素，但是集合是无序的，所以要慎用pop()。

排序

字典中的排序，根据键或值进行升序、降序排序：

d = {'b': 1, 'a': 2, 'c': 10}
d_sorted_by_key = sorted(d.items(), key=lambda x: x[0]) # 根据字典键的升序排序
d_sorted_by_value = sorted(d.items(), key=lambda x: x[1]) # 根据字典值的升序排序
d_sorted_by_key
[('a', 2), ('b', 1), ('c', 10)] #返回的是一个列表，里面是原来字典的键值对组成的元组
d_sorted_by_value
[('b', 1), ('a', 2), ('c', 10)] #返回的是一个列表，里面是原来字典的键值对组成的元组

集合中的排序，直接使用sorted(set)，返回排序好的列表：

s = {3, 4, 2, 1}
sorted(s) # 对集合的元素进行升序排序
[1, 2, 3, 4]

性能

工作原理

字典和元组的内部结构都是一张哈希表

• 字典中的哈希表存储了哈希值(hash)、键和值这三个元素。
• 集合中的哈希表只存储单一的元素。

# 老Python中的哈希表结构如下：
--+-------------------------------+
  | 哈希值 (hash)  键 (key)  值 (value)
--+-------------------------------+
0 |    hash0      key0    value0
--+-------------------------------+
1 |    hash1      key1    value1
--+-------------------------------+
2 |    hash2      key2    value2
--+-------------------------------+
. |           ...
__+_______________________________+


{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}
# 这个字典会存储为下面的形式,随着哈希表的扩张，它会变得越来越稀疏
entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'mike'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]

# 为提高存储空间的利用率，新版本的哈希表除了存储字典本身的结构，还会把索引和哈希值、键、值单独分开
Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------

Entries
--------------------
hash0   key0  value0
---------------------
hash1   key1  value1
---------------------
hash2   key2  value2
---------------------
        ...
---------------------

{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}
# 会存储成这个样子
indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'mike'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]

插入操作

每次向字典或集合插入一个元素时，Python 会首先计算键的哈希值（hash(key)），再和 mask = PyDicMinSize – 1 做与操作，计算这个元素应该插入哈希表的位置 index = hash(key) & mask。如果哈希表中此位置是空的，那么这个元素就会被插入其中。而如果此位置已被占用，Python 便会比较两个元素的哈希值和键是否相等。

• 若两者都相等，则表明这个元素已经存在，如果值不同，则更新值。
• 若两者中有一个不相等，这种情况我们通常称为哈希冲突（hashcollision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。

查找操作

根据哈希值找到应该处于的位置，然后比较哈希表这个位置中元素的哈希值和键，如果相等直接返回，如果不等，继续查找，直到找到空位或抛出异常。

删除操作

Python中字典的删除操作会对这个位置的元素，赋予一个特殊的值，等到重新调整哈希表的大小时，再删除。字典和集合会被预留1/3的剩余空间保证操作的高效性。

总结

# Option A
d = {'name': 'jason', 'age': 20, 'gender': 'male'}

# Option B
d = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
# Option A的操作更高效

d = {'name': 'jason', ['education']: ['Tsinghua University', 'Stanford University']}
# 初始化错误，列表为可变对象，不能作为key

字符串

Python的字符串可以看作由单个字符组成的数组，支持索引、切片、遍历等操作。但本身为不可变对象。

表示

# 三种表示方法都一样
s1 = 'hello'
s2 = "hello"
s3 = """hello"""
s1 == s2 == s3
True

转义

s = 'a\nb\tc'
print(s)
a
b  c

len(s)
5

修改

对字符串进行修改，时间复杂度为O(n)，n为新字符串的长度。

修改’hello’中第一个字符’h’为’H’:

s = 'H' + s[1:]
s = s.replace('h', 'H')

• 第一种方法，直接用大写的’H’，通过’+’操作符，与原字符串切片操作的子字符串拼接而成的新字符串。
• 第二种方法，直接扫描原字符串，把小写的’h’替换成大写的’H’，得到新字符串

时间复杂度为O(n)，n为新字符串的长度。

使用’+=’操作字符串的拼接

打破了字符串不可变的特性，并且时间复杂度仅为O(n)。

str1 += str2  # 表示 str1 = str1 + str2

使用.join()拼接字符串

表示把每个元素都按照指定的格式连接起来:

l = []
for n in range(0, 100000):
    l.append(str(n))
l = ' '.join(l) 

列表的append操作是O(1)复杂度，字符串也是一样的，所以这个for循环例子的时间复杂度为n*O(1) = O(n)。

使用.split()分割字符串

string.split(separator)表示把字符串按照separator分割成子字符串，并返回一个分割后子字符串组合的列表。

常用于对数据的解析处理，比如我们读取了某个文件的路径，想要调用数据库的API，去读取相应的数据，我们通常会写成下面这样:

def query_data(namespace, table):
    """
    given namespace and table, query database to get corresponding
    data         
    """

path = 'hive://ads/training_table'
namespace = path.split('//')[1].split('/')[0] # 返回'ads'
table = path.split('//')[1].split('/')[1] # 返回 'training_table'
data = query_data(namespace, table) 

常见的还有:

• string.strip(str)：表示去掉首尾的str字符串；
• string.lstrip(str)：表示只去掉开头的str字符串；
• string.rstrip(str)：表示只去掉尾部的str字符串。

有时从文件读取进来的字符串，开头和结尾都含有空字符，可以使用strip()去掉它们:

s = ' my name is jason '
s.strip()
'my name is jason'

• string.find(sub,start,end)：表示从start到end查找字符串中子字符串sub的位置。

格式化

print('no data available for person with id: {}, name: {}'.format(id, name))

其中的string.format()是格式化函数，{}是格式符——为后面的真实值预留位置。

# 如果 id = '123',name = 'jason'
'no data available for person with id: 123, name: jason'

官方文档推荐使用foramt()

另外还有%表示，不推荐:

print('no data available for person with id: %s, name: %s' % (id, name))

总结

• Python 中字符串使用单引号、双引号或三引号表示，三者意义相同，并没有什么区别。其中，三引号的字符串通常用在多行字符串的场景。
• Python 中字符串是不可变的（前面所讲的新版本 Python 中拼接操作’+=’是个例外）。因此，随意改变字符串中字符的值，是不被允许的。
• Python 新版本（2.5+）中，字符串的拼接变得比以前高效了许多，你可以放心使用。
• Python 中字符串的格式化（string.format）常常用在输出、日志的记录等场景。

思考

下面两种字符串拼接操作，哪个更优？

s = ''
for n in range(0, 100000):
    s += str(n)

l = []
for n in range(0, 100000):
    l.append(str(n))

s = ' '.join(l)

答：

如果字符串拼接的次数较少，比如range(100)，那么方法一更优，因为时间复杂度精确的来说第一种是O(n)，第二种是O(2n)，如果拼接的次数较多，比如range(1000000)，方法二稍快一些，虽然方法二会遍历两次，但是join的速度其实很快，列表append和join的开销要比字符串+=小一些。