题目描述

给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如，"0:start:3" 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 "1:end:2" 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以 调用多次，可能存在递归调用 。

函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。

以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

示例1:

输入：n = 2, logs = ["0:start:0","1:start:3","1:end:5","0:end:6"]
输出：[4,3]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 3 个单位时间。 
函数 1 在时间戳 3 的起始开始执行，执行 3 个单位时间。 
函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。 
所以函数 0 总共执行 3 + 1 = 4 个单位时间，函数 1 总共执行 3 个单位时间。 

解题思路

这里这道题使用栈（deque）来解决：

1. 准备一个方法专门解析日志文件。
2. 针对数据特点，start->end->start->end 或者 start->start->end->end，每次遇到start则将数据压栈，deque.push
3. 如果遇到end则出栈，并计算耗时；由于可能存在嵌套，那么再判断一下栈中是否有start数据，如果有则将刚刚计算出来的时间作为额外时间记录在栈顶元素中。

根据上述思路，可以得到下面代码：

 
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
 
class Solution1 {
    public int[] exclusiveTime(int n, List logs) {
 
        int[] res = new int[n];
        Deque deque = new LinkedList<>();
 
        for (String log : logs) {
            Log obj = parse(log);
 
            if (obj.start) {
                deque.push(obj);
            } else {
                Log start = deque.pop();
                int value = obj.timestamp - start.timestamp + 1;
                if (deque.peek() != null) {
                    deque.peek().innerDiff += value;
                }
                res[obj.functionId] += (value - start.innerDiff);
            }
 
        }
        return res;
    }
 
    private Log parse(String log) {
        String[] array = log.split(":");
        return new Log(Integer.valueOf(array[0]), "start".equals(array[1]), Integer.valueOf(array[2]));
    }
 
    class Log {
        int functionId;
        boolean start;
        int timestamp;
        int innerDiff;
 
        public Log(int functionId, boolean start, int timestamp) {
            this.functionId = functionId;
            this.start = start;
            this.timestamp = timestamp;
            this.innerDiff = 0;
        }
    }
 
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        System.out.println(Arrays.toString(solution.exclusiveTime(2, Arrays.asList(new String[]{"0:start:0", "1:start:2", "1:end:5", "0:end:6"}))));
    }
}

下面对代码耗时进行部分优化，我自己实现了一个栈，并且优化了解析逻辑，尽量降低处理的时间成本，目前发现自己实现的栈基本对耗时没有影响，优化解析逻辑反而带来明显的效果。下面是部分改造的代码：

实现栈：

class MyDeque {

    Log[] array;
    int tail;

    MyDeque(int length) {
        this.array = new Log[length / 2 + 1];
        this.tail = 1;
    }

    public void push(Log log) {
        array[tail++] = log;
    }

    public Log pop() {
        return array[--tail];
    }

    public Log peek() {
        return array[tail - 1];
    }
}

优化解析逻辑： 

private Log parse(String log) {

    int functionId = 0;
    int timestamp = 0;
    boolean start = false;
    int i = 0;
    while (log.charAt(i) != ':') {
        functionId *= 10;
        functionId += (log.charAt(i) - '0');
        i++;
    }
    if (log.charAt(++i) == 's') {
        start = true;
        i += 6;
    } else {
        i += 4;
    }
    while (i < log.length()) {
        timestamp *= 10;
        timestamp += (log.charAt(i) - '0');
        i++;
    }

    return new Log(functionId, start, timestamp);
}

优化效果截图：

下面是优化后的代码实现：

 
import java.util.*;
 
class Solution {
    public int[] exclusiveTime(int n, List logs) {
 
        int[] res = new int[n];
        MyDeque deque = new MyDeque(logs.size());
 
        for (String log : logs) {
            Log obj = parse(log);
 
            if (obj.start) {
                deque.push(obj);
            } else {
                Log start = deque.pop();
                int value = obj.timestamp - start.timestamp + 1;
                if (deque.peek() != null) {
                    deque.peek().innerDiff += value;
                }
                res[obj.functionId] += (value - start.innerDiff);
            }
 
        }
        return res;
    }
 
    private Log parse(String log) {
 
        int functionId = 0;
        int timestamp = 0;
        boolean start = false;
        int i = 0;
        while (log.charAt(i) != ':') {
            functionId *= 10;
            functionId += (log.charAt(i) - '0');
            i++;
        }
        if (log.charAt(++i) == 's') {
            start = true;
            i += 6;
        } else {
            i += 4;
        }
        while (i < log.length()) {
            timestamp *= 10;
            timestamp += (log.charAt(i) - '0');
            i++;
        }
 
        return new Log(functionId, start, timestamp);
    }
 
    class Log {
        int functionId;
        boolean start;
        int timestamp;
        int innerDiff;
 
        public Log(int functionId, boolean start, int timestamp) {
            this.functionId = functionId;
            this.start = start;
            this.timestamp = timestamp;
            this.innerDiff = 0;
        }
    }
 
    class MyDeque {
 
        Log[] array;
        int tail;
 
        MyDeque(int length) {
            this.array = new Log[length / 2 + 1];
            this.tail = 1;
        }
 
        public void push(Log log) {
            array[tail++] = log;
        }
 
        public Log pop() {
            return array[--tail];
        }
 
        public Log peek() {
            return array[tail - 1];
        }
    }
 
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.exclusiveTime(2, Arrays.asList(new String[]{"0:start:0", "1:start:2", "1:end:5", "0:end:6"}))));
    }
}

 总结

这次优化发现即使自己定制实现一套栈，但是耗时也不一定是最优的（因为这个操作不是最大的短板）。

反而是通过对常用字符串解析操作，做了一次优化，性能得到大幅度提升；但是，真实开发过程中，我还是会使用第一种实现方式，因为代码简单并且可读性强，后续维护成本也比较低。在代码性能、可读性、可维护性，我们其实需要做一个平衡的，这样可能才是实践要去决策的。

最后性能优化还是要找到真正的短板，逐个优化才行，否则效果不会太明显的。