浮点数 Kahan求和

缘起

在计算机组成与体系结构中，浮点数是相当重要的存在. 很多超算性能测试中——每秒浮点运算次数是一个相当重要的指标. 浮点运算性能可以直观地反映一个cpu的计算能力，注意是“计算能力”，可是学过编程的人都知道，占代码量80%的是由if ，while， for 等等构成的分支语句，这些语句对cpu的浮点运算要求不高，可以说没什么要求，但要求有大量的分支预测机制，以加快速度。真正对浮点要求高的是视频压缩，场景的渲染，光线散射的计算等等。那么计算机中对浮点数的存储是怎么样的呢? 以及所谓的精度丢失是怎么回事? 如何解决? 我们来谈谈这个话题. 本文汲取了【1】~ 【5】中的营养.

Read More

leetcode 28 实现 strStr() 后缀数组

缘起

【1】中想校验一下我的后缀数组的板子的愿望再次落空——被T掉了，不论是dc3还是da（da的性能更差）. 其实并不难想象——因为da是nlogn的算法，一旦字符串的规模达到了1e6, 则nlogn将达到恐怖的2000w! 而dc3即便是线性算法（在1e6级别上的表现远优于da）, 但是【2】中说了，它的常数较大. 算法的复杂度依旧不低. 所以基本可以断言, 在精确匹配问题上, kmp、bm、karp-rabin等算法是远胜于后缀数组、后缀树算法的. 毕竟后者还要先针对文本串（文本串的长度一般远大于模式串）构建一个东西，而kmp是针对模式串构造一个东西（kmp复杂度为O(n+m), 而且常数几乎为1），这复杂度当然不可同日而语~ 但是我还是不甘心——因为还是要试一下我的板子对不对啊~ 于是找到”比较弱”的leetcode. 打算找上面一道题目来验证一把我的后缀数组板子的正确性. leetcode 28 实现 strStr()

Read More