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

cxytz01

目前有数组A[1024]；     数组元素个数永远都是1024。

该数组内容的特点是，  绝大多数时间里， 几乎所有的元素都是-1， 只有少部分元素不是-1。

求一算法，取该数组的最大值。

注意：请不要给我冒泡，快速，选择排序算法。

该算法函数经常被调用！！！

cxytz01

是C， C没有内联.有什么好办法回复 4# xsniper001


   

cxytz01

你来告诉我怎么描述数组吧，高手，吹毛求疵。

pmerofc 发表于 2013-01-09 19:47
扯蛋的题目

连如何描述数组都不会

cxytz01

是啊，很难。你搞出个给我看看。

不要告诉下面的代码

int max;

for (i = 0; i < 1024; i++) {
   if (A > A[i+1]) max = A;
   else max = A[i+1];
}

hellioncu 发表于 2013-01-09 19:59
这语气，似乎问题很难似的

cxytz01

后期数组可能会增大，不仅限于1024，而是上万。

而且比较函数是放在for( ; ;   )中的。

想看看有什么时间复杂度低的算法。

linux_c_py_php 发表于 2013-01-09 19:20
排序干嘛... 扫一遍不就知道了?

cxytz01

如果是遍历一遍就简单了，

但问题是是无限遍历

for(;  ; ) {

  某些操作使某个数组元素值变化

  取最大值...     数组目前是1024个元素，后期会扩展成1万个 以上。
   
  使用最大值



}


嗯，和排序无关，我想错了。

ahui886 发表于 2013-01-10 10:50
求个最大值，遍历一遍不就出来了？跟排序有啥关系呢？

cxytz01

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

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

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

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

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
重新来描述下吧，确实描述不清楚。 当时正搞得焦头烂额。

需求：