chapter_2

chapter 2.1

字符串与字节序列

（str,bytes)

• Python3中只有一种能够保存文本信息的数据类型，就是str(string,字符串,不可变序列)
• Python2中用str来表示字节字符串
• Python3中用bytes对象来处理字节字序列（字节字符串，不可变序列)
• Python3所有被'"'''包裹且没有前缀的值都表示str数据类型，都是Unicode.
• Python2中，Unicode需要加u’xxx’前缀，Python3向后兼容，仍支持这个前缀
• Unicode字符串中包含无法用字节表示的抽象文本．Unicode字符串需要被编码为二进制数据，才能在磁盘中保存或在网络中传输

bytes(0~255)之间的整数

print(bytes([100,101,102,103,104]))

b'defgh'

bytes或者bytearray,转化为其他序列类型（list/tuple),也会显示真面目．

list(b'defgh')

[100, 101, 102, 103, 104]

tuple(b'defgh')

(100, 101, 102, 103, 104)

set(b'defgh')

{100, 101, 102, 103, 104}

u'今晚打老虎'

'今晚打老虎'

字符串编码为字节序列

• str.encode(encoding, errors),encoding默认’utf-8’
• bytes(source, encoding, errors),source:字符串，encoding：指定编码格式，没有默认参数

字节序列转换为字符串

• bytes.decode(encoding, errors)

• str(source, encoding, errors),source:字节序列

字节数组bytearray

bytes和str都是不可变对象(每一次微小的修改，都会创建一个新的实例),bytearray是bytes的可变版本，可以任意修改，可以像操作列表一样(append, pop, insert)

字符串的拼接

str在python中作为一个不可变的对象，任意拼接两个字符串都会创建一个新的字符串对象．

如果用循环来拼接多个字符串：

s = ''
for string in str_list:
    s += string

因为str为不可变的，通过循环拼接多个str是一种效率极低的方法．str.join()是一种快速的方法．

s = ''.join(str_list)

str.join()方法的注意事项：

• .join()方法虽然很快，但是并不意味着所有的拼接操作都要用到它，仅在拼接很多个字符串时是最佳选择
• 代码的可读性，可读性是最重要的，拼接较少字符串时’+'更合适
• Cpython中的constant folding,一些复杂的字面值(较长的字符串)会被转换为更短的形式，例如:'a'+'b'+'c'转换为'abc'

Python : list实现细节

  实际上在CPython中列表是由长度可变的数组实现的．Python中的列表是由对其他对象的引用组成的连续数组．指向这个数组的指针及其长度被保存在一个列表的头部结构中，在python中创建列表时，也就是CPython中创建变长数组时，采用了（exponential over-allocation),所以每次插入或删除某个元素并不会改变数组的大小．

列表操作的平均时间复杂度:

• 复制　：O(n)
• 添加元素　：O(1)
• 插入元素　：O(n)
• 获取元素　：O(1)
• 修改元素　：O(1)
• 删除元素　：O(n)
• 遍历　：O(n)
• 获取长度为k的片段　：O(k)
• 删除片段　：O(n)
• 修改长度为k的片段　：O(n+k)
• 列表扩展extend　：O(k)
• 乘以k　：O(n*k)
• 测试元素是否在列表中　：O(n)
• min()/max()　：O(n)
• 获取列表的长度　：O(1)

列表推导

evens = []
for i in range(100):
    if i % 2 ==0:
        evens.append(i)

在python写这样的代码是很糟糕的,原因如下：

• 解释器在每次循环中都需要判断列表中的哪一部分需要修改
• 需要一个计数器来跟踪需要处理的元素
• append()是一个列表方法，每次便利时需要额外执行一次查询函数

evens = [i for in range(100) if i % 2 == 0]

列表推导和内部数组大小的调整

解释器在对列表推导进行求值过程中并不知道最终容器的大小，因此它是无法为数组预先分配大小的．

zip

zip可对多个长度相等的可迭代对象进行均匀的遍历:

for item in zip([1,2,3],[4,5,6],[7,8,9]):
    print(item)
>>>(1, 4, 7)
>>>(2, 5, 8)
>>>(3, 6, 9)

对zip()函数返回的结果再次调用zip():

for item in zip(*zip([1,2,3],[4,5,6],[7,8,9])):
    print(item)
>>>(1, 2, 3)
>>>(4, 5, 6)
>>>(7, 8, 9)

Sequence Unpacking序列解包

不局限于列表和元组，是用于任意序列类型(字符串．字节序列)

a, b, c = 1, 2, 3
print(a, b, c)
>>>1 2 3

a, b, c = 'edc'
print(a, b, c)
>>>e d c

a, b, c = b'edc'
print(a, b, c)
>>>101 100 99

解包还可以利用＊表达式获取单个变量中的多个元素:

a, b, *c = 'abcdefg'
print(a, b, c)
>>>a b ['c', 'd', 'e', 'f', 'g']

a, *b, c = 'abcdefg'
print(a, b, c)
>>>a ['b', 'c', 'd', 'e', 'f'] g

(a, b), (c, d) = (1, 2), (3, 4)
print(a, b, c, d)
>>>1 2 3 4

Dict字典

字典推导析和列表推导具有相同的优点 :

squares_dict = {num : num**2 for num in range(100)}

Python3中keys(),values(),items()返回的是视图对象 :

• keys()
• values()
• items(),返回（key,value)二元元组．
  试图对象既有列表的特性也有迭代器的特性，不会将所有的元素都加载到内存中，但是仍可以使用len()来获取它的长度,in判断元素是否在其中．

实现细节

  Cpython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构．所以只有可hash的对象才能作为字典的键值，如果一个对象有个在整个生命周期都不变的散列值hash value,而且这个值可以和其他对象进行比较，那么这个对象就是可hash的．Python中所有的不可变类型都是可hash的，列表，字典，集合是不可hash的．

定义hash类型的协议包括下面这两种方法:

• hash:给出字典内部实现需要的散列值(int），用户自定义类的实例对象，有id()给出．
• eq:比较两个对象的值是否相等，对于用户自定义的类，除了自身，所有的实例对象默认不相等．

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

散列冲突(hash collision)

  Python字典是使用哈希表实现的，究其本质也是一个数组，其索引是通过哈希函数获得的.散列函数的目标是在数组中均匀分布键，良好的散列函数会最小化小化了冲突的可能，如果两个对象相等，那么它们的散列值一定相等．反之不一定成立,这时冲突就发生了，散列值相等，但是两个对象并不相等．Cpython中使用开放定址法（open addressing)来解决冲突．在构造字典的过程中，当键值(可hash的对象)连续时，hash函数可以很好的工作，但是不连续时会增加碰撞的可能．

开放地址(open addressing)

  开放寻址意思是，当冲突发生的时候，即上图中’z’的情况，索引３已经在数组中被使用，就寻找未被占用的索引，将键值’z’对应的value插入数组中对应的位置．

字典常见操作的时间复杂度

	操作	平均复杂度	最坏复杂度
0	获取元素	O(1)	O(n)
1	修改元素	O(1)	O(n)
2	删除元素	O(1)	O(n)
3	复制	O(n)	O(n)
4	遍历	O(n)	O(n)

注意！！！

  在复制和遍历字典的操作中，最坏情况是字典曾达到的最大元素数目，不是字典当前的元素数目．意思就是如果一个字典原来很大，后来删除了很多元素，遍历仍要花费很长时间．因此如果要频繁删除字典中的元素，同时字典较大，那么最好创建一个新的字典．

字典的缺点和替代方案

• 缺点：保存元素的顺序和键的添加顺序大多数情况下是不一致的，（连续的整数键值除外,因为连续的整数has后的索引值仍是连续的整数．
• 替代方案:Python的标准库collections,提供了一个OrderedDict有序的字典．

from collections import OrderedDict
OrderedDict((str(num):num) for num in range(5))

OrderedDict()

set集合

  当元素的顺序不重要的时候，集合是一个不错的数据结构．Python提供了两种集合类型：

• set():可变，无序，有限的集合，元素唯一
• frozenset():不可变，无序，元素唯一，可哈希
  • forzenset()可作为字典的键值，也可作为set()或forzenset()中的一个元素
  • set()为可变对象，所以set()不能作为set()和forzenset()中的元素，不然会引发TypeError
• 集合推导：{num for num in range(10)}

实现细节

  在CPython中，集合其实就是带空值的字典，键值为集合的元素．因此集合元素也是可哈希的，所以集合中的元素也依赖于类似散列表的结构，平均时间复杂度为O(1),最坏的情况O(n).

超越基础集合的类型－collections

• namedtuple() : 创建元组子类的工厂函数
• deque : 双端队列，类似列表，是栈和队列的一般化，可以从两端添加/取出元素
• ChainMap : 类似字典的类
• Counter : 字典子类，对哈希对象进行计数
• OrderedDict : 字典子类，创建有序的字典
• derfaultdict : 字典子类