如何提高查找速度

Go_To_CU

1. 
   
2. int empty_array(char *array, int size)
   
3. {
   
4.     char *p = array;
   
5.     for (p = array; p < array + size; p++) {
   
6.         if (*p != 0) {
   
7.             return(0);
   
8.         }
   
9.     }
   
10.     return(1);
    
11. }
    
12. 
    

复制代码

这段代码主要是看数组是否为空，即查找一个非0的元素，请问可以有更快的查找速度吗？

mingjwan

如果强行转化为int型，然后再检查，会不会变快呢？
当然这个速度还与字节对齐有关。呵呵。

雨丝风片

对于这种问题，一种最简单的优化就是稍微修改一下，
先通过++依次判断是否找到满足你条件元素，一旦找到
再判断下标是否在数组下标的合法范围之内，这样至少
可以避免每一轮循环都要先去判断下标是否合法。

mingjwan

如果访问的内存全部为0，不是遭了！
不过想法不错，呵呵。

雨丝风片

我说过要“稍微修改一下”嘛，当然要做边界保护的，
比如说，可能要在数组的边界上放一个“多余”的元素。

mingjwan

如果再稍微修改一下，在换成ｉｎｔ，每四字节一读，岂不是更快。当然最好字节对齐了，否则估计就不见效果了。

mik

[quote]原帖由 "Go_To_CU"]这段代码主要是看数组是否为空，即查找一个非0的元素，请问可以有更快的查找速度吗？[/quote 发表：


int empty_array(char *array, int size)
{
         while (size--)  
                 if (*array++)
                       return 0;
         
        return 1;
}

会不会更有效呢？ ：）不过会改变参数，不改变参数，只能设临时变量了

mingjwan

原帖由 "mik" 发表：


int empty_array(char *array, int size)
{
         while (size--)  {
                 if (*array++)
                       return 0;
                 else
                      continue;
    ..........

只是看起来变快了。你的过程又没有比别人少了什么操作。

mik

原帖由 "mingjwan" 发表：


只是看起来变快了。你的过程又没有比别人少了什么操作。

是有不同的：
(1) size-- 操作比 p+size 效率要高嘛，
size-- 可以编译成：
      mov eax, size
         dec eax

总比 p+size:
        mov eax, p
        add eax, size   
   
是不是？ ：）

(2) 少了临时变量操作。
   ：）

Go_To_CU

P+size和size--不一样哦，因为指针一次移动的可能是4个字节