October 24, 2016 at 21:04Simplify binary search in Excel - Double VLOOKUP Trick implementation using UDF
I will add one more to the piggy bank of Habr's articles about Binary search . It will be a question of a custom implementation, it can be useful to everyone who often uses VPR in their work to compare large lists or to search for data in large arrays.
It all started with the fact that I discovered the so-called Double-TRUE VLOOKUP trick (trick with double use of VLOOKUP and TRUE in the 4th parameter). A detailed description of the algorithm can be found in Charles Williams's article “Why 2 VLOOKUPS are better than 1 VLOOKUP” (at the end of the article).
Understanding the principle of work and discovering that this approach can be in the thousandstimes faster than a conventional linear search (VLOOKUP with the 4th parameter FALSE), I began to think through options to reveal its capabilities. During the implementation, several suitable tools for contextual advertising turned out, one of which I still continue to improve, and have already dedicated a couple of articles to the project on Habré. It is recommended to SEO specialists and contextual advertising specialists (I’ll make a reservation right away, the links in the articles are already outdated versions, the latest version is conditionally 6.0, links to download all versions, including the latest one, will be at the end of this article):
» Analysis of large semantic kernels, or “Recognition Robot”
” Lemmatization in Excel, or“ Recognition Robot 3.0
So, despite the incredible speed of these files (incredible for Excel), their creation required the use of the same incredibly long mega-formulas as one of the components of macros (the last of the above articles gives an example - a 3215-character formula). And all the fault is the complicated syntax of the function.
If you get a hand in using it, it ceases to seem difficult, but inexperienced users for whom this approach is intended are unlikely to want to understand it.
The syntax looks like this:
where n is the serial number of the column from which we want to return the value opposite to the desired key.
Instead of “TRUE” in the 4th parameter, you can use “1” for a nominal reduction in the length of formulas, this does not change their essence.
If you announce the progress of the formula, the following will be:
“If a binary search for a key in the first column of an array returns a value less than the key itself, we return an empty string. Otherwise, we return the result of a binary search for a key with an offset n ”.
The approach is used to not return any values if the key to be found is not in the array, because often, if the desired is not found, we do not need a lower value. So to say, all or nothing. In short, this is the essence of the "trick."
Let me remind you that the increase in speed, calculated in three or four-digit numbers, is at stake. If you approach it purely mathematically - on an array of 2 ^ 20 lines a regular binary search will do ~ 10 calculations, the formula above will be about 20, while a linear search will do ~ 500,000, i.e. the growth of the formula above is 25,000 times. If the bare numbers are not impressive, the more eloquent equivalent comparison is 1 second versus ~ 7 hours.
In practice, the growth is not so significant (at the end of the article there is a link to an article where different methods were compared). This is largely due to the processor time spent on additional procedures that the program performs (for example, writing values to cells). BUT the gain is still critically significant (~ 4000 times).
But at the same time, we have a complex, completely non-usable syntax. Not all mortals were given CMD, what to speak of combinations of 2 CPR with IF.
I solved the issue with complex syntax using VBA - I wrote UDF (user-defined function, user function), which hides our conditional constructions under the hood, leaving us the usual syntax of the well-known VLOOKUP.
UDF Code:
To use a function in your Excel file, to add to the current book module, which add the code above, or downloaded from the link file-example where this has been done for you.
The function accepts 3 parameters as input, the syntax is similar to a normal VLR, except for the 4th parameter, because it is not needed: (required; array; column number) .
So at the output, we got a function with the usual syntax and familiar behavior, but at a speed of tens, hundreds, thousands of times faster than a normal VLOOKUP, depending on the length of the array. With one limitation - the function only works correctly on an array sorted from smallest to largest. Often the last moment is not an insurmountable obstacle.
Use, comment. I will be happy with improvements in the algorithm and similar implementation ideas.
I’m working on search optimization in Python, at the moment I haven’t found it faster than the standard dictionary search, I will be glad to comment on this too.
» An article about a double VLOOKUP trick“ Why 2 VLOOKUPs are better than 1 ”
” Comparison of different search methods, including a “double VLOOKUP trick”
” The latest version of“ Recognition Robot ”and all previous and some other contextual advertising tools, including subject of this article, one link.
Background
It all started with the fact that I discovered the so-called Double-TRUE VLOOKUP trick (trick with double use of VLOOKUP and TRUE in the 4th parameter). A detailed description of the algorithm can be found in Charles Williams's article “Why 2 VLOOKUPS are better than 1 VLOOKUP” (at the end of the article).
Understanding the principle of work and discovering that this approach can be in the thousandstimes faster than a conventional linear search (VLOOKUP with the 4th parameter FALSE), I began to think through options to reveal its capabilities. During the implementation, several suitable tools for contextual advertising turned out, one of which I still continue to improve, and have already dedicated a couple of articles to the project on Habré. It is recommended to SEO specialists and contextual advertising specialists (I’ll make a reservation right away, the links in the articles are already outdated versions, the latest version is conditionally 6.0, links to download all versions, including the latest one, will be at the end of this article):
» Analysis of large semantic kernels, or “Recognition Robot”
” Lemmatization in Excel, or“ Recognition Robot 3.0
So, despite the incredible speed of these files (incredible for Excel), their creation required the use of the same incredibly long mega-formulas as one of the components of macros (the last of the above articles gives an example - a 3215-character formula). And all the fault is the complicated syntax of the function.
If you get a hand in using it, it ceases to seem difficult, but inexperienced users for whom this approach is intended are unlikely to want to understand it.
The syntax looks like this:
If (VLOOKUP (sought; array; 1; TRUE) <searched; ""; VLOOKUP (sought; array; n; TRUE))
where n is the serial number of the column from which we want to return the value opposite to the desired key.
Instead of “TRUE” in the 4th parameter, you can use “1” for a nominal reduction in the length of formulas, this does not change their essence.
If you announce the progress of the formula, the following will be:
“If a binary search for a key in the first column of an array returns a value less than the key itself, we return an empty string. Otherwise, we return the result of a binary search for a key with an offset n ”.
The approach is used to not return any values if the key to be found is not in the array, because often, if the desired is not found, we do not need a lower value. So to say, all or nothing. In short, this is the essence of the "trick."
Let me remind you that the increase in speed, calculated in three or four-digit numbers, is at stake. If you approach it purely mathematically - on an array of 2 ^ 20 lines a regular binary search will do ~ 10 calculations, the formula above will be about 20, while a linear search will do ~ 500,000, i.e. the growth of the formula above is 25,000 times. If the bare numbers are not impressive, the more eloquent equivalent comparison is 1 second versus ~ 7 hours.
In practice, the growth is not so significant (at the end of the article there is a link to an article where different methods were compared). This is largely due to the processor time spent on additional procedures that the program performs (for example, writing values to cells). BUT the gain is still critically significant (~ 4000 times).
But at the same time, we have a complex, completely non-usable syntax. Not all mortals were given CMD, what to speak of combinations of 2 CPR with IF.
I solved the issue with complex syntax using VBA - I wrote UDF (user-defined function, user function), which hides our conditional constructions under the hood, leaving us the usual syntax of the well-known VLOOKUP.
UDF Code:
Public Function БИНПОИСК(a, b As Range, c As Integer) As String
If Application.VLookup(a, b.Columns(1), 1, True) = a Then
БИНПОИСК = Application.VLookup(a, b, c, True)
Else
БИНПОИСК = ""
End If
End FunctionTo use a function in your Excel file, to add to the current book module, which add the code above, or downloaded from the link file-example where this has been done for you.
The function accepts 3 parameters as input, the syntax is similar to a normal VLR, except for the 4th parameter, because it is not needed: (required; array; column number) .
So at the output, we got a function with the usual syntax and familiar behavior, but at a speed of tens, hundreds, thousands of times faster than a normal VLOOKUP, depending on the length of the array. With one limitation - the function only works correctly on an array sorted from smallest to largest. Often the last moment is not an insurmountable obstacle.
Use, comment. I will be happy with improvements in the algorithm and similar implementation ideas.
I’m working on search optimization in Python, at the moment I haven’t found it faster than the standard dictionary search, I will be glad to comment on this too.
References
» An article about a double VLOOKUP trick“ Why 2 VLOOKUPs are better than 1 ”
” Comparison of different search methods, including a “double VLOOKUP trick”
” The latest version of“ Recognition Robot ”and all previous and some other contextual advertising tools, including subject of this article, one link.
