最近想起来之前写的一个比较有意思的程序，简单说一说吧~
某互联网黑产需求
之前在帮某“互联网黑产大佬”干苦力的时候有这么一个需求，如果读者玩过某个集换式卡牌手机游戏的话应该知道卡牌的概念。手游卡牌的黑产生意实际上是通过 http 接口去刷别人的初始卡牌组合(就是看脸抽卡)。在刷卡的过程中可能会刷出一些价值比较高的初始号从而拿来挂在什么地方赚钱，这个初始号里相当于预先就存在了一些稀有的卡片，而省去了非洲人百抽不出 SSR 的窘境。而用户的购买过程则是需要提供其心仪的卡片，在已有的卡组里查询符合自己搜索条件的对应卡片。
啊，那换成微博的共同关注？
看不懂上面这段没有关系，我们把这个场景稍微修改，最近微博因为小鲜肉的恋爱爆料挂得比较惨，我们以微博的一个场景来举例：
用户 A 关注了 N 个人，把这些被 A 关注的用户 id 计为集合 X。
用户 B 关注了 M 个人，把这些被 B 关注的用户 id 计为集合 Y。
现在我想知道用户 A 和用户 B 共同关注了哪些用户，实际上就是求
X 和 Y 的交集。要怎么实现呢？
首先我们的数据是一定要落地的，那么这些关注对象一定要在 mysql 里进行存储。实际上用户的关注对象也就是一堆 不可重复 的用户 id，我们如果要画 ER 图的话，会画出一个简单的 1 对 X 的 ER 图。设计起来也不太麻烦，简化掉不需要的内容，需要下面两张表：
users : id, name, status
follows : id, user_id, follow_user_id, status
现在要求两者的交集手段就多了，可能对 sql 比较熟悉的人首先会这么做：
select follow_user_id from follows where user_id = A
intersect
select follow_user_id from follows where user_id = B
当然，这么做也不是不可以。但你最好去了解一下 db 一般是怎么实现这个 intersect 的。实际上 intersect 操作符在 MySQL 里并不支持。。。想要实现类型的功能可能需要简单修改为 not in。但无论是哪种写法，在数据库层面都是一个 O(M * N) 的算法。
我们把场景复杂化，要同时求 5 个人，甚至 100 个人的共同关注。你要让数据库去做这天文数字的循环么？显然不太靠谱。
自然而然地，我们开始琢磨把这些数据从存储系统里拉到内存里进行计算。这样问题就变成了在内存中进行 N 个集合交集计算的算法问题。
在内存里计算交集
还是先看简化版的问题，如何求两个集合的交集：
分两种情况：
1.集合有序，交集算法其实就是简单的双指针移动和判断，可以在 O(M+N) 的时间复杂度情况下搞定。
2.集合无序，虽然鸡贼如你一定已经在网上查到了各种看起来高大上的 bitmap 来求交集。不过还是需要思考一下，我们的黑产在线服务器可能只有 1GB 的内存。。。根本没有空间给你挥霍，虽然我们的关注对象的 id 值域很大，但是关注列表本身不会太大，毕竟微博似乎也有关注的限制，可能 5000 ？(原谅一个几乎不上微博的小白)这时候比较合适的求交集的办法还是用哈希表。哦，如果是 golang，那么比较合适的是 map。一遍循环把关注列表 X 入 map，再一遍循环用 Y 中的元素查表然后把交集直接输出或者存到别的什么地方。
推而广之，现在我们的多个列表来啦！
这里我问到的不少人会给出的第一种算法还是两两求交集，然后用交集再和后面的集合两两求交集，是简单的递归和局部子问题的思想。如果这么做的话会导致一个问题，每次两两进行计算，我都需要一个专门的哈希表记录在前一集合中已出现过的元素。你看我们这么穷，服务器只有 1G 内存，你反复地整一大堆哈希表，我的内存要爆了啊！能不能不要整这么多哈希表？
当然是可以的。仔细想想上面那个场景，微博的关注对象的 id 实际上是不能重复的，如果你要求 100 个关注列表所共有的那些 id，而这些 id 在每个列表中只出现且最多出现 1 次，那么问题实际上就变成了找出这样的一些 id，这个 id 在所有元素中出现了 100 次。接下来问题就简单了：
map[int]int
还是偷懒不写了吧~
上面这是微博的共同关注的场景，回到我们卡牌和卡牌组的场景，实际上这些列表中是有可能有重复的卡牌 id 的，也就是说，我的卡组可能是下面这样的形式：
[1, 3, 4, 4, 5, 7, 8, 8]
这样上面的简单计数法就不灵了，实际上只需要做简单的修改就可以支持这个需求，具体就交给读者去想啦。如果我们的需求又变了(WTF)，我们需要支持用户按照卡片的数目去进行查询要怎么办呢？也交给读者去想吧。
在不需要按照计数查询的前提下，上面的这些需求我们还可以很方便的让 redis 帮我们来做(antirez 万岁)。
推而广之
也许读完这篇文章你会觉得文中提到的场景和算法无比地 low，不要急，首先你需要用 15 行代码正确地实现多排序列表交集，其次需要保证时间复杂度为 O(N*M)，N 是列表的个数，M 呢？卖个关子，请读者自行探索。另外，多列表交集还是搜索引擎较核心的算法之一，如果你依然兴趣饶饶，那不妨再思考一下：
最简单的 Bi-Gram 分词的搜索引擎的倒排列表，是怎么存储的
在 Bi-Gram 的搜索引擎中进行文档搜索时，我是怎么根据倒排列表找到对应的 doc-id 的呢？
以上~
