并发编程趣题: 制造一氧化二氢

最近leetcode的算法题中新增加了一个并发问题的分类, 目前提供了四道题,一道简单题,两道中级题和一道Hard题。这是leetcode尝试在并发算法分类的一个尝试,虽然目前还在摸索阶段,有的题目可以通过作弊的方式提供高分答案,有的即使是通过了测试,但是其实还是有并发的问题的,只不过测试用例没有覆盖到而已。

这也说明了并发编程并不是一件很容易的事情,但是还是很高兴leetcode能在这个方面往前走一步。其中的最难的那道题,看它第一眼的时候觉得还是比较简单的,但是仔细思考后却发现实现它并不是一件很容易的事情,即使目前的接受率才51.9%,但其实已接收的提交有很多还是有并发的问题的,只不过由于验证的问题并没有验证出来。

阅读全文

局部敏感哈希介绍

传统的Hash当源数据有些许的变化的时候生成的哈希值差异也非常的大, 比如:

1
2
3
4
5
6
7
8
9
10
func main() {
s1 := []byte("你好世界")
s2 := []byte("你好,世界")
hash1 := md5.Sum(s1)
hash2 := md5.Sum(s2)
fmt.Println(hex.EncodeToString(hash1[:]))
fmt.Println(hex.EncodeToString(hash2[:]))
}

s1的哈希值是65396ee4aad0b4f17aacd1c6112ee364、s2的哈希值是27444ee2d245c3e8e11ed8b9b035c43b,源数据仅仅是一个逗号的区别,但是哈希值完全不一样。这是我们使用Hash的常见的场景,输出的哈希值经常被称为消息摘要(message digest)或摘要(digest)。

局部敏感哈希(Locality-sensitive hashing, 简称LSH)则不同, LSH则希望相似的源数据计算出来的哈希值越相近越好。
LSH经常用在判重、文章摘要、聚类、相似搜索、近邻查找等场景, 用来减少高维度的数据的维度,相近的数据放在同一个桶中。 比如大规模异常滥用检测:基于局部敏感哈希算法——来自Uber Engineering的实践

阅读全文

<转> 基数估计算法概览

转自淘宝张洋的基数估计算法概览
翻译自Damn Cool Algorithms: Cardinality Estimation.
在淘宝的应用考虑参考 基数估计算法在大数据场景下的应用.

假如你有一个巨大的含有重复数据项数据集,这个数据集过于庞大以至于无法全部放到内存中处理。现在你想知道这个数据集里有多少不同的元素,但是数据集没有排好序,而且对如此大的一个数据集进行排序和计数几乎是不可行的。你要如何估计数据集中有多少不同的数据项?很多应用场景都涉及这个问题,例如设计数据库的查询策略:一个良好的数据库查询策略不但和总的数据量有关,同时也依赖于数据中不同数据项的数量。

我建议在继续阅读本文前你可以稍微是思考一下这个问题,因为接下来我们要谈的算法相当有创意,而且实在是不怎么直观。

阅读全文