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

yulihua49

cxytz01 发表于 2013-01-10 11:20
不好意思，没描述清楚。 目前代码是1024。

后期系统升级，考虑到大并发量，需要同时接入上万个连接，就需 ...

你这个问题，实在应该用epoll，将来上万的连接，select如何吃得消？
最近有人提出使用select做大并发，理由是兼容。
我打算这么解决：
每个连接一个context，系统有context池。context里有fd；
凡连接的context的下标加入AVL树，以fd为key。AVL树里的max就是最大的fd。
这个AVL树很有用。每次从select里激活的fd，能快速找到它的context。
关闭的连接，从avl树里删除。
也可以用RB_tree.
虽然逃脱不了Nlog2(N)的命运，但是它是在连接时逐步建立的，分散的消耗时间，不显。

不过我也提建议，不主张select处理超过1536的连接。

cxytz01

我只要1万个连接。不要多。

一刀。 发表于 2013-01-10 14:09
楼主还是先看看select/poll能不能做高并发服务器吧

cxytz01

如果要做，在加个线程池，能上多少？

描述里面说清楚了，不用epoll，否则不会讨论什么maxfd的比较。

cxytz01 发表于 2013-01-10 15:37
我只要1万个连接。不要多。

cxytz01

你好，epool + aio能够很轻易的做成大并发的服务器。

现在我想考虑的是偏要用select能不能做做到高效率的服务(1~2w吧)。

记得unp上作者的n个回射服务器的例子， 一个单线程的select + 非阻塞io，比多线程阻塞io，快了好像是2倍。但是算法复杂了。

所以是想考虑有什么好的算法可以搞出个好的服务器来。


请问系统context池是什么？

yulihua49 发表于 2013-01-10 14:28
你这个问题，实在应该用epoll，将来上万的连接，select如何吃得消？
最近有人提出使用select做大并发，理 ...

cjaizss

folklore 发表于 2013-01-10 13:24
@cxytz01
hehe, dandingIng

想想“堆排序”算法中里那个堆是怎么形成的

yulihua49

cxytz01 发表于 2013-01-10 15:44
你好，epool + aio能够很轻易的做成大并发的服务器。

现在我想考虑的是偏要用select能不能做做到高效率 ...

context称为“上下文”，按需要定义其内容（里边至少要有一个fd吧？），也可以称为“session”,用来表达任务状态。
通常是一个结构体。多个结构体组成一个数组，称为“池”。
每一个连接进入后，按照所需的业务流程，定义其状态，一步一步的完成作业。


我很怀疑select能做上万？
光是激活后找到激活的fd就是不小的开销。
然后用这个fd找到context，然后根据context的状态调用相应的处理程序。
一般是accept后,，分配一个context，加入avl树，将fd加入FD_set.......
这些必须单线程做，上万？时间都干这个了，能有什么吞吐量？

方兆国

回复 26# cxytz01


    你不是找最大值么？怎么用排序啊？

如果你想把最大值放在最前面的话，最简单的是依次选择最大值，放在另一个数组里，然后交换两个数组的指针，这是最简单的，不过经常修改的数组没必要去排序，那样排序浪费的时间也很大；
提高效率的话，还有一个办法，就是用宏替换的方法，把函数定义成宏，然后调用的地方使用宏名，让编译器依次去替换各个函数

folklore

@windoze用堆的话是log(n),
前提是本身有序。 此外，堆重整也要时间。
所以，堆适用于不关心数据的index， 取值远大于设值的情况。

不然， 用链表保存少量的非-1元素是最有效算法。 复杂变 n

folklore

回复 39# windoze


    最初建堆是nlog(n),此后第次设值， 要log(n)来Adjust

windoze

回复 49# folklore
所以你的方案就变成了两个步骤，第一要确定数据是否有序，第二才是取最大值。
第一个步骤需要n log(n)