16

あなたは Zynga で働いており、さまざまなゲームで現在アクティブなプレーヤーの数を数えたいと考えています。Web サーバーはさまざまなゲームからの ping を処理し、各ユーザーは一意の GUID を持っています。一度に 1 つのゲームのアクティブ ユーザー数を照会できる必要があります。アクティブなユーザーは、直前に 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 を送信していない個別のプレーヤーの数。アクティブなユーザーの数を照会するには、最後の 1 分間を構成する最後の x 時間間隔の加重合計を計算します。

詳細

まず、許容できる時間解像度を選択します。この例では、15 秒間隔を選択します。

5 つの PingInterval データ構造を維持して、これらの間隔のうちの 5 つを表します (1 分よりも 1 つ多い間隔にまたがります)。PingInterval には、カウンターという 1 つのプロパティが含まれます。これらの PingIntervals は、PingMonitor で維持されます。プレーヤーが ping するたびに、各プレーヤーを現在の時間間隔にマップする PingMonitor 内のマップを更新します。このマッピングを実行するときは、PingIntervals 内のカウントを維持する次の手順を実行します (概要セクションで説明した特性に従って)。

  • プレーヤーがすでに間隔にマップされていて、それが現在の間隔である場合は、何もしません。
  • それ以外の場合、プレーヤーが現在の間隔ではない間隔にマップされている場合、
    • 古い間隔のカウントを減らします。
    • 現在の間隔のカウントを増やします。
    • そのプレーヤーをその間隔にマッピングします。
  • それ以外の場合、プレーヤーが間隔にまったくマッピングされていない場合、
    • 現在の間隔のカウントを増やします。
    • プレーヤーを現在の間隔にマップします。

(現在の時刻を表す PingInterval がまだ存在しない場合は、最も古い PingInterval を null に設定し、スレッドセーフな方法で新しい PingInterval を作成してから、通常どおり続行します。)

アクティブなユーザーの数を照会する場合は、過去 5 つの時間間隔の経過時間加重合計を計算します。たとえば、現在の時間間隔が 5 秒しかない場合 (その間隔の次の 10 秒がまだ発生していないことを意味します)、次の値を計算します: 2/3 * 最も古い間隔 + 4 つの新しい間隔の合計。

他の考え

5 つの間隔は非常に保守的です。精度を高めるために数値を大幅に拡大することができ (おそらく 1 秒あたり 1 つ)、それでも大幅な節約が可能です。重要な部分は、私たちの時間が離散的な間隔になっているということです。これは、アクティブなユーザーの数をカウントするときに、個々の時間 (ユーザーの数に等しい) をすべて調べる必要がないことを意味します。代わりに、事前に定義した x ビンの時間を見ることができます。

于 2012-06-14T20:43:40.277 に答える
3

私のアプローチは、観察されるすべての GUID がプッシュされる両端キュー (この投稿の残りの部分ではキューと呼ばれます) を使用することです。つまり、年齢順に並べ替えられます。さらに、キューに存在する GUID のエントリへのポインターを含むハッシュマップを使用します。

新しい GUID がキューにプッシュされると、古いエントリ (存在する場合) がハッシュマップで検索され、キューから削除され、代わりに新しいエントリがハッシュマップに割り当てられます。

時間が経過すると、年齢のしきい値を超えるキュー内のすべてのエントリがポップアウトされます (ハッシュマップから削除されます)。

キューの長さ (アクティブなユーザーの数とも呼ばれます) を別の変数として追跡し、クエリごとにキューをホッピングしないようにすることができます。

複数のゲームをサポートするには、すべてのゲーム ID にこのような構造を追加するだけです。

複雑さ: O(1) 観測の挿入/削除 (完全なハッシュ、つまり衝突がない場合)、O(1) クエリ、O(n) スペース。

于 2012-06-14T19:07:46.710 に答える
0

編集:この質問は、「現在アクティブなユーザーの数」という質問に対するリアルタイムの回答を取得することではなく、過去の値(午後3時25分にアクティブなユーザーの数)を取得することであると想定しました。私は古いソリューションを新しいソリューションの下に置いています:

したがって、現在アクティブなユーザーの数を知りたい場合は、ゲームごとにキューを保持します。新しいログエントリが表示されたら、それが属するゲームを見つけて、ゲームのキューに追加します。追加するたびに、キューの先頭で古いエントリをクリーンアップします(クリーンアップ時に1分より古いすべてのエントリ)。

ゲーム内のアクティブユーザーの数を尋ねられたら、ゲームのキューで同じクリーンアップを実行し、キューの深さを返します。

ゲームをキューにマッピングするハッシュを保持すると、O(N)操作が得られます。Nはログ内の行数です。各行は最大2回処理されます。1回は追加用、もう1回は削除用です。また、追加とルックアップごとに追加の比較を行います(キューエントリが十分に古くないと判断した場合が、これは一定の時間時間Nです。つまり、全体でO(N)です。

他の質問に対する以前の回答:それほど多くの分(1日1440分)がないことを確認して、各ゲームのベクトルを作成し、1分ごとにスロットを作成します。

ログファイルに目を通し、各行の時間を取得し、最も近い分に切り上げて、配列の適切なスロットに1を追加します。完了すると、毎分、各ゲームのアクティブユーザーの数が正確にわかります。

複雑さ-O(N)。Nはログファイルの行数です。

複数のゲームをサポートするには、ハッシュを使用してゲームの名前からそのベクトルにマップします。

これで、これは、分単位の境界(1:00:00、1:01:00など)でのみアクティブユーザーをチェックすることを前提としています。これはおそらくあなたがとにかくする必要があることです。

于 2012-06-14T19:12:18.027 に答える
0

これが私の一連の答えになります。

  1. なぜわざわざ?アクティブなユーザーの数を分単位で数えるのが最も簡単です。それを知るだけでは十分ではありませんか?
  2. 最新の情報が本当に気になる場合は、秒単位のビンで数えましょう(Cheekenによる説明)。これは、ほんの一瞬の精度になります。
  3. さて、リアルタイムの精度が「必要」であり、データ構造について私にインタビューしたい場合は、最後のアクティビティ時間(マスターヨーダによって説明されている)によってスコアリングされた顧客のヒープを使用しましょう。
  4. リアルタイムの精度が必要で、これを本番環境で行う場合は、データ構造サーバーRedisを使用してみましょう。前回のアクティビティ時間でスコア付けされた、ソートされた一連の顧客を維持します。このコマンドを使用して、過去1分間または過去1時間にアクティブだった顧客の数を照会できますzcount。これは便利で信頼性があります。
于 2012-06-15T16:06:54.210 に答える