Mas*_*oda 15 algorithm time-series data-structures
你为Zynga工作,想要计算不同游戏当前活跃玩家的数量.您的Web服务器处理来自许多不同游戏的ping,每个用户都有一个唯一的GUID.必须能够一次查询一个游戏的活跃用户数.活跃用户是那些在最后一刻获得ping的用户.
日志行连续进入Web服务器:
10.1.12.13 - - "http://zynga.com/ping?guid=<guid>&game=<gameID>" -
计算活跃用户的最快捷/最简单的方法是什么？请使用一些代码建议45分钟的答案.
我的版本
// web server interface, every time ping comes in count() will be called
// void count(String gameId, String guid)
// int getNumberActivePlayers(String gameId)
struct Record{
String gameID;
String guid;
};
class PingStorage{
private:
max_heap<long, Record> storage;
public:
// O(log(n))
// n = total number of elements in storage
void count(String gameId, String guid){
long currentTimeStamp = getUnixTimeStamp();
Record rec ;
rec.gameId = gameId;
rec.guid = guid;
storage.add(currentTimeStamp, rec);
}
//N = numner of records in last ,minutes in storage
//O(N)
int getNumberActivePlayers(String gameId){
map<String, Set<string> > game2user;
long tillTimeStamp = getUnixTimeStampNow() - 60;
while(true){
pair<long, Record> rec = storage.getMax(); //O(1)
if(rec.first <= tillTimeStamp) break;
Set<String> temp = game2user[rec.gameid]; //O(1)
temp.add(rec.userid); //O(log(N)) - O(1)
}
return game2user[gameID].size();
}
};
假设这是一个实时解决方案,您可以在O(1)中处理ping请求,在O(1)中生成当前播放器统计信息,并通过牺牲一些准确性来使用O(num_player)空间.关键是要定时化.
概观
基本思想是将离散时间间隔表示为对象,并在这些对象中存储以下属性:在此时间间隔内未执行ping的不同玩家的数量.要查询活动用户数,请计算构成最后一分钟的最后x个时间间隔的加权总和.
细节
首先,选择可接受的时间分辨率.在这个例子中,我选择15秒的间隔.
维护五个PingInterval数据结构以表示其中五个间隔(跨越1个间隔而不是1分钟).PingInterval包含一个属性:一个计数器.这些PingIntervals在PingMonitor中维护.每次玩家ping,都会更新PingMonitor中的地图,将每个玩家映射到当前时间间隔.执行此映射时,请执行以下步骤,以维护PingIntervals中的计数(根据概述部分中描述的特征).
(如果尚未存在表示当前时间的PingInterval,请将最旧的PingInterval设置为null,以线程安全的方式创建新的PingInterval,然后照常继续.)
如果要查询活动用户数,请计算最后五个时间间隔的时间过去加权总和.例如,如果距当前时间间隔仅5秒(意味着该间隔的下一个10秒尚未发生),则计算此值:2/3*最旧间隔+ 4个最新间隔的总和.
其他想法
五个间隔是非常保守的; 我们可以大幅度扩大数量以获得更高的准确度(可能是每秒一次),它仍然可以为我们节省大量成本.重要的是,我们的时代现在是不连续的时间间隔.这意味着当我们计算活跃用户的数量时,我们不必查看每个单独的时间(这等于用户数); 相反,我们可以查看我们预定义的x个时间段.
我的方法是使用双端队列（在本文的其余部分中称为队列），所有 GUID 都被推送到观察到的位置，即按年龄排序。此外，我将使用一个哈希图，其中包含指向队列中存在的任何 GUID 条目的指针。
当新的 GUID 被推送到队列时，将在哈希映射中查找旧条目（如果有），从队列中删除，并将新条目分配给哈希映射。
随着时间的推移，队列中超过年龄阈值的所有条目都将被弹出（并从哈希图中删除）。
队列的长度（也称为活动用户数量）可以作为单独的变量进行跟踪，以避免每次查询都在队列中跳转。
要支持多个游戏，只需为每个游戏 ID 添加这样的结构即可。
复杂性：O(1) 插入/删除观察（给定完美散列，即没有冲突）、O(1) 查询、O(n) 空间。