离散图论1:基础
Posted on
Edited on
01背包算法
Posted on
Edited on
背包问题(Knapsack problem)是一种组合优化的NP完全(NP-Complete,NPC)问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的,但是利用动态规划,我们可以以伪多项式时间复杂度求解背包问题。
背包问题有以下几种分类:
- 01背包问题
- 完全背包问题
- 多重背包问题
MYSQL逻辑架构
Posted on
Edited on
回表查询和覆盖索引
Posted on
Edited on
摩尔投票法最佳实践
Posted on
Edited on
MYSQL 索引选择性陷阱
Posted on
Edited on
布隆过滤器的理论基础及Redisson实现
Posted on
Edited on
如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表
,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表
,Hash table)的数据结构。它可以通过一个Hash函数
将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率
是比较低的。
缓存一致性方案
Posted on
Edited on
分布式锁的实现
Posted on
Edited on