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

yjgsz

   KnifeFox版主说的不错，较圆满。

   哪怕跟EXCEL开发人员的思路不同（也无从知道），只要对过程及结果都能给出合理的解释就是大功告成了，对今后LOOKUP的具体应用也有实用的指导意义。

   多讨论就会有收获。

czzqb

LOOKUP速度测试（之一，数值） 

测试方法    数据区域：A列65536个单元格；公式：LOOKUP(5,A:A)共2000个公式

测试过程

1,A列全部设为1,运行时间：0.006s

   A列全部设为9,运行时间：0.006s

2,A列全部设为1,A1和AA65536两个单元格改为以下三个数字的各种组合：{1,5,9}  运行时间:0.006s

3,A列全部设为RAND()*100【选择性粘贴为数值，且其中没有=5的】，运行时间：0.006s

4,A1:A32767为上半区，A32768:A65536为下半区

  上半区全部＝5,下半区两次测试分别=1和RAND()*100，运行时间都是0.006s

5,三次测试——

    A列全部=5，

    下半区=5，上半区=1

    下半区=5，上半区=RAND()*100

    三次测试的结果都是：运行时间 11.609s

结果分析

1,第5个测试时间为什么这么长？看看流程图的中间部分。当X=A(posi)时，LOOKUP要逐个比较。由于下半区全部=5,所以它要比较(65536-32768)次。当下半区不是全部＝5,就基本上使用二分法，比如上面说的测试3。

2,onkey流程图在二分法为主导的情况下，能找出另外一个逐个比较法的分支来，确属不易！这个精华是不是应该Double?!

3,两个时间之比＝11.609/0.006=1934

  这和查找次数之比基本吻合：

  当采用逐个查找时（测试5)，查找次数是：(65536-32768)

  而采用二分法查找同样的区域（如测试1中的A列=1的情况），查找次数是LOG((65536-32768),2)=15

  (65536-32768)/LOG((65536-32768),2)=2184。

  2184与1934非常接近。这是不是也能从另一个侧面佐证：LOOKUP确实是采用的二分法？

                                                                                                                                                                                                                 .

[此贴子已经被作者于2007-5-17 20:00:24编辑过]

czzqb

LOOKUP速度测试（之二，文本与数值）

测试方法  前面的测试相同。A列整列，公式2000个

测试过程

序号	A1	A66536	其他单元	时间(S)
1	A	5	A	5.484
2	2	5	A	5.484
3	A	2	A	5.484
4	5	5	A	5.484
5	5	2	A	5.484
6	5	A	A	11.059
7	9	A	A	11.059
8	A	A	A	11.059
9	2	A	A	11.059
10	A	9	A	16.391
11	5	9	A	16.391

结果分析

1,LOOKUP确实不是“忽略”文本，而是要作更复杂的运算，需要更多的时间

2,前5个测试（序号1-5)下半区都有一个数字。所以LOOKUP只查找了下半区，这和Willin2000增补的流程相吻合；

  而测试6-测试9这四个，下半区没有数字，所以在查找完下半区后，又反过来查找了上半区。因此它的时间是前5个的2倍。

3, 最后两个测试它的时间是测试6-9的1.5倍。为什么是这样？onkey流程图没说，willin2000的流程图也解释不了这个现象。存疑。也许这是完整流程图的突破点之一？（因为下楼要说到另一个突破点）

                                                                                       .

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

czzqb

LOOKUP速度测试（之三，各种类型）

测试方法    与前相同，A列整列，2000个公式 LOOKUP(5,A:A)

测试过程

1, A列整列 为文本"A"  运行时间：11.047s

2, A列整列 为空值       运行时间：5.438s

3, A列整列 为各种错误值       运行时间：6.703s

4, 上半区为文本，下半区为空值    时间：8.453s

5, 上半区为#N/A，下半区为数值1 时间：0.006s

6, 上半区为#N/A，下半区为数值5 时间：11.609s

7,……

其他的组合，我就不列出了。

结果分析：

我只想说一句，看来我们把他们统称为“非第一参数类型”是不大恰当的，因为显然——LOOKUP对于非第一参数类型元素的处理是各不相同的！

 增加逻辑值测试：A列整列分别写上两种逻辑值true和false，运行时间：5.578s

[此贴子已经被作者于2007-5-18 10:42:53编辑过]

willin2000

QUOTE:

以下是引用czzqb在2007-5-17 19:09:56的发言：

.....................

3, 最后两个测试它的时间是测试6-9的1.5倍。为什么是这样？onkey流程图没说，willin2000的流程图也解释不了这个现象。存疑。也许这是完整流程图的突破点之一？（因为下楼要说到另一个突破点）                                                                                .

 

10,11流程图可以解释的.

6/7/8/9的第一次是走下面图中的:1/2/(出口是A)4/5,在5中right=posi-1=posii-1=32678-1
 

posi10/11的第一次是走下面图中的:1/2(出口是B)/3/4/5,5中right=posi-1=65536(出口B的数)-1=65535,这样第二次还要走一次下半区(不含65526了),

 

CZZQB能否把测试附件发上来,因为我这里94的6-9和95楼的1等区别不大,.

(95-5容易解释.)

[此贴子已经被作者于2007-5-18 0:59:06编辑过]

gouweicao78

[em17][em17][em17]

非常棒！czzqb版主的测试！

gdliyy

QUOTE:

以下是引用gouweicao78在2007-5-18 1:06:06的发言：

[em17][em17][em17]

非常棒！czzqb版主的测试！

哟，这里这么热闹，谢谢几位版主的无私分享!

czzqb

To willin2000：

1，前面的测试有点问题。主要是因为测试条件不统一。今天把测试条件统一了一下，重新作了一遍，结果已经在上面几个帖子中更改。请按新数据重新验证

2，测试的方法很简单。

(1)A列整列输入数据

(2)B列的B1:B2000输入公式LOOKUP(5,A:A)

(3)来个按钮，关联一段宏。代码是：

Sub myTimer()
Dim t, t1
t = Timer
Calculate
t1 = Timer - t
MsgBox Format(t1, "0.000秒")
End Sub
(4)没了

——这样，就不用发附件了吧？

3，

posi10/11的第一次是走下面图中的:1/2(出口是B)/3/4/5,5中right=posi-1=65536(出口B的数)-1=65535,这样第二次还要走一次下半区(不含65536了),

这个解释很对！是我的疏忽！不好意思。测试二的1/2/3/4/5走下半区；6/7/8/9上半区+下半区（整个A列）；而10和11除了整个A列之外，又多走了一遍(差一点)下半区。

——这样我的测试之一、之二的结果就在onkey和willin2000两个流程图中都得到了解释。

下来的工作就是要继续改善流程图，以适应测试之三得到的各种数据。在下面我将继续给出另一个测试结果（之四）

czzqb

LOOKUP速度测试（之四，文本）

在“测试之三”中除了文本之外其余各种情况已经测试（如各种错误值、各种逻辑值），所有错误值速度基本一样，逻辑值的速度也相同。

文本有没有不同？

测试

测试方法同上（A列整列、2000个公式）

英文

字符串从ABCD……XYZ顺序截取

文本长度：	时间s
1	11.047
2	12.063
3	11.234
4	12.219
5	11.625
6	12.578
7	11.844
8	12.75
9	12.016
10	12.969
11	12.328
12	12.328
13	13.734
14	13.344
24	16.578
25	13.563
26	15.594

这得到了一个很奇怪的结果。

好像文本长度为奇数和偶数的分别采用两种查找；而奇数的增长比偶数快……

汉字

测试字符串：从“中华人民共和国北京是首都”顺序截取。

测试结果是：

汉字个数	时间s
1	11.188
2	12.188
3	11.391
4	12.453
5	11.826
6	12.751
7	12.034
8	12.875
9	12.219
10	13.125
11	12.587
12	13.468

看来流程图要想合理地解释这些结果，将会是比较复杂的一个东东吧？（如果这些测试结果正确的话）

[此贴子已经被作者于2007-5-18 11:05:06编辑过]

willin2000

计算时间除了和查找策略有关外,是不是也应该和计算对象有关,因为不同类型的参数在计算机了的存储方式各不相同,同一个表达式在翻译成机器码后机器码的条数也是不一样的.

附件是比较(按"测试"):

HdBsoEA6.rar (8.44 KB, 下载次数: 92)

2007-5-19 11:40 上传

点击文件名下载附件
[函数用法讨论系列10] LOOKUP的查找策略！

(由于上传尺寸限制,下载后将A/B/E/G/HJ/K/N到底(65526) (D列为全空)