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

cokeboL

回复 18# cokeboL


如果支持delete操作，要想快速获取最大值，就建个栈，把最大值的数组下标压栈，push、pop更新，

获取复杂度还是O(1)

cxytz01

不好意思，没描述清楚。 目前代码是1024。

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

该数组是int类型，用于存储sockfd。取最大值得目的是为了select使用。

cokeboL 发表于 2013-01-10 11:03
回复 12# cxytz01

cokeboL

回复 22# cxytz01


空间要求高吗？服务器的话，应该多用个10k级的数组应该不是问题，那就加个跟sockfd数组同样数目的

栈索引来保存最大值的下标吧，比如

#define MAX_CONN_NUM 10000
short max_val_addr[MAX_CONN_NUM] = {-1};

然后参见我前面那个楼的，在insert和delete操作的代码里增加栈操作的代码

cxytz01

重新来描述下吧，确实描述不清楚。 当时正搞得焦头烂额。

需求：
    高并发服务器，目前使用的是常规非阻塞IO + select + 短链接(一笔业务链接过来，处理完毕就关闭socket，同时初始化sockfd数组对应元素为-1)。不使用epoll。

    定义数组： int gt_sockfd[FD_SETSIZE]   //FD_SETSIZE目前为1024，后期会把select改成poll方式，支持更多的连接，上万。
    数组初始值： 每个元素为-1(标识为没有被使用)

    数组元素会按由低下标，到高下标的 顺序使用， 被使用时，其值会被置成一正数。当该元素被使用后，会再次被初始化成-1。 元素被再次初始化的顺序是不确定的，不一定从低下标到高下标的顺序初始化，完全随机。

    每当数组元素变化(不管是初始化成-1，还是被赋值成正数)，我都需要计算最大的数组元素。   /* 可以不用每次数组元素变化都计算一次， 每隔一段时间计算一次即可，但本着抠门的精神，就想抠一抠这样的方式。*/

    代码
    for (; {

        ...

         select(maxfd + 1, &listenfd_set.....);

         connfd = accept(listenfd ...........);

         pthread_mutex_lock(..);
         for (i = 0; i < FD_SETSIZE; i++) {          /* 存储fd，用于其他线程使用，其他线程使用完毕，将其置位为-1 */
             if (gt_sockfd == -1) {
                 gt_sockfd = connfd;

                  如果gt_sockfd  比当前 maxfd大，那么就设置maxfd 为 gt_sockfd
                  break;
             }

          }
     pthread_mutex_unlock(..);
         /* 该for循环, 不断的循环啊循环啊，maxfd总会不停的变大。 而select总是不停的轮询maxfd个数据，随着maxfd的增大，select效率会降低。而且maxfd如果不做处理，总有一天会溢出。
             这里也可以指定当maxfd达到某一数值之后，才重新计算下maxfd。  但是如果我想每次for循环都计算maxfd(本着抠的精神，没事找茬的精神)，可又怕效率过低，所以发帖请教一好的计算maxfd的算法。。
       */

         ...........

    }
         

cxytz01

空间没要求，能换时间就好。

cokeboL 发表于 2013-01-10 11:27
回复 22# cxytz01

cxytz01

哦，错了，poll不需要maxfd，那就不用poll，改FD_SETSIZE大小吧。

cxytz01 发表于 2013-01-10 11:55
重新来描述下吧，确实描述不清楚。 当时正搞得焦头烂额。

需求：

cokeboL

回复 24# pmerofc


    同迷惑

windoze

回复 25# cxytz01


这个需求…………
其实和数组半毛钱关系都没有，表用select就好了，改用epoll/kqueue/....啥的就不用纠结了

cxytz01

确实可以使用，但是现在目的是想搞懂一个取最大值得高效算法。

windoze 发表于 2013-01-10 12:18
回复 25# cxytz01