知识卡片
二分定位不替代有序性保证
bisect在已排序序列定位插入点,不会先验证输入有序;无序输入也可能给出一个数,却不具有正确排序意义。insort再执行插入,维护列表可能移动后续项,不能把O(log n)查找成本当整个插入操作的成本。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
不会判断原列表是否是有序的,因为这样做的开销太大了。因此,将它们用于无序列表虽然不会报错,但可能会导致不正确的结果。
参考来源
- 位置:《利用Python进行数据分析》附录A Python语言精要《二分搜索及维护有序列表》(spine332;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0317_split_001.html;u332-ch90-035)。
- 结论依据:原文在“不会判断原列表是否是有序的”附近的定义、例子或代码支撑本卡核心说明:bisect在已排序序列定位插入点,不会先验证输入有序;无序输入也可能给出一个数,却不具有正确排序意义。边界按已读前提解释;示例未执行。
- 原始内容:不会判断原列表是否是有序的,因为这样做的开销太大了。因此,将它们用于无序列表虽然不会报错,但可能会导致不正确的结果。