更多文章代码详情:
可以查看博主GitHub地址：https://github.com/TheAlgorithm-SimpleChinese/Python
博主个人网站：https://www.iwtmbtly.com/
对序列使用+和*（序列的拼接操作）
Python 程序员会默认序列是支持 + 和 * 操作的。通常 + 号两侧的序列由相同类型的数据 所构成，在拼接的过程中，两个被操作的序列都不会被修改，Python 会新建一个包含同样类型数据的序列来作为拼接的结果。
如果想要把一个序列复制几份然后再拼接起来，更快捷的做法是把这个序列乘以一个整 数。同样，这个操作会产生一个新序列：
>>> l = [1, 2, 3] >>> l * 5 [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3] >>> 5 * 'abcd' 'abcdabcdabcdabcdabcd'
+ 和 * 都遵循这个规律，不修改原有的操作对象，而是构建一个全新的序列。
如果在 a * n 这个语句中，序列 a 里的元素是对其他可变对象的引用的话， 你就需要格外注意了，因为这个式子的结果可能会出乎意料。比如，你想用 my_list = [[]] * 3 来初始化一个由列表组成的列表，但是你得到的列表里包含 的 3 个元素其实是 3 个引用，而且这 3 个引用指向的都是同一个列表。这可能不是你 想要的效果。
下面来看看如何用 * 来初始化一个由列表组成的列表。
建立由列表组成的列表
有时我们会需要初始化一个嵌套着几个列表的列表，譬如一个列表可能需要用来存放不同 的学生名单，或者是一个井字游戏板上的一行方块，想要达成这些目的，最好的选择是 使用列表推导：
# 建立一个包含 3 个列表的列表，被包含的 3 个列表各自有 3 个元素。打印出这个嵌套列表 >>> board = [['_'] * 3 for i in range(3)] >>> board [['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']] # 把第 1 行第 2 列的元素标记为 X，再打印出这个列表 >>> board[1][2] = 'X' >>> board [['_', '_', '_'], ['_', '_', 'X'], ['_', '_', '_']]
下面展示了另一个方法，这个方法看上去是个诱人的捷径，但实际上它是错的：
# 外面的列表其实包含 3 个指向同一个列表的引用。当我们不做修改的时候，看起来都还好。 >>> weird_board = [['_'] * 3] * 3 ➊ >>> weird_board [['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']] # 一旦我们试图标记第 1 行第 2 列的元素，就立马暴露了列表内的 3 个引用指向同一个对象的事实。 >>> weird_board[1][2] = 'O' >>> weird_board [['_', '_', 'O'], ['_', '_', 'O'], ['_', '_', 'O']]
上例犯的错误本质上跟下面的代码犯的错误一样：
row=['_'] * 3 board = [] for i in range(3): board.append(row) # 追加同一个行对象（row）3 次到游戏板（board）。
相反，上面正确的例子中的方法等同于这样做：
>>> board = [] >>> for i in range(3): ... row=['_'] * 3 # 每次迭代中都新建了一个列表，作为新的一行（row）追加到游戏板（board）。 ... board.append(row) ... >>> board [['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']] >>> board[2][0] = 'X' >>> board # 正如我们所期待的，只有第 2 行的元素被修改。 [['_', '_', '_'], ['_', '_', '_'], ['X', '_', '_']]
我们一直在说 + 和 *，但是别忘了我们还有 += 和 *=。随着目标序列的可变性的变化，这两个运算符的结果也大相径庭。
序列的增量赋值增量赋值运算符 += 和 *= 的表现取决于它们的第一个操作对象。简单起见，我们把讨论 集中在增量加法（+=）上，但是这些概念对 *= 和其他增量运算符来说都是一样的。
+= 背后的特殊方法是 __iadd__ （用于“就地加法”）。但是如果一个类没有实现这个方 法的话，Python 会退一步调用 __add__ 。考虑下面这个简单的表达式：a += b
如果 a 实现了 iadd 方法，就会调用这个方法。同时对可变序列（例如 list、bytearray 和 array.array）来说，a 会就地改动，就像调用了 a.extend(b) 一样。但是如果 a 没有实现 __iadd__ 的话，a += b 这个表达式的效果就变得跟 a = a + b 一样了：首先计算 a + b，得到一个新的对象，然后赋值给 a。也就是说，在这个表 达式中，变量名会不会被关联到新的对象，完全取决于这个类型有没有实现 __iadd__ 这 个方法。
总体来讲，可变序列一般都实现了__iadd__方法，因此 += 是就地加法。而不可变序列 根本就不支持这个操作，对这个方法的实现也就无从谈起。
上面所说的这些关于 += 的概念也适用于 *=，不同的是，后者相对应的是 __imul__。
接下来有个小例子，展示的是 *= 在可变和不可变序列上的作用：
>>> l = [1, 2, 3] >>> id(l) 4311953800 # 刚开始时列表的 ID。 >>> l *= 2 >>> l [1, 2, 3, 1, 2, 3] >>> id(l) 4311953800 # 运用增量乘法后，列表的 ID 没变，新元素追加到列表上。 >>> t = (1, 2, 3) >>> id(t) 4312681568 # 元组最开始的 ID。 >>> t *= 2 >>> id(t) 4301348296 # 运用增量乘法后，新的元组被创建。
对不可变序列进行重复拼接操作的话，效率会很低，因为每次都有一个新对象，而解释器 需要把原来对象中的元素先复制到新的对象里，然后再追加新的元素。
str 是一个例外，因为对字符串做 += 实在是太普遍了，所以 CPython 对它做了优化。为 str 初始化内存的时候，程序会为它留出额外的可扩展空间，因此进行增量操作的时候，并不会涉及复制原有字符串到新位置这类操作。
我们已经认识了 += 的一般用法，下面来看一个有意思的边界情况。这个例子可以说是突 出展示了“不可变性”对于元组来说到底意味着什么。
一个关于+=的谜题如下所示：
>>> t = (1, 2, [30, 40]) >>> t[2] += [50, 60]
上例两个表达式会产生什么结果？
到底会发生下面 4 种情况中的哪一种？
a. t 变成 (1, 2, [30, 40, 50, 60])。
b. 因为 tuple 不支持对它的元素赋值，所以会抛出 TypeError 异常。
c. 以上两个都不是。
d. a 和 b 都是对的。
我刚看到这个问题的时候，异常确定地选择了 b，但其实答案是 d，也就是说 a 和 b 都是 对的！
没人料到的结果：t[2] 被改动了，但是也有异常抛出
>>> t = (1, 2, [30, 40]) >>> t[2] += [50, 60] Traceback (most recent call last): File "", line 1, in TypeError: 'tuple' object does not support item assignment >>> t (1, 2, [30, 40, 50, 60])
Python Tutor（http://www.pythontutor.com）是一个对 Python 运行原理进行可视化分析的工 具。图里是两张截图，分别代表示例中 t 的初始和最终状态。
至此我得到了 2 个教训。
- 不要把可变对象放在元组里面。
- 增量赋值不是一个原子操作。我们刚才也看到了，它虽然抛出了异常，但还是完成了 操作。
list.sort 方法会就地排序列表，也就是说不会把原列表复制一份。这也是这个方法的 返回值是 None 的原因，提醒你本方法不会新建一个列表。在这种情况下返回 None 其实 是 Python 的一个惯例：如果一个函数或者方法对对象进行的是就地改动，那它就应该返 回 None，好让调用者知道传入的参数发生了变动，而且并未产生新的对象。例 如，random.shuffle 函数也遵守了这个惯例。
与 list.sort 相反的是内置函数 sorted，它会新建一个列表作为返回值。这个方法可以 接受任何形式的可迭代对象作为参数，甚至包括不可变序列或生成器。而 不管 sorted 接受的是怎样的参数，它最后都会返回一个列表。
不管是 list.sort 方法还是 sorted 函数，都有两个可选的关键字参数。
- reverse
如果被设定为 True，被排序的序列里的元素会以降序输出（也就是说把最大值当作 最小值来排序）。这个参数的默认值是 False。
- key
一个只有一个参数的函数，这个函数会被用在序列里的每一个元素上，所产生的结果 将是排序算法依赖的对比关键字。比如说，在对一些字符串排序时，可以用 key=str.lower 来实现忽略大小写的排序，或者是用 key=len 进行基于字符串长度的排 序。这个参数的默认值是恒等函数（identity function），也就是默认用元素自己的值来排 序。
可选参数 key 还可以在内置函数 min() 和 max() 中起作用。另外，还有些标 准库里的函数也接受这个参数，像 itertools.groupby() 和 heapq.nlargest() 等。
下面通过几个小例子来看看这两个函数和它们的关键字参数：
>>> fruits = ['grape', 'raspberry', 'apple', 'banana'] >>> sorted(fruits) ['apple', 'banana', 'grape', 'raspberry'] # 新建了一个按照字母排序的字符串列表。 >>> fruits ['grape', 'raspberry', 'apple', 'banana'] # 原列表并没有变化 >>> sorted(fruits, reverse=True) ['raspberry', 'grape', 'banana', 'apple'] # 按照字母降序排序。 # 新建一个按照长度排序的字符串列表。因为这个排序算法是稳定的， # grape 和 apple 的长度都是 5，它们的相对位置跟在原来的列表里是一样的。 >>> sorted(fruits, key=len) ['grape', 'apple', 'banana', 'raspberry'] # 按照长度降序排序的结果。结果并不是上面那个结果的完全翻转，因为用到的 # 排序算法是稳定的，也就是说在长度一样时，grape 和 apple 的相对位置不会改变。 >>> sorted(fruits, key=len, reverse=True) ['raspberry', 'banana', '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 来一步到位，并 且后者的速度更快一些。
让我们来看几个例子：
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 函数。
bisect_fn = bisect.bisect_left
else:
bisect_fn = bisect.bisect
print('DEMO:', bisect_fn.__name__) # 把选定的函数在抬头打印出来。
print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)
输出如下：
bisect 的表现可以从两个方面来调教。
首先可以用它的两个可选参数——lo 和 hi——来缩小搜寻的范围。lo 的默认值是 0，hi 的默认值是序列的长度，即 len() 作用于该序列的返回值。
其次，bisect 函数其实是 bisect_right 函数的别名，后者还有个姊妹函数叫 bisect_left。它们的区别在于，bisect_left 返回的插入位置是原序列中跟被插入元 素相等的元素的位置，也就是新元素会被放置于它相等的元素的前面，而 bisect_right 返回的则是跟它相等的元素之后的位置。这个细微的差别可能对于整数序列来讲没什么 用，但是对于那些值相等但是形式不同的数据类型来讲，结果就不一样了。比如说虽然 1 == 1.0 的返回值是 True，1 和 1.0 其实是两个不同的元素。
bisect 还可以用来建立一个用数字作为索引的查询表格，比如说把分数和成绩对应起来，如下：
# 根据一个分数，找到它所对应的成绩 >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): ... i = bisect.bisect(breakpoints, score) ... return grades[i] ... >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] ['F', 'A', 'C', 'C', 'B', 'A', 'A']用bisect.insort插入新元素
排序很耗时，因此在得到一个有序序列之后，我们最好能够保持它的有 序。bisect.insort 就是为了这个而存在的。
insort(seq, item) 把变量 item 插入到序列 seq 中，并能保持 seq 的升序顺序。如下例：
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)
输出如下：
insort 跟 bisect 一样，有 lo 和 hi 两个可选参数用来控制查找的范围。它也有个变体 叫 insort_left，这个变体在背后用的是 bisect_left。
