博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Rocket - util - PrefixSum
阅读量:5878 次
发布时间:2019-06-19

本文共 552 字,大约阅读时间需要 1 分钟。

 
简单介绍PrefixSum的实现。
 
 
1. 基本介绍
 
把一个序列从前向后逐个执行迭代(assocOp),每针对一个元素执行一遍迭代,针对一整行执行一次迭代(layerOp)。
 
2. PrefixSum
 
a. layers:抽象方法,返回层数,等于layerOp执行的次数;
b. idLayer: 默认的layerOp,即没有动作,把输入原样返回;
 
3. RipplePrefixSum
 
每次只使用前一个元素对当前元素执行一次迭代,其他元素不进行迭代动作。
 
apply重构之后为:
 
a. offset只当前针对第几个元素进行迭代,当迭代到最后一个元素停止:
 
 
b. 只针对当前元素执行assocOp:
 
 
offset每次递增1,当offset与当前元素序号相等时,才执行assocOp;
 
c. 当针对当前元素执行完assocOp后,执行一次layerOp:
 
 
d. 把layerOp的结果,带入下一次迭代:
 
 
 
一个迭代过程的例子如下:
 
实际执行的例子如下:
 
4. DensePrefixSum
 
提升迭代效率,每次迭代一半。
 
迭代过程如下:
 
执行过程如下:
 
5. SparsePrefixSum
 
 
6. 附录
 

转载于:https://www.cnblogs.com/wjcdx/p/10992216.html

你可能感兴趣的文章
CSS 技巧篇(二):visibility:hidden和display:none的区别
查看>>
终于搞定了vertical-align:baseline对齐的问题
查看>>
解析vue2.0的diff算法
查看>>
HTML标签
查看>>
理解JS中的Event Loop机制
查看>>
转载:字符编码笔记:ASCII,Unicode和UTF 8
查看>>
修复看不懂的 Console Log
查看>>
Android跨进程通信 AIDL使用
查看>>
ajax常见面试题
查看>>
细数Java的语法糖(一): 用于字符串拼接的 "+" 运算符
查看>>
java B2B2C Springcloud仿淘宝电子商城系统-Zipkin服务端配置
查看>>
函数式点滴--高阶函数及抽象
查看>>
Web聊天工具的富文本输入框
查看>>
动手实现AsyncTask v1.1
查看>>
java 异步查询转同步多种实现方式:循环等待,CountDownLatch,Spring EventListener,超时处理和空循环性能优化...
查看>>
Runc和CVE-2019-5736
查看>>
JS专题之数组展开
查看>>
javaScript原型、原型链
查看>>
55. Jump Game
查看>>
理解AJAX
查看>>