算法 – 在最后一分钟内计算活动用户的最快速/最简单的方法是什么？

你为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过的不同玩家的ping数.要查询活动用户的数量,请计算构成最后一分钟的最后x个时间间隔的加权和.

细节

首先,选择可接受的时间分辨率.在这个例子中,我选择15秒的间隔.

维护五个PingInterval数据结构,以代表其中五个间隔(跨越1个间隔超过1分钟). PingInterval包含一个属性：一个计数器.这些PingIntervals维护在PingMonitor中.每次播放器ping,更新PingMonitor内的映射,将每个播放器映射到当前时间间隔.执行此映射时,请执行以下步骤,以保持PingIntervals内的计数(根据概述部分中描述的特性).

>如果播放器已经映射到一个间隔,它是当前的间隔,什么都不做.

>否则,如果播放器映射到不是当前间隔的间隔,

>递减旧区间数,

>增加当前间隔的计数,

并将该播放器映射到该间隔.

否则,如果播放器没有被映射到间隔,

>增加当前间隔的计数,

>将播放器映射到当前间隔.

(如果PingInterval表示当前时间不存在,将最早的PingInterval设置为null,以线程安全的方式创建一个新的PingInterval,然后继续正常运行.)

当要查询活动用户数时,计算最后五个间隔时间间隔的时间加权和.例如,如果当前时间间隔只有5秒(意味着该间隔的未来10秒还没有发生),请计算此值：2/3 * 4个最新间隔的最早间隔和.

其他想法

五个间隔非常保守;我们可以大幅提高数量,以获得更高的准确性(也许每秒一次),而且仍然可以节省大量资金.重要的是我们的时代现在是离散的间隔.这意味着当我们去计算活跃用户的数量时,我们不必每个时间(等于用户数量);相反,我们可以看看我们预定义的x个时间段.