Problem 934. Find: Faster Alternatives for Large Sorted/Unique Vectors
The Challenge is to create faster Find methods for large unique ascending vectors.
Methods exist that are 1000 times faster than Find.
Methods have applications where data files are loaded for multiple searches(Rubik's Mini Cube, DNA).
Input: [a,val]
- a: vector [N large,1] of type uint32 that is unique and sorted ascending
- val: The value to find in the "a" vector. Val will exist in "a".
Output: [ptr]
- ptr: The index in array "a" where a(ptr) is val
Score: Time in msec to find 200 random values in a 12,000,000 long vector
The basic find(a==val,1,'first') takes approximately 14 seconds (12M, 200 cases).
High performance find_fast can find 200 values in 4 to 12 milli-seconds for a 12M vector.
Find time increases linearly with the array size. High performance methods don't appear to incur any increased processing time.
Hints:
- There are multiple methods that significantly outperform find.
- Bisect searches
- Predictive searches
- Combining Bisect/Predictive with a Linear Chaser
A static goal vector find time could be enhanced by a Pre-Index array. Not applicable to this challenge.
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers35
Suggested Problems
-
Find the numeric mean of the prime numbers in a matrix.
8948 Solvers
-
Find the "ordinary" or Euclidean distance between A and Z
162 Solvers
-
First non-zero element in each column
864 Solvers
-
331 Solvers
-
We love vectorized solutions. Problem 1 : remove the row average.
828 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!