[函数用法讨论系列10] LOOKUP的查找策略！

willin2000

在右边的话会有问题,附件是按右边模拟的结果:

  8X6HOrhZ.zip (10.68 KB, 下载次数: 119)

2007-5-16 21:26 上传

点击文件名下载附件

[此贴子已经被作者于2007-5-16 21:26:49编辑过]

gdliyy

好久没看到这么好的东东了，怎么没人顶，让更多人都了解！！！

yjgsz

Lookup函数二分法原理模拟器中对收敛的描述是错误的。

模拟器所描述的不是严格的二分法。

 
ubAcI9q5.rar (74.46 KB, 下载次数: 103)

2007-5-16 07:12 上传

点击文件名下载附件

[此贴子已经被作者于2007-5-16 7:12:42编辑过]

willin2000

QUOTE:

以下是引用yjgsz在2007-5-15 22:00:47的发言：

Lookup函数二分法原理模拟器中对收敛的描述是错误的。

模拟器所描述的不是二分法。

确实LOOKUP查找流程和严格意义上讲的二分法是有区别,特别是posi>left,posi<right为否和A(posi)=x为是的情况,可以说是"扩展的二分法".

其实叫法无所谓,只要能真正了解LOOKUP的查找策略就行了.

我在80楼做了一个流程图对含非数字情况的补充,希望yigsz能提供意见,如发现和这个流程图不一致的情况,请告知以便改进:

http://club.excelhome.net/viewthread.php?tid=113915&replyID=840887&skin=1

[此贴子已经被作者于2007-5-16 21:27:19编辑过]

gouweicao78

to yjgsz朋友：

1、首先，从Onkey的流程图上来说，它本身就不是严格的二分法，只不过——套用了二分法的理论和类似的流程。

2、这个帖子从Excel的角度来说，“二分法”只是一个主流方向的称谓，如果严格按数据库理论讲，你的理解是正确的。如果从对Onkey的流程图来描述收敛范围，我的理解是正确的。——比如你说的“如既然在第2步就已经收敛至只剩190、99两个数值，怎么又返回到不是收敛范围中的78（上上次的中间值）”——这个在Onkey流程图左下角，“posi=1？——〉NO——〉返回A(posi-1)”

换句话说，也就是当在收敛范围被逼到了“墙角”无可再收敛时——如果此时这个“墙角”的位置是1（也就是数据的最左边），则返回#N/A表示找不到，否则就把墙角的左边一个数据抓过来交差。

gouweicao78

to willin2000:

今晚，我与ExcelPX、Officefans的KnifeFox版主（刀狐）聊了一下，他用VBA的办法进行测速，并用简单的例子推理了一个观点——Lookup并不忽略与第1参数不同类型的值以及空单元格！！！

这证实了我提出的“忽略”质疑，也印证了czzqb版主说的“以前我曾见到这样一句话：LOOKUP（包括VLOOKUP，HLOOKUP）、MATCH这些函数的查找时间与数据量不成正比。数据越多，查找速度越快。”现象的一部分，Lookup查找的时间与数据量不成正比，但也不是数据越多查找速度越快——而是与数据的结构及所查找的值本身有关。

大方向是“二分法”，在此基础上补充（包括Onkey流程图本身就是补充后的二分法）。

我已邀请 刀狐 参加讨论，希望他能亲自来写这部分，呵呵。

另，由于近日来我事务繁忙，未曾细看后面这些讨论，87楼补充流程图大意也体现了我与刀狐聊天的时的猜想，可再完善些。

[此贴子已经被作者于2007-5-16 0:50:28编辑过]

willin2000

谢谢草兄!

"忽略"的概念我后来发现确实是错误的.哈哈,当时有点想当然.其实在那天以前我没看过讨论贴里的二分图,因为你曾对我说LOOKUP是二分法,而我知道二分算法(数据结构里的基本算法),所以也没仔细看(主要是时间问题).

所以后来化了一些时间来研究找非数的规律,现在87楼的图是我图骥验证每个判断项以后认为的最终结果.

同时也希望草兄和刀狐能对我的流程有新的改进,这将肯定将使我收益非浅,因为越到后来可能越难.

在完成新的流程图后,也就知道LOOKUP(,0/(xx=y))找的不一定是最后一个,也不一定是第一个, 而LOOKUP(1,0/(xx=y))如果找到一定是最后一个(效率也比前者高)在有非数的情况下,LOOKUP的查找效率也会大大降低.

[此贴子已经被作者于2007-5-16 7:50:51编辑过]

yjgsz

QUOTE:

以下是引用gouweicao78在2007-5-16 0:16:33的发言：

本身就不是严格的二分法，只不过——套用了二分法的理论和类似的流程。

只是一个主流方向的称谓，如果严格按数据库理论讲，你的理解是正确的。如果从对Onkey的流程图来描述收敛范围，我的理解是正确的。——比如你说的“如既然在第2步就已经收敛至只剩190、99两个数值，怎么又返回到不是收敛范围中的78（上上次的中间值）”——这个在Onkey流程图左下角，“posi=1？——〉NO——〉返回A(posi-1)”

换句话说，也就是当在收敛范围被逼到了“墙角”无可再收敛时——如果此时这个“墙角”的位置是1（也就是数据的最左边），则返回#N/A表示找不到，否则就把墙角的左边一个数据抓过来交差。

我想说，二分法的基本原理，是不是还适用。

1、数列按升序排序（或“视升序排序”）

2、每次先取中间位置值比较，中间位置=int((首位数位置+末位数位置)/2)

3、数列中每个数值不会被重复查找，即不会被查找第二次。

4、每次收敛范围是上次收敛范围的子集。

模拟中有些结果符合二分法，有些不符合，“只能套用了二分法的理论和类似的流程”。

应该说，对于LOOKUP 存在有待继续探讨和发现的查找原理。

[此贴子已经被作者于2007-5-16 7:20:20编辑过]

gouweicao78

QUOTE:

以下是引用yjgsz在2007-5-16 7:11:34的发言：

我想说，二分法的基本原理，是不是还适用。

1、数列按升序排序（或“视升序排序”）——这一点在前面我已经说明很多次了，理解是一致的。

2、每次先取中间位置值比较，中间位置=int((首位数位置+末位数位置)/2)——理解是一致的。

3、数列中每个数值不会被重复查找，即不会被查找第二次。——这一点你严格按二分法，Lookup不严格按二分法，所以我说只是一个“主流方向”并不代表完全。

4、每次收敛范围是上次收敛范围的子集。——基本一致，但Lookup有例外判断，与第3点同，Lookup不严格按二分法。

模拟中有些结果符合二分法，有些不符合，“只能套用了二分法的理论和类似的流程”。

应该说，对于LOOKUP 存在有待继续探讨和发现的查找原理。

如果要严格按照二分法，则数据就要严格升序，否则二分法就失去了算法基础。这一点我在本帖76楼《无望的回归》一文中已经说过了。可能因为帖子太长，你不一定记得前面所讨论过的，所以在观点上有些重复了，但，不影响我们继续探索的求知欲。

knifefox

经过这两天的研究，以及和gouweicao78兄的探讨中我初步认定是这样的一个过程。有不妥之处希望大家指正！

lookup首先是二分法查找（这一点大家基本一致了），lookup不忽略任何数据（这和以前的理解有区别了），二分点完全是由查找区域决定的

看过gouweicao78模拟器的都知道其有个收敛的特点（如果类型相同这个已经吻合了）

那么我想的流程是：二分查找——如果类型相同，根据大小关系进行收敛；如果类型不同记下查找点，但不进行收敛,然后向右移动一位查找。同样如果遇到类型相同就根据大小关系进行收敛。如果类型不同，再次记下查找点。如果向右到最后一个数后再向左在查找点间进行二分查找。（所以类型相同和不同的区别主要就是就是是否进行收敛）

另如果查找到与查找值相同的数值时就不再二分查找，而是直接向右查找（这个大家意见也统一了）

举例：

比如A1：A10都为文本， =lookup(9,A1:A10)

那么先后查找的位置是 5 6 7 8 9 10 2 3 4 1

[此贴子已经被作者于2007-5-16 14:04:46编辑过]