16

您为 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();
  }
};
4

4 回答 4

7

假设这是一个实时解决方案，您可以在 O(1) 中处理 ping 请求，在 O(1) 中生成当前玩家统计信息，并通过牺牲一些准确性来使用 O(num_player) 空间。关键是离散时间。

概述

基本思想是将离散的时间间隔表示为对象，并在这些对象中存储以下属性：在此时间间隔内 ping 过但此后未 ping 过的不同玩家的数量。要查询活跃用户数，请计算构成最后一分钟的最后 x 个时间间隔的加权和。

细节

首先，选择一个可接受的时间分辨率。在本例中，我选择 15 秒间隔。

维护五个 PingInterval 数据结构来表示其中的五个间隔（跨越比 1 分钟多 1 个间隔）。PingInterval 包含一个属性：计数器。这些 PingInterval 保存在 PingMonitor 中。每次玩家 ping 时，更新 PingMonitor 中的地图，将每个玩家映射到当前时间间隔。当您执行此映射时，请执行以下步骤，以维护 PingIntervals 内的计数（根据我在概述部分中描述的特征）。

  • 如果玩家已经映射到一个区间并且它是当前区间，则什么也不做。
  • 否则，如果玩家被映射到不是当前区间的区间，
    • 减少旧间隔的计数，
    • 增加当前间隔的计数，
    • 并将该玩家映射到该间隔。
  • 否则，如果玩家根本没有映射到某个区间，
    • 增加当前间隔的计数，
    • 将播放器映射到当前间隔。

（如果表示当前时间的 PingInterval 尚不存在，请将最早的 PingInterval 设置为 null，以线程安全的方式创建新的 PingInterval，然后照常继续。）

当要查询活跃用户数时，计算最后五个区间时间间隔的时间加权和。例如，如果您只进入当前时间间隔 5 秒（意味着该时间间隔的下 10 秒尚未发生），则计算此值：2/3 * 最旧时间间隔 + 4 个最新时间间隔的总和。

其他想法

五个区间非常保守；我们可以大大增加这个数字以获得更高的准确性（可能每秒一个），它仍然可以为我们节省大量资金。重要的是，我们的时代现在是离散的间隔。这意味着当我们去统计活跃用户的数量时，我们不必查看每个单独的时间（等于用户数量）；相反，我们可以查看我们预定义的 x 个时间箱。

于 2012-06-14T20:43:40.277 回答
3

我的方法是使用一个双端队列（在本文的其余部分中称为队列），所有 GUID 都被推送到观察到的位置，即按年龄排序。此外，我将使用包含指向队列中存在的任何 GUID 条目的指针的哈希图。

当一个新的 GUID 被推送到队列时，旧的条目（如果有的话）将在 hashmap 中查找，从队列中删除，并将新的条目分配给 hashmap。

随着时间的推移，队列中所有超过年龄阈值的条目都将被弹出（并从哈希图中删除）。

队列的长度（也就是活跃用户的数量）可以作为一个单独的变量来跟踪，以避免每次查询都在队列中跳跃。

要支持多个游戏，只需为每个游戏 ID 添加这样的结构。

复杂性：O(1) 观察的插入/删除（给定一个完美的散列，即没有冲突），O(1) 查询，O(n) 空间。

于 2012-06-14T19:07:46.710 回答
0

编辑：我认为这个问题不是要获得“现在有多少用户活跃”这个问题的实时答案，而是要获得历史值——下午 3:25 有多少用户活跃。我将旧解决方案保留在新解决方案之下：

所以，你想知道现在有多少用户是活跃的，每场比赛都要排队。每当您看到新的日志条目时，找出它属于哪个游戏，并将其添加到游戏队列中。每次添加后，清理队列开头的旧条目（清理时所有超过 1 分钟的条目）。

当询问游戏中的活跃用户数量时，对游戏队列进行相同的清理，并返回队列的深度。

保持将游戏映射到队列的哈希值，您得到一个 O(N) 操作，其中 N 是日志中的行数 - 每行最多处理两次 - 一次用于添加它，一次用于删除它。您还可以在每次添加和查找时进行额外的比较（当确定队列条目不够老时），但这是常数时间乘以 N。所以总共 O(N)。

之前对另一个问题的回答：看到没有那么多分钟（每天 1440 分钟），我会为每个游戏创建一个向量，每分钟都有一个插槽。

查看日志文件，为每一行获取时间，将其四舍五入到最接近的分钟，并将 1 添加到数组中的相应插槽。完成后，您将确切知道每分钟每个游戏有多少活跃用户。

复杂度 - O(N)，其中 N 是日志文件中的行数。

要支持多个游戏，只需使用哈希将游戏名称映射到其向量即可。

现在，这假设您只检查整个分钟边界（1:00:00、1:01:00 等）的活动用户。无论如何，这可能是您需要做的。

于 2012-06-14T19:12:18.027 回答
0

这将是我的答案序列：

  1. 何必？最简单的方法是按分钟计算有多少用户处于活动状态。知道这些还不够吗？
  2. 如果您真的关心最新信息，让我们按秒计算（如 Cheeken 所述）。这将精确到几分之一秒。
  3. 好的，如果实时准确性是“必要的”，并且您想就数据结构采访我，让我们使用按上次活动时间评分的一堆客户（如尤达大师所述）。
  4. 如果需要实时准确性，并且我们要在生产中执行此操作，那么让我们使用数据结构服务器 Redis。我们维护一组按上次活动时间评分的分类客户。zcount我们可以使用该命令查询在最后一分钟或最后一小时内有多少客户处于活动状态。这是有用且可靠的。
于 2012-06-15T16:06:54.210 回答