2

定数整数xおよびtが与えられた場合、引数をとらず、関数が過去t秒間にx回呼び出された場合にtrueを返す関数を記述します。

これは、可能なアルゴリズムの擬似コード/ C ++実装ですが、それが正しい/効率的かどうかはわかりません。

const int x;
const int t;
vector<long> v;
boolean countNumberOfTimesBeenCalled(){
    int numberOfCallsInLastTSeconds=0;
    v.push_back(System.currentTimeInMillis());
    for(int x=0; x<v.size();x++){
        if((v.at(x)>=(System.currentTimeInMillis()-1000*t))&&(v.at(x)<=System.currentTimeInMillis())
            numberOfCallsInLastTSeconds++;
    }
    if(numberOfCallsInLastTSeconds==x)
        return true;
    else
        return false;
}

誰かが代替案を提案できますか？

4

2 に答える 2

3

以前のすべての呼び出しの完全なログを保持する必要はありません。最後の x 回の呼び出しがどのくらいの期間にわたって行われたかを知る必要があるだけです。

const int x;
const int t;
bool have_we_made_enough_calls_lately() {
    static deque<int> times;
    times.push_back(current_time_in_msec());
    if (times.size() > x)
        times.pop_front();
    return times.back() - times.front() <= 1000 * t;
}

編集：他の回答を確認すると、質問があいまいであることがわかりました。少なくともx 回の呼び出し (私が想定したもの) または正確にx 回の呼び出し (他の人が想定したもの)があった場合に true を返すかどうかは明確ではありません。

于 2012-11-25T22:36:57.867 に答える
0 
bool calledXTimesInLastTSeconds() {
   static deque<long> last_calls;
   long time = currentTimeInMillis();

   // clear last calls
   long last_call_to_consider = time - 1000*t;
   while (last_calls.front() < last_call_to_consider)
      last_calls.pop_front()

  last_calls.push_back(time);
  return last_calls.size() == x;
}

時間計算量は償却定数です。

編集:これは、正確にx 呼び出しをチェックする方法です。==xこれを ( に変更することにより)少なくとも x 回の呼び出しに単純に変更できたとしても>=x、メモリ使用量には一定の上限があるため、Ross Smith からの回答の方が優れています。

于 2012-11-25T22:37:16.587 に答える