In part 1 I looked at some of the difficulties with making efficient use of Excel’s built-in Lookup and Match functions:

- Lookups are often recalculated unecessarily even when all data actually relevant to the Lookup is unchanged.
- Binary Search Lookup requires a double lookup to handle missing data
- Linear Search requires either a double lookup or IFERROR to handle the #N/A from missing data
- Excel’s Lookup and Match functions are not designed to handle multiple results
- Whole-column arguments are handled well as long as the used-range is OK

An ideal Lookup/Match function would handle these problems and also

- Allow Named column headers as well as numbers
- Allow more than one column as the Lookup Value
- Allow alternative sets of Lookup Values
- VLOOKUP would handle both ascending and descending sorted data

And of course it has to be faster than Excel’s functions in most circumstances!

What I finally developed was the AVLOOKUP/AMATCH/AVLOOKUPS/AMATCHS series of UDFs in FastExcel Version2 and 3

This post describes the design approach and shows some sample code from these UDFs.

## The Design Approach

### Solution for No Relevant Data Changed

The solution I chose was to store the row number in the TableRange where the answer was last found, and then before doing the actual lookup check whether that row number still gives the right answer. If it does then short-circuit the UDF by returning the answer, else go do the full lookup.

There is a small problem with this approach in that a VBA UDF is not supposed to be able to alter anything except by returning values to its calling cells, **so how do you store the Row number? **The solution I chose is to to use the Range.ID property for the calling cell. This works well (althought it only persists for the duration of the Excel workbook session). In the multi-threaded C++ FastExcel V3 version I use lockable global memory mapped structures stored within the workbook.

The great thing about this approach is that it is fail-safe and avoids having to handle some tricky situations: if there are 2 UDF calls using this technique within a formula the first call will get the row number stored by the second call, decide that this gives the wrong answer and then do the full lookup to get the right answer.

### Binary Search with Missing Data

Part 1 showed how to make this work by making a lookup lookup itself to see if it has found an approximate or an exact match. So you need to have 2 arguments for the function (Data_Is_Sorted and Do_Exact_Match) instead of just one (Data_Is_Sorted). Then if the data is sorted and an Exact Match is requested the UDF can do the Binary Search exact match trick.

### Handling the #N/A from Missing Data

This also requires another optional parameter for the UDF, giving the Value to return if an exact match has been requested but not found (defaults to #N/A).

### Optimizing Data Transfer

To minimise data transfer time if the Lookup_Table is a range then the UDF keeps it as a range and passes the range object to Application.WorksheetFunction.MATCH, instead of transferring all the data to a Variant array and then either searching that using VBA or passing the variant array to MATCH. If the input is a calculated range or array constant rather than a Range then the UDF passes that directly to MATCH.

When checking if the stored row number gives the right answer the UDF does need to get a value, but it only gets a single cell.

### Handling Whole Column arguments

Because the UDF is passing Range Objects rather than Variant arrays to Excel worksheet functions it does not really need to bother about this. In other cases the trick would be to use Application.Intersect(UsedRange,InputRange).

### Handling Multiple Results & Alternative sets of Lookup Values

This is handled by writing the UDF so that it loops on the inputs and lookups and returns an array of results rather than a single value.

### Named Column Headers

If the Answer Column parameter is passed as a string then the UDF searches for it in the first row of the data, but if its passed as a number then that is used as the column index.

### Ascending and descending Sorted data

Internally the UDF uses Excel’s MATCH function which handles both sort types.

## Example code – the FLOOKUP UDF

FLOOKUP is a simplified version of the FastExcel V3 AVLOOKUP2 function.

**FLOOKUP does not contain these AVLOOKUP2 features**:

- Calculated columns/ranges or constant array arguments
- Named Column headers
- Multiple Answers
- More than one column as the Lookup Value
- Alternative sets of Lookup Values
- Function Wizard Help
- Multi-threaded execution
- Lookup memory persisted in saved workbook
- Named Lookup Memory sets
- Written in C++ as an XLL

### FLOOKUP VBA Code

Option Explicit Option Base 1 Option Compare Text ' ' COPYRIGHT © DECISION MODELS LIMITED 2006, 2007, 2011. All rights reserved ' May be redistributed for free but ' may not be sold without the author's explicit permission. ' Public Function FLOOKUP(lookup_value As Variant, _ Lookup_Range As Range, _ Answer_ColNum As Variant, _ Optional Sort_Type As Variant, _ Optional Exact_Match As Variant) ' ' FLOOKUP UDF: Fast Lookup ' ' find the Lookup_Value in the first column of Lookup_Range ' and return the corresponding row value from Answer_Colnum ' ' Sort_Type may be: ' -1 = sorted descending ' 1 = sorted ascending ' 0 = not sorted ' ' Exact_Match may be: True or False or any Non-Boolean value or string ' Exact_Match is returned if there is no exact match ' ' Sort_Type is optional and defaults to 1 ' Exact_Match is optional and defaults to False if sorted, or #N/A if unsorted ' Dim vAnsa As Variant ''' output to be assigned to function Dim vRow As Variant ''' the row number found in Lookup_Range else error Dim vNoMatch As Variant ''' the value to return if no exact match found Dim lSorted As Long ''' -1 =descending, 0= not sorted, 1=ascending Dim jAnswerColumn As Long ''' the answer column number in Lookup_Range Dim blExact As Boolean ''' exact match flag Dim blFound As Boolean ''' true if a match found ' ' setup error handler ' On Error GoTo FuncFail ' ' skip execution if empty or uncalculated inputs ' If IsEmpty(lookup_value) Or IsEmpty(Lookup_Range(1, 1)) Or IsEmpty(Answer_ColNum) Then Exit Function End If ' ' convert defaults etc ' SetDefaults Sort_Type, lSorted, Exact_Match, vNoMatch, blExact, _ Answer_ColNum, jAnswerColumn ' ' now try to find the lookup_value ' blFound = False If Not blExact Then ' ' approx match sorted requested ' On Error Resume Next vRow = Application.WorksheetFunction.Match(lookup_value, Lookup_Range.Columns(1), lSorted) If Err = 0 Then blFound = True On Error GoTo FuncFail Err.Clear Else ' ' exact match requested ' ' first check memory, If matches then done ' vRow = lMemoryId(Application.Caller) If vRow > 0 Then ' ' check value in column 1 against Lookup_Value ' If vRow <= Lookup_Range.Rows.Count Then If Lookup_Range(vRow, 1) = lookup_value Then blFound = True End If End If End If ' ' no memory or memory does not match ' If Not blFound Then ' ' look for the row ' vRow = Application.Match(lookup_value, Lookup_Range.Columns(1), lSorted) ' ' if unsorted and nomatch vRow contains error ' If Not IsError(vRow) Then If lSorted = 0 Then blFound = True Else ' ' we have a potential row: check against Lookup_Value ' If Lookup_Range(vRow, 1) = lookup_value Then blFound = True End If End If End If End If ' ' return the value ' If Not blFound Then ' ' unsuccessful Exact Match: return the given error value ' FLOOKUP = vNoMatch Else ' ' successful: get answer from column ' FLOOKUP = Lookup_Range(vRow, jAnswerColumn) End If ' ' store memory ' If blExact Then Call StoreID(Application.Caller, vRow) End If Exit Function FuncFail: FLOOKUP = CVErr(xlErrValue) Exit Function End Function Private Sub SetDefaults(Sort_Type As Variant, lSorted As Long, Exact_Match As Variant, _ vNoMatch As Variant, blExact As Boolean, _ Answer_ColNum As Variant, jAnswerColumn As Long) ' ' sorted defaults to sort ascending : 1 ' lSorted = 1 If Not IsMissing(Sort_Type) Then lSorted = CLng(Sort_Type) ' ' set blExact and vNoMatch ' vNoMatch = CVErr(xlErrNA) blExact = True ' If IsMissing(Exact_Match) Then ' ' Exact_Match defaults to False if Sorted, #N/A if unsorted ' If lSorted <> 0 Then blExact = False Else ' ' do exact match unless sorted and exact match=false ' vNoMatch = Exact_Match If VarType(vNoMatch) = vbBoolean And lSorted <> 0 Then If Not vNoMatch Then blExact = False End If End If ' ' answer column must be convertible to long ' jAnswerColumn = CLng(Answer_ColNum) End Sub Private Function lMemoryId(oCaller As Range) As Long ' ' get the ID from the calling cell and convert to long ' Dim vID As Variant lMemoryId = 0 On Error GoTo FuncFail ' ' ID property not available in Excel 97 ' If Val(Left(Application.Version, 2)) > 8 And Not oCaller Is Nothing Then vID = oCaller.ID If vID <> "" And IsNumeric(vID) Then lMemoryId = CLng(vID) End If End If FuncFail: End Function Private Sub StoreID(oCaller As Range, vRowNum As Variant) ' ' store the id in the calling cell ' If Not oCaller Is Nothing And Val(Left(Application.Version, 2)) > 8 Then oCaller.ID = CStr(vRowNum) End If End Sub

### Performance Comparison of FLOOKUP and VLOOKUP

These comparisons are done using Excel 2010 32-bit, but with multi-threading calculation switched off.

The data range is 32000 rows and timings are for 10 function calls.

Vlookup Error handling is using the double lookup method rather than IFERROR.

**Case 1: Approx Match on sorted data**

- VLOOKUP 0.53 Millisecs
- FLOOKUP 1.01 Millisecs

**Case 2: Exact Match on Unsorted Data (Midpoint)**

- VLOOKUP 2.65 Millisecs
- FLOOKUP 1.28 Millisecs (second call)

**Case 3: Exact Match – Unsorted Data – No Match found – return #N/A**

- VLOOKUP 4.64 Millisecs
- FLOOKUP 5.43 Millisecs

**Case 4: Exact Match – Unsorted Data – with Error Handling (Midpoint)**

- VLOOKUP 4.5 Millisecs
- FLOOKUP 1.29 Millisecs (second call)

**Case 5: Exact Match – Unsorted Data – with Error Handling (No Match found)**

- VLOOKUP 4.66 Millisecs
- FLOOKUP 5.48 Millisecs

**Case 6: Exact Match – Sorted Data – With Error Handling (Midpoint)**

- VLOOKUP 4.56 millisecs (Double Exact Lookup)
- VLOOKUP 0.6 Millisecs (Double Sorted Lookup trick)
- FLOOKUP 1.35 Millisecs

**Case 6: Exact Match – Sorted Data – With Error Handling (No Match Found)**

- VLOOKUP 4.63 Millisecs (Double Exact Lookup)
- VLOOKUP 0.58 Millisecs (Double Sorted Lookup trick)
- FLOOKUP 1.49 Millisecs

## Summary

- Although VBA UDFs have a higher overhead than Excel’s native functions carefully written functions can perform well.
- Using memory with unsorted exact matches can significantly improve LOOKUP performance.
- The double sorted lookup trick is significantly faster than Linear search on sorted data with missing values.
**FLOOKUP and the double sorted lookup trick win 4 out of the 6 tests!**

** I have now rewriten the AVLOOKUP family of functions into C++ to exploit multi-threading, improved performance, the lower UDF overhead of the XLL interface and to persist the lookup memory within a saved workbook.**

You have an error in this line.

If vRow If Lookup_Range(vRow, 1) = lookup_value Then

Thanks Steve, problem with copy and paste from VBA to html. I have fixed it

Hi Charles – I wonder if I could ask a big favour – for you to post a workbook with the VBA, your test data and some timing code? I’d like to see if I can translate your function to VB.NET with Excel-DNA and compare the speed with the VBA, and with your future C++ version…

Hi Govert,

Sure, I have sent you a test workbook.

Charles,

The Range.ID property is part of Excel vba that I was not really aware of. It appears intriguing.

Can you list any other general areas where use of this could offer advantages?

Thanks for keeping me awake,

‘—

Jim Cone

Jim,

The problem with Range.ID is that it does not persist in a saved workbook (actually not sure I have tried it in an xlsx file). The FLOOKUP trick is the only way I use it, but there must be other uses for it.

Charles,

For what it is worth, I’ve come up with another use for the Range,ID property.

In my Special Sort add-in, one sort method requires the position of blank cells within the data be maintained. To do this now, blank cells are filled with the value from cell above and a Range.ID is attached to the cell…

rCell.Value2 = rCell(0, 1).Value2

rCell.ID = “Blank”

When the sort completes the ID’s are removed…

For Each rCell in RangeToSort.Columns(num).Cells

If Len(rCell.ID) Then

rCell.ID = vbNullString

rCell.ClearContents

End if

Next

Checking the length of a non-existent Range.ID does not generate an error.

As I said, FWIW.

Jim,

Sounds cool.

I just tested in XL 2010 and Range.ID still does not persist in a saved workbook.

Hi Charles. I love these articles. I’m planning to point readers of my book here, and wonder if you can unmangle the damage WordPress has done to the code in terms of the usual <> issue.

(I’m also going to suggest they seriously look at the commercial option of FastExcel, which will be a stepchange again in efficiency. But pointing to these two posts is the prelude to that).

Cheers

Jeff

OK – I think I fixed the mangling – happened when I converted to the 2010 theme – I fixed the later posts but forgot to fix the early ones.

Sorry, another question: what does “Double Exact Lookup” mean in relation to the times under cases 6 and 7 above? You mean doing a double lookup on unsorted data?

A double linear search lookup

Hmm. I understand what you mean by the Double Sorted Lookup trick, and why users would use it (Because it’s damn fast, that’s why). But I can’t see anything here that explaines what the Double Exact Lookup / Double Linear Search Lookup is, or when a user would use it.

Can you elaborate further? I’m curious now…

Hi Charles. I’m still curious about what a Double Exact Lookup / Double Linear Search Lookup is, and when a user would use it. Thought I’d give this thread a nudge in case you’re able to elaborate further. Apologies if you can’t spare the time just now… I expect you’re every bit as busy as I am. But if you can, there’s a glass of Central Otago Rabbit Ranch in it for you, provided you can pick it up from Wellington. Otherwise I’ll just toast your answer from here as I drain it in your honor. 🙂

Jeff, If you can’t use IFERROR with linear exact search for compatibility reasons (less likely now than when this post was written) then you have to use IF wrapping 2 exact match lookups.

Ahhh. Gotcha. Prost!

Charles, your SetDefaults function needs a slight tweak, because as coded it is impossible for blExact to be set to TRUE.

Here’s the code you have. As you can see, blExact will remain False even if Exact_Match is true.

‘ do exact match unless sorted and exact match=false

‘

vNoMatch = Exact_Match

If VarType(vNoMatch) = vbBoolean And lSorted 0 Then

If Not vNoMatch Then blExact = False

End If

End If

Apologies, I’ve pointed at the wrong bit. (I hadn’t realised that earlier you’d set blExact = true)

The bit that needs a tweak is to do with this:

‘ set blExact and vNoMatch

vNoMatch = CVErr(xlErrNA)

blExact = True

…because just a little bit further below, you overwrite that vNoMatch variable in all cases:

' do exact match unless sorted and exact match=false

'

vNoMatch = Exact_Match

If VarType(vNoMatch) = vbBoolean And lSorted 0 Then

If Not vNoMatch Then blExact = False

End If

…meaning that even if the user passed in TRUE, if there is not an exact match they won’t see an error…they’ll just see the word TRUE.

I think your intent was for something like this:

vNoMatch = Exact_Match

If VarType(vNoMatch) = vbBoolean And lSorted 0 Then

If vNoMatch Then

vNoMatch = CVErr(xlErrNA)

Else

blExact = False

End If

End If

…and I’d probably be tempted to go one further and let the user pass in either TRUE or 1 just like the other functions do:

' do exact match unless sorted and exact match=false

'

vNoMatch = Exact_Match

If VarType(vNoMatch) = vbBoolean Or vNoMatch = 1 Then

If lSorted 0 Then

If vNoMatch Then

vNoMatch = CVErr(xlErrNA)

Else

blExact = False

End If

Else: blExact = False

End If

End If

…although I’m sure that extra IF could be restructured out with a slight tweak.

@Jeff, Exact_Match is what to return if no exact match is found: for example “Not Found” (so that you don’t need IFERROR). You COULD pass in TRUE for Exact_Match but it would not make much sense to return TRUE if no match was found.

Yeah, I understand that if the data is sorted and an Exact Match is requested the UDF can do the Binary Search exact match trick. I’m just (still) a little confused about the intent behind the line

If VarType(vNoMatch) = vbBoolean.Given the lookup array {1;2;3;5}, I see that:

=FLOOKUP(4,$A$1:$B$4,1,1) returns 3 i.e. inexact match

=FLOOKUP(4,$A$1:$B$4,1,1,”Not Found” returns “Not Found”

=FLOOKUP(4,$A$1:$B$4,1,1,NA()) returns NA()

I also see in terms of that

If VarType(vNoMatch) = vbBoolean And lSorted 0 Thenline that:=FLOOKUP(4,$A$1:$B$4,1,1,FALSE) returns 3, but that FALSE argument is redundant in this case, because =FLOOKUP(4,$A$1:$B$4,1,1)

alsoreturns 3=FLOOKUP(4,$A$1:$B$4,1,1,TRUE) returns “TRUE”, so you’re clearly not expecting TRUE to mean anything in the context of that VarType test.

At the same time, in your post also says under the “Handling the #N/A from Missing Data” heading

This also requires another optional parameter for the UDF, giving the Value to return if an exact match has been requested but not found (defaults to #N/A).And indeed you set

vNoMatch = CVErr(xlErrNA). But it gets overwritten 4 instructions later withvNoMatch = Exact_MatchSo as coded, the only way I can get it to return #N/A for exact binary search is like this:

=FLOOKUP(4,$A$1:$B$4,1,1,NA())

If I understand correctly, then

as coded, both thatvNoMatch = CVErr(xlErrNA)line and thatIf VarType(vNoMatch) = vbBoolean And lSorted 0 Thenline are redundant, and the statementif an exact match has been requested but not found (defaults to #N/A)is incorrect.Which is why I proposed the coding change above – because given what you say in the post I think that’s the intent. But I’m doing some serious second guessing.