简述 本文记录使用到的算法复杂度.
复杂度 以下所有内容都是关于时间损耗的: 如果需要对数组进行扩展, Libev会使用realloc重新分配并移动整个数组.
不过随着数量的增加, 这样的操作次数会逐渐减少. 所以O(1)的意思是Libev执行了很长时间的realloc操作, 但是在一般情况下它很快且接近与常数级(constant time)操作.
添加 / 删除 计时器O(logn):
这意味着: 如果您有一个1小时后触发的timer, 还有100个左右的timer会在此之前触发. 那么每次的插入都会不得不跳过大约7(ld 100)个左右的timer.
改变计时器O(logn):
改变计时器的成本比删除/添加计时器的成本要低, 只需要在计算在内部结构中的操作.
添加 IO / idle/ signal/ child等O(1):
只需要将它们添加到数组或链表的指定位置.
每次循环迭代对文件描述符的每次更改:
更改意味着启动或停止ev_io, 这需要Libev重新计算它的状态. 这取决于是否需要通知内核(系统调用).
每次循环迭代中找到下一个计时器O(1):
从最小堆(二叉树或四叉)中总能在固定的位置找到下一个计时器.