详解布隆过滤器

一、引言假设我们想要开发一个邮件系统,那么如何实现垃圾邮件的过滤呢。 最简单的办法就是把确定为是垃圾邮件的地址都保存起来,存入黑名单中。当用户接收到黑名单地址的邮件时,直接将邮件归类到垃圾箱中。 垃圾邮件的地址数量可能是巨大的,因此除了被存储在数据库中,程序实际使用的时候一定是需要借助缓存的。不论是使用本地缓存还是内存缓存,当数据量达到一定数量级时,都是不太合适的。 咳咳,如果你的数量级连百万...

热度算法和个性化推荐

今日头条的走红带动了“个性化推荐”的概念,自此之后,内容型的产品,个性化算法就逐渐从卖点变为标配。伴随着“机器学习”,“大数据”之类的热词和概念,产品的档次瞬间提高了很多。而各种推荐算法绝不仅仅是研发自己的任务,作为产品经理,必须深入到算法内部,参与算法的设计,以及结合内容对算法不断“调教”,才能让产品的推荐算法不断完善,最终与自己的内容双剑合璧。 本文以新闻产品为例,结合了我之前产品从零积累用户...

字符串的模式匹配(KMP)算法

一、背景给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。 Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。 在继续下面的内容之前,有...

最长上升子序列(LIS)算法

理解:该子序列中后一项都比前一项大,例如有序列2 7 1 5 6 4 3 8 9,则最长上升子序列为2 5 6 8 9。 具体应用:用于确定一个代价最小的调整方案,使一个序列变为升序。只需要固定LIS中的元素,调整其他元素即可。 动态规划实现 O(n2)我们将序列存入数组a中,定义一个dp数组,存放最大长度。 2 7 1 5 6 4 3 8 9 我们能够得出一个规律: dp[i] = 前面v...

最长公共子序列(LCS)算法

一、最长公共字串与最长公共子序列1.1 最长公共子串(Longest Common Substirng)子串是串的一个连续的部分,子串中字符的位置必须连续。 例如:有两个字符串ABCBDAB 和 BDCABA,则它们的最长公共子串是:AB。 1.2 最长公共子序列(Longest Common Subsequence,LCS)子序列是从串中去掉任意的元素而获得新的序列,子串中字符的位置不必连续。 ...

最小生成树(Prim)算法

算法思想 假设G=<V,E>是连通图,TE是G上最小生成树中边的集合。 算法从U={u0}(u0∈V),TE={ }开始,任取一个顶点u0作为开始点。 重复执行下述操作:在所有u∈U, v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。 注意:选择最小边时,可能有多条同样权值的边可选,此时任选其一。 代码实现12345...

最短路径(Dijkstra)算法

一、算法功能给定一个出发点(单源点)和一个有向网G=(V, E), 求出源点到其它各顶点之间的最短路径。 二、算法思想(1)把图中顶点集合分成两组,第一组为集合S,存放已求出其最短路径的顶点,第二组为尚未确定最短路径的顶点集合是V-S(令W=V-S),其中V为网中所有顶点集合。 (2)按最短路径长度递增的顺序逐个把W中的顶点加到S中,直到S中包含全部顶点,而W为空。 (3)在加入的过程中,总保持从...
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×