演算法 – 在最後一分鐘內計算活動使用者的最快速/最簡單的方法是什麼？

你為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個時間段.