知识卡片
按前缀分割递归搜索树
枚举长度为 M、每位有 n 个取值的序列时,可按首位把搜索树切为 n 个互不重叠的子树,分给 n 个工人;按前两位可切为 n² 个子树。每个工人只遍历剩余后缀,工头合并计数。拆分降低单个任务的递归深度,不改变总结果数;工人数量、调度和输出开销仍约束收益。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《大规模分布式系统架构与设计实战》第2章《分布式并行计算的原理与实践》2.5.12“使用并行计算大幅提升递归算法效率”(源文件:`_epub-src/OEBPS/text00030.html`)
- 结论依据:原文给出按一位、两位前缀拆成 n、n×n 份的递归式;示例代码中工人以 index 为初始前缀,工头只累加各工人的计数。
- 原始内容:假设我们有n台计算机,每台计算机的编号依次为1到n,那么每台计算机实际上只要计算r(n,m-1)的结果就够了,这里实际上将递归降了一级,并且让多机并行计算。