Binary Search: Lookup Efficiency With MatchType Set to 1

[Aladin Akyurek]

Quoted from: http://www.mrexcel.com/board2/viewtopic.php?t=87050

formula 1:

=VLOOKUP(B14,{"Deluxe Tour",128;"Jungle River Safari",88;"My Generation Tour Adult Only",128;"Power Boat Jeep Rental",295},2,0)

formula 2:

=LOOKUP(B14,{"Deluxe Tour","Jungle River Safari","My Generation Tour Adult Only","Power Boat Jeep Rental";128,88,128,295})

i've often wondered how these two would perform next to each other in like conditions, one syntax to another. any idea aladin?
_________________
Regards,
Zack

Both formulas use a sorted built-in table. The LOOKUP formula invokes binary search, the VLOOKUP formula linear search as determined by the match-type = 0. Therefore the LOOKUP formula will be faster.

How do VLOOKUP, LOOKUP, INDEX/MATCH perform when all invoke binary search?

Before proceeding further, one thing must be noted. Using binary search formulas with sortedtextrequires caution. To see this, enter in B14 the following:

Voyage au bout de la nuit

The LOOKUP formula happily returns 295, while the VLOOKUP formula with match-type set to 0 errors out.

=VLOOKUP(B14,{"Deluxe Tour",128;"Jungle River Safari",88;"My Generation Tour Adult Only",128;"Power Boat Jeep Rental",295},2,1)

would behave like the LOOKUP formula.

This cautionary note does not apply to the use of BigNum/BigStr as lookup values in formulas which invoke binary search in order to determine last numeric/text values in ranges of interest.

How about performance differences?

What follows compares the following sets of formulas:

[1]

=VLOOKUP(B7,AccList!$F$2:$H$9978,3,1)

=VLOOKUP(B7,AccList!$F$2:$L$9978,7,1)

[2]

=LOOKUP(B7,AccList!$F$2:$F$9978,AccList!$H$2:$H$9978)

=LOOKUP(B7,AccList!$F$2:$F$9978,AccList!$L$2:$L$9978)

[3]

=INDEX(AccList!$H$2:$H$9978,MATCH(B7,AccList!$F$2:$F$9978,1))

=INDEX(AccList!$L$2:$L$9978,MATCH(B7,AccList!$F$2:$F$9978,1))

[4]

=INDEX(AccList!$H$2:$H$9978,H7)

=INDEX(AccList!$L$2:$L$9978,H7)

=MATCH(B7,AccList!$F$2:$F$9978,1)

which is in H7.

As is clear, the lookup table is in AccListF2:L9978. Column F houses text-formatted account-numbers and the table is sorted in ascending order on F.

Each formula is copied to 6255 cells.

The figures are averages of 5 runs.

All With BS MrExcel.xls
	A	B	C	D	E	F	G	H	I
1		FastExcelWorkBookProfile					Version2.0Build434
2	WorkBookSummary
3				CalcTime(Millisec)		%	MicroSecs	Range	Total
4		Const	Formula	ReCalc	FullCalc	Volatile	/Formula	Mem(K)	Mem(K)
5	[1]VLOOKUP	94,935	12,522	0.2	115.6	0.2%	9.2	2,071	2,136
6	[2]LOOKUP	94,935	12,522	0.2	109.7	0.2%	8.8	2,119	2,208
7	[3]INDEX/MATCH(a)	94,935	12,522	0.2	118.2	0.2%	9.4	2,195	2,260
8	[4]INDEX/MATCH(b)	94,935	18,783	0.2	91.9	0.3%	4.9	2,319	2,406
9
FastXL

 

[fairwinds]

Hi,

How do I interpret no 4, is there one Match formula for each index formula?

 

[Aladin Akyurek]

Hi,

How do I interpret no 4, is there one Match formula for each index formula?

No, just one for both. MATCH determines in H7 the position of B7. INDEX pulls off values from two different columns.

 

[fairwinds]

So even if I had one match for each index it should be a little faster than Index / match combination (in one cell)...?

 

[Zack Barresse]

so the INDEX/MATCH combo is slightly bulkier and uses slightly more memory to function. but in the same breath, if you break apart the two functions and use in conjunction with each other from different cells, your memory usage will go up yet re-calc time will inversely go down drastically. am i following this right so far? so from the above example, i would have to conclude that it is sometimes much more effective, if measuring performance standards, to break apart computations which rely on each other, keeping in mind the desired results and route/method used to achieve them. maybe not all the time, but where the occasion presents itself.

or do i need more coffee today

 

[Aladin Akyurek]

so the INDEX/MATCH combo is slightly bulkier and uses slightly more memory to function. but in the same breath, if you break apart the two functions and use in conjunction with each other from different cells, your memory usage will go up yet re-calc time will inversely go down drastically. am i following this right so far? so from the above example, i would have to conclude that it is sometimes much more effective, if measuring performance standards, to break apart computations which rely on each other, keeping in mind the desired results and route/method used to achieve them. maybe not all the time, but where the occasion presents itself.

or do i need more coffee today

That's right. That's also why I often suggest a 2-cell approach instead of:

=IF(ISNA(VLOOKUP()),X,VLOOKUP())

The issue is knows as space/time trade off.

 

[Zack Barresse]

That's right. That's also why I often suggest a 2-cell approach instead of:

=IF(ISNA(VLOOKUP()),X,VLOOKUP())

The issue is knows as space/time trade off.

gotcha. never did like that type of combo anyway. usually becomes quite cumbersome. but nonetheless, your results are interesting and provokes one to examine their judgement call/s on providing 'the right solution' to a question.

btw, thank you very much for taking the time to examine that question. i appreciate it!

 

[Aladin Akyurek]

So even if I had one match for each index it should be a little faster than Index / match combination (in one cell)...?

Yes. It's better performancewise for example to replace:

=VLOOKUP(LookupVal,$A$2:$D$2000,2,MatchType)

=VLOOKUP(LookupVal,$A$2:$D$2000,3,MatchType)

=VLOOKUP(LookupVal,$A$2:$D$2000,4,MatchType)

or

{=VLOOKUP(LookupVal,$A$2:$D$2000,{2,3,4},MatchType)}

with

X2:

=MATCH(LookupVal,$A$2:$A$2000,MatchType)

=INDEX(B$2:B$2000,$X2)

copied across.

 

[fairwinds]

Thanks!

 

[shades]

Thanks, Aladin. We have one spreadsheet that has thousands of lookups exactly like that. And it takes a while to re-calculate. It isn't my spreadsheet, but the person has asked about trying to speed it up. I am looking forward to making the substitutions recommended here to see what happens.