C++で解く「関数の排他時間」問題 ― スタックによる効率的な計算方法

問題の概要

シングルスレッドのCPU上でいくつかの関数を実行する状況を考えてみましょう。各関数には 0 から N-1 までの一意な ID が割り振られており、関数の開始・終了のタイミングを記録したログがタイムスタンプ順に与えられます。

各ログは「{function_id}:{"start" | "end"}:{timestamp}」という形式の文字列です。たとえば「0:start:3」は ID 0 の関数がタイムスタンプ 3 の始まりの時点で実行を開始したことを、「1:end:2」は ID 1 の関数がタイムスタンプ 2 の終わりの時点で完了したことを意味します。ここでいう排他時間（exclusive time）とは、その関数自身が実際に処理に費やした時間単位数のことです。

入力が n = 2、logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] の場合、出力は [3, 4] になります。処理の流れを追うと、まず関数 0 が時刻 0 の始まりに起動し、2 単位の時間を実行して時刻 1 の終わりまで進みます。次に関数 1 が時刻 2 の始まりに起動し、4 単位の時間を実行して時刻 5 で終了します。その後、関数 0 が時刻 6 の始まりに再び実行され、時刻 6 の終わりに完了するため、ここで 1 単位の時間を消費します。したがって、関数 0 の合計実行時間は 2 + 1 = 3 単位、関数 1 は 4 単位となります。

解法のアプローチ：スタックで実行状態を管理

この問題はスタックを使うことで効率よく解けます。手順は以下の通りです。

• サイズ n の結果用配列 ret と、整数を格納するスタック st を用意する
• j = 0、prev = 0 で初期化する
• i を 0 からログ配列のサイズ - 1 までループする
  • temp = logs[i] とし、j = 0、id = 0、num = 0、type = 空文字列で初期化する
• temp[j] がコロン（:）ではない間、id = id * 10 + temp[j] の数値として j を 1 増やす（関数 ID を解析）
• j を 1 増やす
• temp[j] がコロンではない間、type に temp[j] を連結して j を 1 増やす（start / end の種別を解析）
• j を 1 増やす
• j が temp のサイズ未満である間、num = num * 10 + temp[j] の数値として j を 1 増やす（タイムスタンプを解析）
• type が start の場合
  • スタックが空でなければ、ret[スタックの先頭要素] に num - prev を加算する
  • id をスタックにプッシュし、prev = num とする
• それ以外（end の場合）
  • x = スタックの先頭要素を取り出してポップする
  • ret[x] に (num + 1) - prev を加算する
  • prev = num + 1 とする
• 最後に ret を返す

なぜ (num + 1) を使うのか

end ログのタイムスタンプは「その時刻の終わり」を表すため、終了処理では (num + 1) - prev を加算します。一方、start ログのタイムスタンプは「その時刻の始まり」を表すので、開始処理では num - prev をそのまま加算すればよいのです。この違いを意識することが、正確な排他時間を計算するうえでのポイントになります。

C++での実装例

以下のコードで実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
       vector <int> ret(n);
       stack <int> st;
       int id, num;
       int j = 0;
       string temp;
       string type;
       int prev = 0;
       for(int i = 0; i < logs.size(); i++){
          temp = logs[i];
          j = 0;
          id = 0;
          num = 0;
          type = "";
          while(temp[j] != ':'){
             id = id * 10 + (temp[j] - '0');
             j++;
          }
          j++;
          while(temp[j] != ':'){
             type += temp[j];
             j++;
          }
          j++;
          while(j < temp.size()){
             num = num * 10 + temp[j] - '0';
             j++;
          }
          if(type == "start"){
             if(!st.empty()){
                ret[st.top()] += num - prev;
             }
             st.push(id);
             prev = num;
          } else {
             int x = st.top();
             st.pop();
             ret[x] += (num + 1) - prev;
             prev = num + 1;
          }
       }
       return ret;
    }
};
main(){
    vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
    Solution ob;
    print_vector(ob.exclusiveTime(2, v));
}

入力

2
["0:start:0","1:start:2","1:end:5","0:end:6"]

出力

[3, 4]

計算量について

ログ全体を一度走査するだけで処理が完結するため、時間計算量は O(L)（L は全ログの文字数の総和）、空間計算量は O(n)（スタックと結果配列の分）となります。関数呼び出しがどれほど深くネストしていても、スタックによって実行中の関数を正しく追跡できるため、線形時間で各関数の排他時間を求めることができます。