流畅的 Python(29):序列构成的数组 2.8&2.8.1

阅读数:10 2019 年 11 月 20 日 17:11

流畅的Python(29):序列构成的数组 2.8&2.8.1

内容简介
本书致力于帮助 Python 开发人员挖掘这门语言及相关程序库的优秀特性,避免重复劳动,同时写出简洁、流畅、易读、易维护,并且具有地道 Python 风格的代码。本书尤其深入探讨了 Python 语言的高级用法,涵盖数据结构、Python 风格的对象、并行与并发,以及元编程等不同的方面。

(用bisect来管理已排序的序列)

bisect 模块包含两个主要函数,bisectinsort,两个函数都利用二分查找算法来在有序序列中查找或插入元素。


(用bisect来搜索)

bisect(haystack, needle)haystack(干草垛)里搜索 needle(针)的位置,该位置满足的条件是,把 needle 插入这个位置之后,haystack 还能保持升序。也就是在说这个函数返回的位置前面的值,都小于或等于 needle 的值。其中 haystack 必须是一个有序的序列。你可以先用 bisect(haystack, needle) 查找位置 index,再用 haystack.insert(index, needle) 来插入新值。但你也可用 insort 来一步到位,并且后者的速度更快一些。

Python 的高产贡献者 Raymond Hettinger 写了一个排序集合模块( http://code.activestate.com/recipes/577197-sortedcollection/ ),模块里集成了 bisect 功能,但是比独立的 bisect 更易用。

示例 2-17 利用几个精心挑选的 needle,向我们展示了 bisect 返回的不同位置值。这段代码的输出结果显示在图 2-4 中。

示例 2-17 在有序序列中用 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)  ➊
        offset = position * '  |'  ➋
        print(ROW_FMT.format(needle, position, offset))  ➌

if __name__ == '__main__':

    if sys.argv[-1] == 'left':  ➍
        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 函数来计算元素应该出现的位置。

❷利用该位置来算出需要几个分隔符号。

❸ 把元素和其应该出现的位置打印出来。

❹ 根据命令上最后一个参数来选用 bisect 函数。

❺ 把选定的函数在抬头打印出来。

图 2-4:用 bisect 函数时示例 2-17 的输出。每一行以 needle @ position(元素及其应该插入的位置)开始,然后展示了该元素在原序列中的物理位置

bisect 的表现可以从两个方面来调教。

首先可以用它的两个可选参数——lohi——来缩小搜寻的范围。lo 的默认值是 0hi 的默认值是序列的长度,即 len() 作用于该序列的返回值。

其次,bisect 函数其实是 bisect_right 函数的别名,后者还有个姊妹函数叫 bisect_left。它们的区别在于,bisect_left 返回的插入位置是原序列中跟被插入元素相等的元素的位置,也就是新元素会被放置于它相等的元素的前面,而 bisect_right 返回的则是跟它相等的元素之后的位置。这个细微的差别可能对于整数序列来讲没什么用,但是对于那些值相等但是形式不同的数据类型来讲,结果就不一样了。比如说虽然 1 == 1.0 的返回值是 True11.0 其实是两个不同的元素。图 2-5 显示的是用 bisect_left 来运行上述示例的结果。

图 2-5:用 bisect_left 运行示例 2-17 得到的结果(跟图 2-4 对比可以发现,值 18232930 的插入位置变成了原序列中这些值的前面)

bisect 可以用来建立一个用数字作为索引的查询表格,比如说把分数和成绩 1 对应起来,见示例 2-18。

1 成绩指的是在美国大学中普遍使用的 A~F 字母成绩,A 表示优秀,F 表示不及格。——译者注

示例 2-18 根据一个分数,找到它所对应的成绩

>>> 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']

示例 2-18 里的代码来自 bisect 模块的文档( https://docs.python.org/3/library/bisect.html )。文档里列举了一些利用 bisect 的函数,它们可以在很长的有序序列中作为 index 的替代,用来更快地查找一个元素的位置。

这些函数不但可以用于查找,还可以用来向序列中插入新元素,下面就来看看它们的用法。

图灵地址 https://www.ituring.com.cn/book/1564

评论

发布