求一取最大值得算法！！常见排序算法不要。

yulihua49

folklore 发表于 2013-01-10 18:09
@windoze用堆的话是log(n),
前提是本身有序。 此外，堆重整也要时间。
所以，堆适用于不关心数据的index， ...

完全不用任何的序。在accept后判定fd的最大值即可：

1. 
   
2. 
   
3. int max_fd=-1,s;
   
4. while(1) {
   
5.       s=accept(...);
   
6.      max_fd=MAX(max_fd,s);
   
7.      ......
   
8. }
   

复制代码

folklore

@yulihua49人家还要删除

windoze

yulihua49 发表于 2013-01-10 19:47
完全不用任何的序。在accept后判定fd的最大值即可：

对于总共n个连接，难道那个循环不用执行n次？

yulihua49

windoze 发表于 2013-01-10 20:45
对于总共n个连接，难道那个循环不用执行n次？

当然是n次，但是分散了，而且只对少数有效连接操作，不用对数组的大部分－1操作。
此n非彼n。
此n是每次连接一次，可能比彼n少，也可能多。但是相对于耗时冗长的连接活动，它的开销忽略不计。虽然是O（n)，但其前边的系数是0！！！

0O(n), 明白吗？
这种问题，理论上吃干轧净了，不会有新发明，在前边的系数上下下工夫吧。

selfrun

你要解决的问题，是这个系统的瓶颈吗？
回答这个问题之前，别拍脑袋，拿测试代码和测试结果说话。

一刀。

回复 42# cxytz01


    别说一万，两三千就不行了。参考一下这个http://lse.sourceforge.net/epoll/index.html
    select和poll的性能几乎是一样的，检测到事件之后，就必须要扫一遍fd_set，每次读数据之前都循环一万次，性能能好吗？

star_in_sky

回复 49# folklore


    建堆的复杂度是O(n)。删除堆顶元素，然后调整堆的复杂度是O(logN)，向堆中插入元素复杂度是O(logN)

folklore

@star_in_sky
这个。。。。


































































































不可能有小于nlog(n)的排序算法。。。

windoze

回复 55# yulihua49

原来只要“忽略不计”，复杂度就可以变成O(0)的，楼上的高度果然有好几十层楼那么高……
干脆以后就表优化神马程序了，反正对于宇宙几十亿年漫长的寿命而言，程序执行的那点时间都可以忽略不计的