Developing Faster Lookups - Part 2 - How to build a faster VBA Lookup

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
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).

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,InpurRange).

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 AVLOOKUP function.
FLOOKUP does not contain these AVLOOKUP 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

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!

So now all I have to do is rewrite the AVLOOKUP family of functions into C++ to exploit multi-threading, improved performance and the lower UDF overhead of the XLL.

About these ads