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

_Rayx

最好说说应用于什么场景，这样能够有针对性的优化。

yulihua49

_Rayx 发表于 2013-01-11 14:58
最好说说应用于什么场景，这样能够有针对性的优化。

说明了，就是在select之前需要知道max_fd.
那么，在accept之后就可以判定max_fd,这个只需在连接时进行O（1），每次io免除了O（n）的操作。
虽然在总体上是O（无穷），但是accept发生相对较少，间距较长，所以发生率是很低的，一分钟没有几次。
同时最大的fd就是发生在accept时，在此判断最合理。

windoze

回复 69# yulihua49

找最大数当然是O(n)，这个是理论上限。
但是lz提错了需求，他说他就要让select/找maxfd更快点，可是早就有人告诉他，epoll/devpoll/eventport/kqueue/IOCP就是更快的select，而且不需要找maxfd。

复杂度就是复杂度，不是你“忽略掉”就不存在的，只有不需要做的事复杂度才是0。

xsniper001

回复 7# cxytz01
C可以用宏

   

leejqy

既然大部分时候总是-1，那干脆array[0-1023] = {-1}， max=-1;
对写操作加上if(array[i]>max)max=array[i]，不就行了？

yulihua49

cxytz01 发表于 2013-01-09 19:16
目前有数组A[1024]；     数组元素个数永远都是1024。

该数组内容的特点是，  绝大多数时间里， 几乎所有 ...

每一个元素的指针加入一个平衡二叉树（带重码处理的二叉树）。然后在二叉树中搜索最大值，几下就出来了。
这个二叉树就是这个数组的索引。
可以用STL的multi_map.

cxytz01

回复 76# yulihua49

也对，回去看看二叉树，忘了


   

tony_trh

不管你用什么方法，最少也得扫描一遍吧，不然，你怎么知道哪个最大？

yulihua49

tony_trh 发表于 2013-05-11 08:29
不管你用什么方法，最少也得扫描一遍吧，不然，你怎么知道哪个最大？

对，但是扫一遍，以后用N次都无须扫描了。

fender0107401

lz你知道什么叫memorization吗？