Chinaunix

标题: 如何提高查找速度 [打印本页]

作者: Go_To_CU 时间: 2005-09-18 11:25
标题: 如何提高查找速度

int empty_array(char *array, int size)
{
char *p = array;
for (p = array; p < array + size; p++) {
if (*p != 0) {
return(0);
}
}
return(1);
}

复制代码

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

作者: mingjwan 时间: 2005-09-18 11:31
标题: 如何提高查找速度
如果强行转化为int型，然后再检查，会不会变快呢？
当然这个速度还与字节对齐有关。呵呵。

作者: 雨丝风片 时间: 2005-09-18 11:33
标题: 如何提高查找速度
对于这种问题，一种最简单的优化就是稍微修改一下，
先通过++依次判断是否找到满足你条件元素，一旦找到
再判断下标是否在数组下标的合法范围之内，这样至少
可以避免每一轮循环都要先去判断下标是否合法。

作者: mingjwan 时间: 2005-09-18 11:37
标题: 如何提高查找速度
如果访问的内存全部为0，不是遭了！
不过想法不错，呵呵。

作者: 雨丝风片 时间: 2005-09-18 11:39
标题: 如何提高查找速度
我说过要“稍微修改一下”嘛，当然要做边界保护的，
比如说，可能要在数组的边界上放一个“多余”的元素。

作者: mingjwan 时间: 2005-09-18 11:40
标题: 如何提高查找速度
如果再稍微修改一下，在换成ｉｎｔ，每四字节一读，岂不是更快。当然最好字节对齐了，否则估计就不见效果了。

作者: mik 时间: 2005-09-18 12:06
标题: 如何提高查找速度
[quote]原帖由 "Go_To_CU"]这段代码主要是看数组是否为空，即查找一个非0的元素，请问可以有更快的查找速度吗？[/quote 发表：

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

      return 1;
}

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

作者: mingjwan 时间: 2005-09-18 12:09
标题: 如何提高查找速度

原帖由 "mik" 发表：

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

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

作者: mik 时间: 2005-09-18 12:14
标题: 如何提高查找速度

原帖由 "mingjwan" 发表：

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

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

总比 p+size:
      mov eax, p
      add eax, size

是不是？：）

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

作者: Go_To_CU 时间: 2005-09-18 12:16
标题: 如何提高查找速度
P+size和size--不一样哦，因为指针一次移动的可能是4个字节

作者: mik 时间: 2005-09-18 12:17
标题: 如何提高查找速度
[quote]原帖由 "Go_To_CU"]P+size和size--不一样哦，因为指针一次移动的可能是4个字节[/quote 发表：

晕倒~~~~

连指针的基本用法，你都不懂。

int *p
p--; // 移动 4个 bytes

char *p
p--; // 移动 1 个 bytes

作者: mingjwan 时间: 2005-09-18 12:18
标题: 如何提高查找速度
优化后那段代码只执行一次的。没有什么差别。
三楼的想法，改好了，可以省去一半的比较。那才是，提高效率啊。

作者: mik 时间: 2005-09-18 12:27
标题: 如何提高查找速度

原帖由 "mingjwan" 发表：
优化后那段代码只执行一次的。没有什么差别。
三楼的想法，改好了，可以省去一半的比较。那才是，提高效率啊。

省去一半的比较？？
不明白？
如何？？

作者: mingjwan 时间: 2005-09-18 12:29
标题: 如何提高查找速度
三楼说得很清楚啊。

作者: mik 时间: 2005-09-18 12:30
标题: 如何提高查找速度

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

？？？？

你是说：

（1）先找出非 0 元素？还是找出 0 的元素？（找不到呢？？继续找？？）
（2）再看是不是超出 size ????

作者: mingjwan 时间: 2005-09-18 12:31
标题: 如何提高查找速度
是啊。难道不是吗？

作者: mik 时间: 2005-09-18 12:31
标题: 如何提高查找速度
[quote]原帖由 "mingjwan"]三楼说得很清楚啊。[/quote 发表：

最多只能说，省去了一个计算时间，

而且，他说的也是错误的想法

作者: mingjwan 时间: 2005-09-18 12:33
标题: 如何提高查找速度
怎么错了？

作者: mik 时间: 2005-09-18 12:53
标题: 如何提高查找速度
[quote]原帖由 "mingjwan"]怎么错了？[/quote 发表：

（1）先找出非 0 元素？还是找出 0 的元素？（找不到呢？？继续找？？）

作者: mq110 时间: 2005-09-18 12:57
标题: 如何提高查找速度
3楼的想法到是挺好..不过不正确.

作者: 雨丝风片 时间: 2005-09-18 13:01
标题: 如何提高查找速度

原帖由 "mik" 发表：

（1）先找出非 0 元素？还是找出 0 的元素？（找不到呢？？继续找？？）

我所说的并不局限于某个具体的问题，你想找什么样的元素就找什么样
的元素，条件是你自己定的，但这本质上是一个顺序查找的问题，我说
的只是对顺序查找的一般优化原则。

在楼主的程序中，使用了一个for循环：
for (p = array; p < array + size; p++) {

这样，在每一轮的循环中，都会先去判断p < array + size是否满足，然后
才会去判断当前位置上的元素是否满足我们的条件。而我所说的就是对于每一
个元素，我们可以先去判断它是否满足我们的条件，一旦满足，我们再去判断
它的下标是否仍然在数组的合法范围之内，这样，实际上p < array + size
这个判断最多只会执行一次。

但是在实际编程过程中，可能对你的数组需要进行一点特别的处理，可能
需要安排一个多余的元素，这个元素必须是满足你的“条件”的，这样才能
让循环正确停止下来，而此时显然下标已经不在“合法”范围之内了，因此
并不会影响到查找失败的结果。

作者: mik 时间: 2005-09-18 13:12
标题: 如何提高查找速度

原帖由 "雨丝风片" 发表：

我所说的并不局限于某个具体的问题，你想找什么样的元素就找什么样
的元素，条件是你自己定的，但这本质上是一个顺序查找的问题，我说
的只是对顺序查找的一般优化原则。

在楼主的程序中，使用了一个for循环..........

这个元素的选择会有一定困难，你不能担保这个元素在数组中是正常有用的。

作者: Go_To_CU 时间: 2005-09-18 13:16
标题: 如何提高查找速度
对，这个特殊元素不好弄，难道就没有别的操作方式了吗？

作者: mq110 时间: 2005-09-18 13:17
标题: 如何提高查找速度
常规的查找吧. 按4 bytes

作者: 雨丝风片 时间: 2005-09-18 13:17
标题: 如何提高查找速度

原帖由 "mik" 发表：

这个元素的选择会有一定困难，你不能担保这个元素在数组中是正常有用的。

从严格的意义上来说，这个元素是不属于这个数组的。也就是说，如果
我需要用数组来存放10个元素的话，为了使用我说的方法进行顺序查找，
那么可能就需要生成一个有11个元素的数组，而最后一个元素对外是不
可见的，仅仅用于顺序查找循环的停止。我想，不管你要查找的条件是
什么，在这个地方随便放一个满足你的查找条件的元素应该是很简单的
事情吧？而这个多余的空间就是这个想法的代价。是否可以忍受这个代价，
就需要看数组的大小等其它的因素了。

作者: 雨丝风片 时间: 2005-09-18 13:19
标题: 如何提高查找速度
[quote]原帖由 "Go_To_CU"]对，这个特殊元素不好弄，难道就没有别的操作方式了吗？[/quote 发表：

我前面已经解释了，这并不是一个“特殊”的元素，而仅仅是满足你的查找
条件的任意一个元素！这个想法的代价仅仅是在定义数组的时候留出来的一个
多余的位置以及由此产生的你心里的一点“别扭”。。。呵呵

作者: Go_To_CU 时间: 2005-09-18 13:24
标题: 如何提高查找速度
如果这个函数是用来检测随便一段内存的值的函数呢？不能增加这样的元素来终止循环，那样会修改内存的值的

作者: mik 时间: 2005-09-18 13:26
标题: 如何提高查找速度
[quote]原帖由 "mq110"]常规的查找吧. 按4 bytes[/quote 发表：

如果，确定数组较大的。那么可以按 6 bytes 查、8 bytes

甚至更多。。。

这样是否更快。

作者: 雨丝风片 时间: 2005-09-18 13:27
标题: 如何提高查找速度
[quote]原帖由 "Go_To_CU"]如果这个函数是用来检测随便一段内存的值的函数呢？不能增加这样的元素来终止循环，那样会修改内存的值的[/quote 发表：

我只能说，对于你的这个条件来说，那个方法不适用，

任何方法都是有前提的，而那个方法的前提就是你有权利来安排一个
“多余”空间。 :wink:

作者: Go_To_CU 时间: 2005-09-18 13:29
标题: 如何提高查找速度
感谢各位的参与，其实我这段函数主要是用来检测内存是否为空的

作者: mq110 时间: 2005-09-18 13:30
标题: 如何提高查找速度

原帖由 "mik" 发表：

如果，确定数组较大的。那么可以按 6 bytes 查、8 bytes

甚至更多。。。

这样是否更快。

我想不是这样的... 32位机来说按4bytes 应该是最快的. 个人理解.如不对请指教.

作者: mik 时间: 2005-09-18 13:40
标题: 如何提高查找速度

原帖由 "mq110" 发表：

我想不是这样的... 32位机来说按4bytes 应该是最快的. 个人理解.如不对请指教.

但是，按 8 bytes 来查，明明是比 4 bytes 省了一半的时间嘛。

而且，在 gcc 中，编译器缺省对齐是 16 bytes 上。

andl $-16, esp

复制代码

作者: 雨丝风片 时间: 2005-09-18 13:49
标题: 如何提高查找速度
[quote]原帖由 "mik"]但是，按 8 bytes 来查，明明是比 4 bytes 省了一半的时间嘛。 [/quote 发表：

你在32位的机器上去判断一个64位的区域是否为空，请问你是如何
“比 4 bytes 省了一半的时间嘛”？ :wink:

作者: mq110 时间: 2005-09-18 13:54
标题: 如何提高查找速度
同时处理32位2进制数. 怎么会8bytes 比4bytes 节省一半时间???不解.

作者: mik 时间: 2005-09-18 14:26
标题: 如何提高查找速度

原帖由 "雨丝风片" 发表：

你在32位的机器上去判断一个64位的区域是否为空，请问你是如何
“比 4 bytes 省了一半的时间嘛”？ :wink:

嘿~~~

int main()
{
   int a[] = { 0, 1};
   int *p = a;

   if (*(long long*)p)
      printf("long long size is %d,%d\n"  a[1]);

   *(long long*)p = 0;
if (!*(long long*)p)
      printf("long long size is %d,%d\n" a[1]);

return 0;

}

你们试一试，结果如何？？？　

作者: mq110 时间: 2005-09-18 14:30
标题: 如何提高查找速度
这能说明效率问题?

作者: mik 时间: 2005-09-18 14:47
标题: 如何提高查找速度
[quote]原帖由 "mq110"]这能说明效率问题?[/quote 发表：

int main()
{
int a[] = { 0, 1 };
int *p = a;
*p = 0;
*(p+1) = 0;
if ( !*p && !*(p+1))
printf("%d\n",a[1]);
}

复制代码

gcc 3.3.1 编译为：

leal -8(%ebp), %eax
movl %eax, -12(%ebp)
movl -12(%ebp), %eax
movl $0, (%eax)
movl -12(%ebp), %eax
addl $4, %eax
movl $0, (%eax)
movl -12(%ebp), %eax
cmpl $0, (%eax)
jne .L2
movl -12(%ebp), %eax
addl $4, %eax
cmpl $0, (%eax)
jne .L2
movl -4(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
.L2:
movl $0, %eax
leave

复制代码

而：

int main()
{
int a[] = { 0, 1};
int *p = a;
*(long long*)p = 0;
if (!*(long long*)p)
printf("long long size is %d,%d\n" a[1]);
return 0;
}

复制代码

gcc 3.3.1编译为：

leal -8(%ebp), %eax
movl %eax, -12(%ebp)
movl -12(%ebp), %eax
movl $0, (%eax)
movl $0, 4(%eax)
movl -12(%ebp), %eax
cmpl $0, (%eax)
jne .L2
movl -4(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
.L2:
movl $0, %eax
leave

复制代码

用事实说话，不用解释了，对比一下：）

不过是未在优化编译的。　不知优化编译后，是否一样。。。

作者: mik 时间: 2005-09-18 15:00
标题: 如何提高查找速度
将两段代码用优化　-O　编译了。

产生代码是差不多。

：）

作者: win_hate 时间: 2005-09-18 21:35
标题: 如何提高查找速度

原帖由 "mik" 发表：

用事实说话，不用解释了，对比一下：）

不过是未在优化编译的。　不知优化编译后，是否一样。。。

int main()
{
int a[] = { 0, 1};
int *p = a;
*(long long*)p = 0;
if (!*(long long*)p)
printf("long long size is %d,%d\n" a[1]);
return 0;
}

复制代码

这段汇编是 gcc 生成的吗？

leal -8(%ebp), %eax
movl %eax, -12(%ebp) # p = a
movl -12(%ebp), %eax
movl $0, (%eax)
movl $0, 4(%eax) # *(long long *)p = 0
movl -12(%ebp), %eax # eax <-- p, or a
cmpl $0, (%eax) # a[0] == 0 ??? where is a[1]
jne .L2
movl -4(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
.L2:
movl $0, %eax
leave

复制代码

作者: win_hate 时间: 2005-09-18 21:43
标题: 如何提高查找速度
同样的c代码(虽然没看明白你在干什么)，gcc 3.3.5 生成：

main:
pushl %ebp
movl %esp, %ebp
subl $24, %esp
andl $-16, %esp
movl $0, %eax
subl %eax, %esp
movl $0, -8(%ebp)
movl $1, -4(%ebp)
leal -8(%ebp), %eax
movl %eax, -12(%ebp)
movl -12(%ebp), %edx
movl (%edx), %eax # eax <-- a
orl 4(%edx), %eax # eax <-- a[0] | a[1]
testl %eax, %eax
jne .L2
movl -4(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
.L2:
movl $0, %eax
leave
ret

复制代码

a[1] 和 a[2] 都处理了。

关键是如何处理这个逻辑表达式

(!*(long long*)p)

复制代码

!a 应该把 a 转换为 int 还是......

不清楚标准上是怎么写的。

ps>; 我好象又记起了一些东西

如果 typeof(a) 是 long long, 那么 !a 被转换为 !(a==0)， long long 与long long 的比较。所以不处理 a[1] 的代码是错误的。

作者: win_hate 时间: 2005-09-18 21:49
标题: 如何提高查找速度
我赞成雨丝和 mq110 的观点，在 32 位机上用 long long 并不能加速。此外雨丝提出的方法不依赖于具体的语言和硬件，是很好的方法。加进去的元素一般叫什么``哨兵'' 吧，记不清楚了。

作者: Arghawk 时间: 2005-09-18 22:50
标题: 如何提高查找速度
3楼的想法必须基于一个假设就是超越该数组边界的内存中必存在不等于0的，倘若超过数组边界后的很长一段内存都为0，岂不是又白白浪费一段时间啊。

作者: 雨丝风片 时间: 2005-09-19 07:52
标题: 如何提高查找速度
[quote]原帖由 "Arghawk"]3楼的想法必须基于一个假设就是超越该数组边界的内存中必存在不等于0的，倘若超过数组边界后的很长一段内存都为0，岂不是又白白浪费一段时间啊。[/quote 发表：

呵呵，请再看看我前面的解释。超过数组边界之后的内存到底有多长一段是0
已经不重要了，关键是你已经进入了雷区，随时都有可能因内存非法访问而
出错，这个方法的思路和限制也请见前述。

在Donald E.Knuth的TAOCP的第三卷的第6.1节Sequential Searching
中讲到了顺序查找算法，同时也给出了对顺序查找的优化思路，即
Quick sequential search和Quicker sequential search，可以参考一下。

作者: bleem1998 时间: 2005-09-19 08:53
标题: 如何提高查找速度
偶用memcmp行不

作者: 雨丝风片 时间: 2005-09-19 09:13
标题: 如何提高查找速度
[quote]原帖由 "bleem1998"]偶用memcmp行不[/quote 发表：

我们讨论的是memcmp的源代码，

作者: bleem1998 时间: 2005-09-19 09:17
标题: 如何提高查找速度

你们继续
在下旁观

作者: mq110 时间: 2005-09-19 12:09
标题: 如何提高查找速度

原帖由 "雨丝风片" 发表：
我说过要“稍微修改一下”嘛，当然要做边界保护的，
比如说，可能要在数组的边界上放一个“多余”的元素。

这个方法还是不错的.
通过雨丝风片的方法.
可以这样改进将最快.
先判断最后一个元素是不是0.
如果是0的话将最后一个元素赋值为1.

然后开始从头按雨丝风片所说的方法来做.
这样保证即使全是0到最后肯定不会越界.

作者: 雨丝风片 时间: 2005-09-19 12:24
标题: 如何提高查找速度

原帖由 "mq110" 发表：

这个方法还是不错的.
通过雨丝风片的方法.
可以这样改进将最快.
先判断最后一个元素是不是0.
如果是0的话将最后一个元素赋值为1.

然后开始从头按雨丝风片所说的方法来做.
这样保证即使全是0到最后肯定..........

不错，这样可以在不用另外增加一个元素的空间，只不过这是一种
破坏性的查找，

，查完了之后别忘了消灭作案痕迹，把最后一个
元素恢复原值才好。

作者: mq110 时间: 2005-09-19 12:26
标题: 如何提高查找速度

原帖由 "雨丝风片" 发表：

不错，这样可以在不用另外增加一个元素的空间，只不过这是一种
破坏性的查找，，查完了之后别忘了消灭作案痕迹，把最后一个
元素恢复原值才好。

你的思想总是十分的开阔. 每次都让我有耳目一新的感觉.
呵呵学习.

作者: 圆点坐标 时间: 2005-09-19 12:38
标题: 如何提高查找速度
获益匪浅,不错

作者: 雨丝风片 时间: 2005-09-19 12:43
标题: 如何提高查找速度

原帖由 "mq110" 发表：

你的思想总是十分的开阔. 每次都让我有耳目一新的感觉.
呵呵学习.

在下也着实对兄台仰慕得紧啊！

才来cu不久，已经被这里的高手们的招数弄得头晕目眩了，
这里永远都不缺乏值得自己学习的东西，我也继续学习ing！

作者: yzc2002 时间: 2005-09-19 12:54
标题: 如何提高查找速度
不能修改最后一个的值，这个串一般是个const的
(1)串长可能为0
(2)如果是个字符串常量，这个修改可能会造成core dump
(3)如果这个串是静态的，则是线程不安全的，存在溢出的风险

作者: bleem1998 时间: 2005-09-19 12:58
标题: 如何提高查找速度
咱家也写了一个
思路参考前面某些人的讨论
array前面的大部分都用int来判断
剩下的不足一个int长的就用char来判断

#include "../my.h"
int empty_array(char *array, int size)
{
int num = size / 4, i;
int *p = (int *)array;
for(i = 0; i < num; i++) {//用32位来判断
if (*p++ != 0)
return 0;
}
num = size - num * 4;
for(i = 0; i < num; i++) {//最后的尾巴用char来判断
if (*array != '\0')
return 0;
}
return 1;
}
int main()
{
char buf[99];
bzero(buf, 99);
//buf[60] = 'a';
printf("buf is%s a empty array!!\n",
empty_array(&(buf[0]), sizeof(buf))?"":" not");
return 0;
}

复制代码

作者: renstone921 时间: 2005-09-19 13:03
标题: 如何提高查找速度
num = size - num * 4;
换成
num %= sizeof(int);

作者: bleem1998 时间: 2005-09-19 13:09
标题: 如何提高查找速度
你的意思是num = size % sizeof(int)吧

作者: renstone921 时间: 2005-09-19 13:16
标题: 如何提高查找速度
对，写错了。只不过是想用求余运算。

作者: mq110 时间: 2005-09-19 13:37
标题: 如何提高查找速度

原帖由 "yzc2002" 发表：
不能修改最后一个的值，这个串一般是个const的
(1)串长可能为0
(2)如果是个字符串常量，这个修改可能会造成core dump
(3)如果这个串是静态的，则是线程不安全的，存在溢出的风险

如果是const修饰的串不适合采取修改的办法.

至于长度是0.应该在程序中判断. 总不至于出现你说的问题.

作者: mik 时间: 2005-09-19 16:42
标题: 如何提高查找速度
[quote]原帖由 "win_hate"][/quote 发表：

那段代码是用 gcc 3.3.1 生成的,这无用置疑! 我也不会做什么手脚！

至于，它什么只会比较 a[0] != 0 而不比较 a[1] != 0
我只能推测这是它一个比较智能的方面。可能是：代码分别将 a[0] 与 a[1]
置为０，故比较 a[0]。当然这只是推测。或许，这是个 BUG 也有这个可能性。

作者: converse 时间: 2009-04-10 16:36

#include <stdio.h>
int empty_array(char *array, int size)
{
unsigned long *p = (unsigned long*)array;
int n = sizeof(unsigned long) / sizeof(char);
unsigned long mask = 1UL;
for (; (char*)p < array + size - n; p++)
{
if (*p && mask)
{
return 0;
}
}
char *tmp;
for (tmp = array + size - n; tmp < array + size; ++tmp)
{
if (*tmp)
return 0;
}
return 1;
}
int main()
{
char buffer[1024] = {0};
printf("empty = %d\n", empty_array(buffer, 1024));
buffer[1] = 1;
printf("empty = %d\n", empty_array(buffer, 1024));
return 0;
}

复制代码

作者: converse 时间: 2009-04-10 16:45
今天才看到,雨兄的思路确实挺好.

我最后贴出来的那个代码嘛,大家就看看就得了...

作者: astezheng 时间: 2009-04-10 19:05

原帖由 Go_To_CU 于 2005-9-18 13:29 发表
感谢各位的参与，其实我这段函数主要是用来检测内存是否为空的

long long *p = array

然后控制好边界，迭代

然后判断*p是否为零，变成8字节/迭代

结贴吧

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)