《全栈工程师修炼指南》学习笔记 - 算法
2023-03-14 本文已影响0人
VioletJack
在全栈开发中,包含了很多算法的运用。
流量控制
在解决实际问题的时候,我们面临的问题往往是复杂的、多样的。因此,我们可以考虑能不能先简化问题,再来尝试映射到某一个数学模型上去。那些先不考虑的复杂条件,有的可能就可以忽略掉的,而有的为了思路的清晰。一开始我们可以先忽略,有了解题的方法原型后,再初步加回来考虑。
- 简单计数法:限定每分钟只能进入 10000 条数据
- 滑动窗口:任意一分钟的窗口内数据只能有 10000 条
- 时间队列:维护一个长度不超过 10000 的时间戳队列
- 请求数队列:维护一个长度为 60 的队列,记录每一秒的请求数。保证整个队列请求数总和不超过 10000
- 漏桶算法:我们每次都可以根据流速以及上一次的流量检测时间,获知在考虑漏水的情况下,如果接纳当前请求,那么桶中将达到怎样的水位,是否会超过 burst。如果不超过,就允许此次访问,反之拒绝。
- 令牌桶算法
无损压缩
无损压缩的基本原理就是利用数据的重复性。
- 哈夫曼编码:通过获取字符出现的数量构建哈夫曼树,然后将数据按照哈夫曼树的编码组合。其中字符串出现频率越高、编码串的长度就越短。
- RLE 编码:利用字符的重复来表示压缩数据,即
5A2B1C7D
。数据可以以特定的方式经过 RLE 编码后,在使用哈夫曼等方式进一步压缩。 - 算术编码:通过数据出现的概率来进行编码。最后一段编码前的数据,最后编码成了一个数。