AC之路 序

不知不觉就要到大三了,也玩过很多东西,但总感觉缺乏新的挑战,到达了一个瓶颈。

于是想要隐居深山,闭关修炼,回到计算机的本源,更多跟深地去死磕自己从前从来没有好好去探索的CS领域,SO HERE I AM,

阅读更多

LeetCode题解:最长回文串之manacher算法

manacher 俗称马拉车算法,也是本文的主角,是一种能够将最长回文串的求解复杂度降低到 O(N) 的一种高效算法,
当我第一次见到求解最长回文串的题目时,首先采用的就是暴力解法,O(N平方) 复杂度遍历所有可能的串,然后再用 O(N) 的时间来求回文串的最大长度,使用 map 存储各个下标对的回文情况尽管能减少一部分计算,
但是显然这种方式时间复杂度过高,部分 case 容易超时

这种算法的大概思路如下:

  • 通过插入一些符号简化奇偶个数和边界对判断回文串的干扰
  • 中心点的整个边界(除去中心点)的一半恰好等于中心点的最大回文串长度
  • 利用大回文串边界内的位置的最大回文串个数以大中心点对称的规律大大简化计算量
阅读更多

无缓冲通道引发的BUG

最近在刚玩具级的 MapReduce ,其中充斥着大量的并发编程的代码,稍有不慎就可能导致 Map 或者 Reduce 的时候遭遇到未知的阻塞状态 (Blocking),导致整个系统无法按照计划
处理所有的 Task 并将输出的结果写入文件,经过一番 DEBUG ,发现竟是无缓冲通道的基本用法没有掌握熟练,当遇上多个 channel 协作的时候就难免会踩坑

先说重点:

无缓冲通道要求发送方和接收方同时准备好,才能”进行”发送和接收操作

show me the code

阅读更多

分布式初探 Distributed 101

什么是分布式系统?

使用多机来处理单机相同问题的系统

多点存储,多点计算

为什么需要分布式系统?

解决日益增长的存储资源和计算资源占用的问题,分散系统压力

阅读更多

在 Gin 中实践TDD测试API

如果这篇文章能够从此让你放下手中的快递员,从此开始做一个 TDD First 的 programmer ,那么本文的目的也就达到了

Why TDD is so important?

TDD 的重要性最直接的体现就是 No guessing 和 Robust,一切都在测试的意料之中,同时也确保你自己考虑清楚了所有的情况。而不是直接将你的代码或API接口
丢给测试人员,然后根据反馈再继续修改,这样一来一回实际上十分降低效率,那么当我们意识到这一点时,为什么我们不能自己先将大部分的BUG利用测试事先发现并改掉呢?

其次,当系统的规模不断变大,新的功能不断加入进来,这时系统的单元测试有利于我们进行系统的重构,通过代码覆盖率定位到死代码(Dead Code),通过查看调用次数将一些
已经非常健壮的代码独立成包或 module,实现增量编译等,在避免臃肿,加快构建速度等改善系统腐化的问题中,测试绝对是功不可没。

阅读更多