Exclusive Execution Time of Functions
Statement
Let n be the number of functions running in a single-threaded CPU. Also let logs be an execution log, where each log is a string with format [function id]:[start | end]:[timestamp]. Compute the exclusive time of functions in the program. The exclusive time is the sum of execution times for all calls to a specific function.
Constraints
- 1 ≤
n≤ 100 - 1 ≤
logs.length()≤ 500 - 0 ≤
function id≤n - 0 ≤
timestamp≤ 10³ - No two start events and two end events will happen at the same timestamp
- Each function has an end log entry for each start log entry
Solution
"""
production algorithm
"""
from data_structures.stack.stack import Stack
class Solution:
def exclusive_time(self, n, logs):
"""
time complexity O(k * (logn + logt))
space complexity O(k)
"""
stack, result = Stack(), [0 for _ in range(n)]
for string in logs:
log = Log(string)
if log.event == "start":
stack.push(log)
else:
top = stack.pop()
result[top.id] += log.timestamp - top.timestamp + 1
if not stack.empty():
result[stack.top().id] -= log.timestamp - top.timestamp + 1
return result
class Log:
def __init__(self, log):
id, event, timestamp = log.split(":")
self.id = int(id)
self.event = event
self.timestamp = int(timestamp)"""
unit tests
"""
from unittest import TestCase
from algorithms.stacks.exclusive_execution_time_of_functions.solution import Solution
class SolutionTestCase(TestCase):
def test_one_function_many_calls(self):
# Given
n = 1
logs = ["0:start:0", "0:end:1", "0:start:2", "0:end:3", "0:start:4", "0:end:5",
"0:start:6", "0:end:7", "0:start:8", "0:end:9", "0:start:10", "0:end:11"]
solution = Solution()
# When
actual = solution.exclusive_time(n, logs)
# Then
expected = [12]
self.assertEqual(actual, expected)
def test_many_functions_one_call(self):
# Given
n = 6
logs = ["0:start:0", "1:start:1", "2:start:2", "3:start:3", "4:start:4", "5:start:5",
"5:end:6", "4:end:7", "3:end:8", "2:end:9", "1:end:10", "0:end:11"]
solution = Solution()
# When
actual = solution.exclusive_time(n, logs)
# Then
expected = [2, 2, 2, 2, 2, 2]
self.assertEqual(actual, expected)
def test_many_functions_many_calls(self):
# Given
n = 6
logs = ["0:start:0", "1:start:1", "2:start:2", "2:end:3", "1:end:4", "0:end:5",
"3:start:6", "4:start:7", "5:start:8", "5:end:9", "4:end:10", "3:end:11"]
solution = Solution()
# When
actual = solution.exclusive_time(n, logs)
# Then
expected = [2, 2, 2, 2, 2, 2]
self.assertEqual(actual, expected)Strategy
Stacks.
Explanation
The algorithm initializes a stack and an array to hold the exclusive time of each function. Then, the execution logs are iterated.
Each execution log is converted to a Log object. If the log is a start event, then it’s pushed to the stack. Otherwise it’s an end event, and the top of the stack is popped. That’s because the top of the stack is a start event of the same function as the current end event.
The difference from start to end time of the function is calculated, and added to the exclusive time of the current function. Then, if the stack still has a top, then the difference is also subtracted from the exclusive time of the previous function. This is because the previous function isn’t running while the current function is running, and so the exclusive time of the current function needs to be subtracted from the exclusive time of the previous function.
Time Complexity
Each character of all string execution logs is processed. Let k be the number of execution logs. The time complexity to process one execution log depends on the number of characters in its function id and timestamp, since the number of characters in the “start” and “end” events is constant.
The number of characters in any function id is logarithm base 10 of n, where n is the function id. Also, the number of characters in any timestamp is logarithm base 10 of t, where t is the timestamp. So, the time complexity to process one execution log is O(log(n) + log(t)).
Therefore, the time complexity of the algorithm is O(k × (log(n) + log(t))).
Space Complexity
The auxiliary space complexity of the stack can grow to a size proportional to k, where k is the number of execution logs. Therefore, the auxiliary space complexity of the algorithm is O(k).
