知识卡片

普通读书笔记卡 · 1708.b.2.g · 生成模型:未记录

计量单位决定操作成本

理解等级:中级

把一次库调用算作一步只是某种分析模型,不代表它实际所做工作与参数无关。memcpy要处理指定范围的字节,若复制长度随输入增长,就不能在按字节工作量的模型里无条件记常数;malloc的代价还依赖实现及分配状态。

当元素大小固定时,将一次元素搬动抽象成常数可以帮助分析排序规模。若同时研究元素长度,就要把该参数纳入成本。原书“无论复制/分配多少都固定时间”的概括过强,不能从机器级高效推出与数据量无关。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      通常memcpy和malloc的调用会在一段固定的时间内执行完。一般来说,无论复制或分配多少数据,在机器运行级别上,这些函数的运行效率都是非常高的。当然,它们更为精确的效率取决于它们在哪种计算机上执行和一些其他因素(特别是malloc,它的效率还取决于系统调用它时的状态)。

    参考来源

    - 位置:《算法精解:C语言描述》第4章《问与答》(spine1202;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1170.html;u045-ch04-008)。 - 结论依据:45最后一问明确涉及memcpy/malloc参数与实现状态,却给出固定时间过宽结论;结合44的esize实际搬动区分计费模型,不声称具体分配器复杂度或测量结果。 - 原始内容:通常memcpy和malloc的调用会在一段固定的时间内执行完。一般来说,无论复制或分配多少数据,在机器运行级别上,这些函数的运行效率都是非常高的。当然,它们更为精确的效率取决于它们在哪种计算机上执行和一些其他因素(特别是malloc,它的效率还取决于系统调用它时的状态)。