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

 

[Zack Barresse]

Yes. It's better performancewise...

let me ask you this:

do you think it would ever be more advantageous to couple the two fore-mentioned functions together to save space memory wise, and sacrafice re-calc time? it would seem to me that it'd have to be a pretty hefty workbook with extremely large areas of data. and if this was the case, you'd already be at a disadvantage in regards to re-calc time.

 

[Aladin Akyurek]

Yes. It's better performancewise...

let me ask you this:

do you think it would ever be more advantageous to couple the two fore-mentioned functions together to save space memory wise, and sacrafice re-calc time? it would seem to me that it'd have to be a pretty hefty workbook with extremely large areas of data. and if this was the case, you'd already be at a disadvantage in regards to re-calc time.

The MATCH bit in separate cells in the exhibit accounts for ~200K additional memory. That doesn't look like a big issue...

 

[Zack Barresse]

The MATCH bit in separate cells in the exhibit accounts for ~200K additional memory. That doesn't look like a big issue...

i know. i must've come across wrong. i was thinking more along the lines of your exhibit x1,000, even x10,000 in some people's cases. i guess it would be more of a non-issue if they are attempting to steamline efficiency for their workbook/s anyway.

 

[Aladin Akyurek]

The MATCH bit in separate cells in the exhibit accounts for ~200K additional memory. That doesn't look like a big issue...

i know. i must've come across wrong. i was thinking more along the lines of your exhibit x1,000, even x10,000 in some people's cases. i guess it would be more of a non-issue if they are attempting to steamline efficiency for their workbook/s anyway.

One issue that never gets rised is whether the lookup formulas should be used as a means of copying large chunks of a large area of data. After that, further processing is applied to the retrieved data. One wonders why such processing is not applied directly to the source area.

 

[Brian from Maui]

Aladin,

Since you're still up and I joined this thread rather late, much like ridding the #N/A in Vlookup, efficiency wise, replace Vlookup with a two step approach using Match then Index?

 

[Zack Barresse]

agreed. i believe that to be, imho, a 'flexibility' issue if you will - for the user. as i've done many times in the past (as in your description) it seems to add a measure of control the user manifests in their worksheets. i could be wrong, like in many cases, but that's how it appears to me at times.

{hiya Brian }

 

[Aladin Akyurek]

Aladin,

Since you're still up and I joined this thread rather late, much like ridding the #N/A in Vlookup, efficiency wise, replace Vlookup with a two step approach using Match then Index?

Like...

In C2:

=MATCH(A2,$X$2:$X$100,0)

In B2:

=IF(ISNUMBER(C2),INDEX($Y$2:$Y$100,C2),"")

would be similar to, perhaps lightly faster,...

In C2:

=VLOOKUP(A2,$X$2:$X$100,2,0)

In B2:

=IF(ISNA(C2),"",C2)

 

[Brian from Maui]

GEEZ!,

Just when I changed all my Vlookups to =IF(ISNA(A10)......

At my age, change is difficult!!!!

Hey Zack...get some sleep tonight!

 

[Zack Barresse]

and...

In C2:

=MATCH(A2,$X$2:$X$100,0)

In B2:

=IF(ISNUMBER(C2),INDEX($Y$2:$Y$100,C2),"")

compared to this...

=IF(ISNUMBER(MATCH(A2,$X$2:$X$100,0)),INDEX($Y$2:$Y$100,C2),"")

could be more beneficial efficiency wise. if i'm understanding you.