知识卡片

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

离线批处理利用已知查询

理解等级:中级

若所有查询预先可用,可分别排序数据与查询,再用双指针合并扫描,随后按原查询位置还原答案;比较模型下排序成本 O(n log n),扫描 O(n)。

书中把在线查询必然写成 O(n²) 过于绝对:静态数据可先排序、每次二分,或按适用假设构建散列索引。离线方案应与合理的在线预处理方案比较,并计入建索引和输出成本。

289讨论并行顺序查找;拥有n个处理器时的并行时间不等于总工作量,还需要计入调度、内存带宽、归并及实际处理器数量。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      离线算法 与在线算法的通常假设不同,我们可能会一次提交众多问题实例批量解决,而不要求每个实例提交后就马上返回结果。 假设我们要实现一个字典,先在这个空字典中插入一个含有n个数字y1……yn的集合,然后进行n/2次的查询contains(xi):x1……xn/2。最优的数据结构是将每个yj插入到一个无

    • · 查看原书依据

      n个处理器上并行查找就有可能提高这n/2个顺序查找的性能,这样最坏情况的复杂度为O(n)。想要更深入了解并行算法,建议去读一下Berman和Paul(2004)年关于这个方面的著作。另外了解一些利用多核处理器并行机制的实际系统对也此也很有裨益,具体参见Armstrong的《Erlang编程:实现并发

    参考来源

    - 位置:《算法技术手册》第10章《离线算法》(spine1678;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1640.html;u288-ch10-003)。 - 结论依据:288全文实读。 - 原始内容:离线算法 与在线算法的通常假设不同,我们可能会一次提交众多问题实例批量解决,而不要求每个实例提交后就马上返回结果。 假设我们要实现一个字典,先在这个空字典中插入一个含有n个数字y1……yn的集合,然后进行n/2次的查询contains(xi):x1……xn/2。最优的数据结构是将每个yj插入到一个无 - 位置:《算法技术手册》第10章《并行算法》(spine1679;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1641.html;u289-ch10-003)。 - 结论依据:289讨论并行顺序查找;拥有n个处理器时的并行时间不等于总工作量,还需要计入调度、内存带宽、归并及实际处理器数量。 - 原始内容:n个处理器上并行查找就有可能提高这n/2个顺序查找的性能,这样最坏情况的复杂度为O(n)。想要更深入了解并行算法,建议去读一下Berman和Paul(2004)年关于这个方面的著作。另外了解一些利用多核处理器并行机制的实际系统对也此也很有裨益,具体参见Armstrong的《Erlang编程:实现并发