如何快速写出一个陌生人推荐系统
如何快速写出一个陌生人推荐系统
在社交游戏中，除了和好友互动，经常还会设计陌生人互动的游戏环节。下面两张图分别是QQ水浒和全民农场的陌生人推荐界面。
QQ水浒陌生人界面
全民农场陌生人界面
那么，陌生人推荐系统一般是怎么做的呢？下面以全民农场的陌生人推荐系统为例来阐述如何快速构建一个陌生人推荐系统，由于采用了boost::multi_index库，整个推荐系统代码在400行左右，非常简洁。
首先，我们简单介绍一下全民农场的陌生人推荐系统规则：
1. 等级相近
2. 城市相近
3. 性别相反
4. 活跃用户
一个简单的方法是用列表存储所有近期登录的玩家的数据，查询的时候对遍历每个玩家，并过滤。然而这种方式效率比较低下，查询10个玩家平均需要遍历的玩家个数是：
10 * 100 (假设100阶等级) * 50(假设50个城市) * 2 (男女各半)
= 100000
显然简单地列表方式查询效率低下，所以我们要做索引，这里不得不提到multi_index库，对于这个库的介绍只用一句话：multi_index是一个模拟关系型数据库索引结构的容器（ The concept of multi-indexing over the same collection of elements is borrowed from relational database terminology and allows for the specification of complex data structures in the spirit of multiply indexed relational tables where simple sets and maps are not enough），其内部实现相当于多个std::map组合，但比std::map组合更高效，更方便。
考虑到性别字段的值域比较小，我们就不用对它做索引了。我们对等级、城市、和上次登录时间做索引，考虑等级比城市的优先级更高，我们决定对<等级, 城市>做复合索引(你没听错，就是关系型数据库里的复合索引)。基于上述考虑，我们的陌生人推荐系统的数据结构如下图所示：
struct stranger_info
{
pod_open_id_t open_id;
pod_city_t city;
uint32_t ts;
uint32_t level;
uint32_t gender;
};
typedef bmi::multi_index_container<
stranger_info,
bmi::indexed_by<
bmi::ordered_non_unique<bmi::tag<tag_level_city>,
bmi::composite_key<stranger_info,
bmi::member<stranger_info, uint32_t, &stranger_info::level>,
bmi::member<stranger_info, pod_city_t, &stranger_info::city> >
>,
bmi::ordered_non_unique<bmi::tag<tag_ts>, bmi::member<stranger_info, uint32_t, &stranger_info::ts> >,
bmi::ordered_unique<bmi::tag<tag_open_id>, bmi::member<stranger_info, pod_open_id_t, &stranger_info::open_id> >
>,
stranger_info_allocator_t
> stranger_info_db_t;
上述代码定义了两个数据结构stranger_info和stranger_info_db_t。stranger_info描述了玩家的信息，stranger_info_db_t看上去比较复杂，其实非常简单，它定义了一个stranger_info的容器，该容器对stranger_info结构的open_id, city, ts, level这几个字段做索引。
加上索引后，陌生人推荐系统的规则就很容易满足了：
1. 等级相近
2. 城市相近
按tag_level_city这个索引查找到最匹配的玩家，然后以该玩家为基准，前向/后向遍历，找到推荐的陌生人。
3. 性别相反
在按tag_level_city遍历过程中，对性别不满足的过滤掉
4. 活跃用户
定时按tag_ts从头遍历，删除ts过小的节点。
自此，陌生人推荐系统就介绍到这里，附近里是陌生人推荐系统的实现文件。需要注意的是，在真实的系统中，stranger_info有一个handler字段，这个字段相当于一个下标，客户端请求时把上次的handler传过来，服务器从该handler往后取数据，实现分页功能。
具体实现见附件