一次 O(n) 到 O(logn) 的真实体验

背景

一直对于 O(N) 和 O(logN) 没什么概念，只是知道肯定后者更快。但是快到什么个程度？不知道

直到最近做了一个上万量级的数据查找才有了真实体验

结论就是：两者可以有三个数量级的差异

再形象点就是 1s 和 1000s(16min+) 的区别！

那当程序运行起来就是：嗖的一下 和 菜都凉了··· 的区别

好了，到这里本文就结束了，就是想说一下体感上的差别···

具体例子

最近在解析 trace 的时候遇到的这个情况。

需求是：已知 cpu running 状态的所有时间段，也已知每个 function 的自己的耗时情况，根据这两个数组计算每一个方法的 cpu 真实耗时，也就是 cpu self time

cpu running 状态的所有时间段:

[[1, 3], [4,5], [5,10], [11, 12], [13,15], ···]
表示的是 cpu 在 1-3s 4-5s 5-10s 等等，都是 running 状态

function 耗时情况：

[[1, 5], [6,10], [11,14], ···]
表示的是 func1 在 1-5s 执行， func2 在 6-10s 执行等等

那我们可以知道，其实 3-4s 的时候，cpu 并不是一个 running 状态，所以 func1 的 cpu self time 并不是 5-1 = 4，而是 (3-1) + (5-4) = 3

假设，现在我们想要计算 func3 [11,14] 的 cpu self time

如果数据量很小，那当然可以 for 循环从头遍历，找到对应 index 值，然后处理下边界情况就好了，这也是一开始的做法

然后，就 run 了10分钟还没有结束···

开始以为是哪里有 bug，后面通过输出 log 发现 cpu 状态数组的长度大概是 1w 左右，func 数组的长度是 10w 的量级，数量级很大，就是单纯的 慢！

切换为二分查找，4s 就跑完了整个运算过程，时间差了几千倍！！！！

可以交差了···