[Python知识库]【读书笔记】 《流畅的python》2.7-2.8 读书笔记

2021-09-02 《流畅的python》2.7-2.8 读书笔记

一、list.sort方法和内置函数sorted
list.sort 方法会就地排序列表，也就是说不会把原列表复制一份。这也是这个方法的 返回值是 None 的原因。（本方法不会新建一个列表。在这种情况下返回 None 其实是 Python 的一个惯例：如果一个函数或者方法对对象进行的是就地改动，那它就应该返回 None，好让调用者知道传入的参数发生了变动，而且并未产生新的对象）。random.shuffle函数也遵守此惯例。
list.sort 方法的弊端：调用者无法将其串联起来。而返回一个新对象的方法（比如说 str 里的所有方法）则正好相反，它们可以串联起来调用，从而形成连贯接口（fluent interface）。
与 list.sort 相反的是内置函数 sorted，它会新建一个列表作为返回值。这个方法可以接受任何形式的可迭代对象作为参数，甚至包括不可变序列或生成器。而不管 sorted 接受的是怎样的参数，它最后都会返回一个列表。

>>> fruits = ['grape', 'raspberry', 'apple', 'banana'] 
>>> sorted(fruits)['apple', 'banana', 'grape', 'raspberry']# 新建了一个按照字母排序的字符串列表。
>>> fruits 
['grape', 'raspberry', 'apple', 'banana'] # 原列表并没有变化。
>>> sorted(fruits, reverse=True) 
['raspberry', 'grape', 'banana', 'apple'] # 按照字母降序排序。
>>> sorted(fruits, key=len) 
['grape', 'apple', 'banana', 'raspberry'] #新建一个按照长度排序的字符串列表。因为这个排序算法是稳定的，grape 和 apple 的 长度都是 5，它们的相对位置跟在原来的列表里是一样的。 
>>> sorted(fruits, key=len, reverse=True) 
['raspberry', 'banana', 'grape', 'apple'] #按照长度降序排序的结果。结果并不是上面那个结果的完全翻转，因为用到的排序算法是稳定的，也就是说在长度一样时，grape 和 apple 的相对位置不会改变。
>>> fruits 
['grape', 'raspberry', 'apple', 'banana'] # 直到这一步，原列表 fruits 都没有任何变化。
>>> fruits.sort() # 对原列表就地排序，返回值 None 会被控制台忽略。
>>> fruits 
['apple', 'banana', 'grape', 'raspberry'] #此时 fruits 本身被排序。

已排序的序列可以用来进行快速搜索，而标准库的 bisect 模块给我们提供了二分查找算法。
二、用bisect来管理已排序的序列
bisect 模块包含两个主要函数，bisect 和 insort，两个函数都利用二分查找算法来在有序序列中查找或插入元素。
（一）用bisect来搜索
bisect(haystack, needle) 在 haystack（干草垛）里搜索 needle（针）的位置，该位置满足的条件是，把 needle 插入这个位置之后，haystack 还能保持升序。也就是在说这个函数返回的位置前面的值，都小于或等于 needle 的值。其中 haystack 必须是一个有序的序列。
可以先用 bisect(haystack, needle) 查找位置 index，再用haystack.insert(index, needle) 来插入新值。也可用 insort 来一步到位，并且后者的速度更快一些。
在有序序列中用 bisect 查找某个元素的插入位置

import bisect
import sys
HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]
ROW_FMT = '{0:2d} @ {1:2d} {2}{0:<2d}'


def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle)  #  用特定的 bisect 函数来计算元素应该出现的位置。
        offset = position * ' |'  # 利用该位置来算出需要几个分隔符号。
        print(ROW_FMT.format(needle, position, offset))  # 把元素和其应该出现的位置打印出来。


if __name__ == '__main__':
    if sys.argv[-1] == 'left':
        bisect_fn = bisect.bisect_left  # 根据命令上最后一个参数来选用 bisect 函数。
    else:
        bisect_fn = bisect.bisect  # 把选定的函数在抬头打印出来。
    print('DEMO:', bisect_fn.__name__)
    print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
    demo(bisect_fn)

运行结果：

DEMO: bisect_right
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14  | | | | | | | | | | | | | |31
30 @ 14  | | | | | | | | | | | | | |30
29 @ 13  | | | | | | | | | | | | |29
23 @ 11  | | | | | | | | | | |23
22 @  9  | | | | | | | | |22
10 @  5  | | | | |10
 8 @  5  | | | | |8 
 5 @  3  | | |5 
 2 @  1  |2 
 1 @  1  |1 
 0 @  0 0 

说明：每一行以 needle @ position（元素及其应该插入的位置）开始，然后展示了该元素在原序列中的物理位置。
bisect 的表现可以从两个方面来调教。
首先可以用它的两个可选参数——lo 和 hi——来缩小搜寻的范围。lo 的默认值是 0，hi的默认值是序列的长度，即 len() 作用于该序列的返回值。
其次，bisect 函数其实是 bisect_right 函数的别名，后者还有个姊妹函数叫bisect_left。它们的区别在于，bisect_left 返回的插入位置是原序列中跟被插入元素相等的元素的位置，也就是新元素会被放置于它相等的元素的前面，而 bisect_right返回的则是跟它相等的元素之后的位置。这个细微的差别可能对于整数序列来讲没什么用，但是对于那些值相等但是形式不同的数据类型来讲，结果就不一样了。比如说虽然 1 == 1.0 的返回值是 True，1 和 1.0 其实是两个不同的元素。
（二）用bisect.insort插入新元素
1.排序很耗时，因此在得到一个有序序列之后，我们最好能够保持它的有序。bisect.insort 就是为了这个而存在的
2.insort(seq, item) 把变量 item 插入到序列 seq 中，并能保持 seq 的升序顺序。
insort 可以保持有序序列的顺序

import bisect
import random
SIZE=7
random.seed(1729)
my_list = []
for i in range(SIZE):
    new_item = random.randrange(SIZE*2)
    bisect.insort(my_list, new_item)
    print('%2d ->' % new_item, my_list)

输出结果：

10 -> [10]
 0 -> [0, 10]
 6 -> [0, 6, 10]
 8 -> [0, 6, 8, 10]
 7 -> [0, 6, 7, 8, 10]
 2 -> [0, 2, 6, 7, 8, 10]
10 -> [0, 2, 6, 7, 8, 10, 10]