返回主题:批处理作业的写法:连接、聚合与作业抽象

知识卡片

普通读书笔记卡

按前缀分割递归搜索树

理解等级:中级

枚举长度为 M、每位有 n 个取值的序列时,可按首位把搜索树切为 n 个互不重叠的子树,分给 n 个工人;按前两位可切为 n² 个子树。每个工人只遍历剩余后缀,工头合并计数。拆分降低单个任务的递归深度,不改变总结果数;工人数量、调度和输出开销仍约束收益。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《大规模分布式系统架构与设计实战》第2章《分布式并行计算的原理与实践》2.5.12“使用并行计算大幅提升递归算法效率”(源文件:`_epub-src/OEBPS/text00030.html`) - 结论依据:原文给出按一位、两位前缀拆成 n、n×n 份的递归式;示例代码中工人以 index 为初始前缀,工头只累加各工人的计数。 - 原始内容:假设我们有n台计算机,每台计算机的编号依次为1到n,那么每台计算机实际上只要计算r(n,m-1)的结果就够了,这里实际上将递归降了一级,并且让多机并行计算。