如何提高查找速度

win_hate

我赞成 雨丝 和 mq110 的观点， 在 32 位机上用 long long 并不能加速。此外 雨丝 提出的方法不依赖于具体的语言和硬件，是很好的方法。加进去的元素一般叫什么``哨兵'' 吧，记不清楚了。

Arghawk

3楼的想法必须基于一个假设就是超越该数组边界的内存中必存在不等于0的，倘若超过数组边界后的很长一段内存都为0，岂不是又白白浪费一段时间啊。

雨丝风片

[quote]原帖由 "Arghawk"]3楼的想法必须基于一个假设就是超越该数组边界的内存中必存在不等于0的，倘若超过数组边界后的很长一段内存都为0，岂不是又白白浪费一段时间啊。[/quote 发表：


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

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

bleem1998

偶用memcmp行不

雨丝风片

[quote]原帖由 "bleem1998"]偶用memcmp行不[/quote 发表：


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

bleem1998

你们继续
在下旁观

mq110

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

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

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

雨丝风片

原帖由 "mq110" 发表：


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

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

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

mq110

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


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

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

圆点坐标

获益匪浅,不错