知识卡片

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

原地差商更新要保护旧一行

理解等级:中级

差商表当前级只依赖前一级,故不必同时保存整个三角表。interpol用n项table保存一行,算出下一行后记录其首项为coeff[k],即可继续覆写同一缓冲。

实际内层i从小到大,每次用旧table[i+1]与旧table[i]计算新table[i];较右的旧值尚未被覆写。若把循环反过来而不改存储方案,table[i+1]可能已是新行,就混用了不同阶数。

这种空间复用依赖读写次序,而非看到“只依赖上一行”就能任意原地遍历。table/coeff临时数组各n项,第二次分配失败时原实现会free(table),正常完成也分别释放。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      仅依赖于其前一行的计算结果(见图13-2以及图13-3),因此并不需要一次性保存所有的表项。所以,只为最占用空间的行分配存储空间即可,该行将有n个条目。接下来,用fx中的值来初始化差商表的第一行。这是为计算差商表中的第三行做准备。(前两行不需要计算,因为这两行中的条目都已经保存在x和fx中。)初始化

    参考来源

    - 位置:《算法精解:C语言描述》第13章《多项式插值的实现与分析》(spine1362;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1328.html;u232-ch13-008)。 - 结论依据:232全部空间/差商循环说明与02991–02992完整初始化、递推、两次释放实读,保护旧值逻辑由实际从左至右更新推导。 - 原始内容:仅依赖于其前一行的计算结果(见图13-2以及图13-3),因此并不需要一次性保存所有的表项。所以,只为最占用空间的行分配存储空间即可,该行将有n个条目。接下来,用fx中的值来初始化差商表的第一行。这是为计算差商表中的第三行做准备。(前两行不需要计算,因为这两行中的条目都已经保存在x和fx中。)初始化