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

windoze

star_in_sky 发表于 2013-01-10 21:59
回复 49# folklore
建堆的复杂度是O(n)。

这个不就是O(n)了？还能更快么？

cxytz01

你好，我目前的系统，单线程处理可以在1s内同时接受1000以上的连接。但是由于没有权限更改最大打开描述符数目，没法测试2000以上，但就目前的情况看，没有问题的。

可以在2s内接受1000以上连接，并且可以recv所有连接的数据报文，且发送出去。每个数据报文1024bytes。

我的程序单线程，accept+接受客户端数据报文+将客户端数据报文加密+将客户端数据报文发送出去(发送到本机的另外一个serv)。

客户端也在本机上，使用线程池，一下开启1000个线程，连接我的程序。每个线程发送1024bytes字节。



由于是本机测试，网络状况太过于理想。所以接收和发送很快。 这里就只考虑accept吧。

一刀。 发表于 2013-01-10 21:41
回复 42# cxytz01

cxytz01

现在想做的，既不是epoll，也不是多进线程，而是将单线程的功能最大化！

大家有兴趣可以看下 unp卷一 第15.2节。

一个从文本文件读取程序的客户端，将文本文件发送给服务端，然后服务端原封不动的将文本文件回送回来，客户端接收，然后输出到终端。

一共有5种客户端模型，在作者的环境下
停等待方式             354.0s
使用select和阻塞io 12.3s
单进程非阻塞io        6.9s
多进程阻塞io           8.7s
多线程阻塞io           8.5s

单线程的程序速度飞快～～～，就是算法复杂了。

所以这里，我也搞了个单线程程序。但总觉得求出maxfd是我这个程序的瓶颈。每次循环都要弄一遍。

当然，这个只是初期的系统模型，不过已经可以满足生产要求了。后期如果有需求，再将现在的这个线程剥离出来，弄成多线程，或者epoll形式。 所以该线程是基础。

windoze

cxytz01 发表于 2013-01-10 22:46
现在想做的，既不是epoll，也不是多进线程，而是将单线程的功能最大化！

epoll不就是将单线程功能最大化的方法么？不明白楼主为什么抱着select/poll不放

man page第一句话就是：
epoll is a variant of poll...

简单说，epoll就是一个不用每个连接都把maxfd重新弄一遍的select/poll

star_in_sky

folklore 发表于 2013-01-10 22:02
@star_in_sky
这个。。。。

我说的是建堆;而不是堆排序. 你似乎理解错了.

selfrun

Select 之前的FD_SET ,顺便比较一下不就行了?问题出在你存储fd的方式上。

goldenfort

回复 1# cxytz01


    先把本来的问题 叙述给大家，为什么 一上来，就把 数字放在 数组里，不是binary tree里，

    不说本来问题，人为编造的类似   面试题的东西毫无意义

lxyscls_cu

cxytz01 发表于 2013-01-10 10:51
是啊，很难。你搞出个给我看看。

不要告诉下面的代码

你可以只记录索引么
当然你的元素也是INT，没什么开销{:3_189:}

yulihua49

windoze 发表于 2013-01-10 22:20
回复 55# yulihua49

原来只要“忽略不计”，复杂度就可以变成O(0)的，楼上的高度果然有好几十层楼那么高 ...

O,就是那个O，谁也没办法。但是在实际工作中，有时可以消解到其他操作中，就是溶解掉。就像糖，溶解到水里，喝水时顺便了（反正喝水是必须的），无需研究吃糖的复杂度。
找到溶解O的办法，你的确需要爬几十层楼。
反正关于楼主的问题，我给的就是最优解，你还能比我快吗？
实践中，解决这个问题对性能的影响是感觉不到的。

pitonas

似乎的
问题很难