Problem 934. Find: Faster Alternatives for Large Sorted/Unique Vectors

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Challenge is to create faster Find methods for large unique ascending vectors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Methods exist that are 1000 times faster than Find.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Methods have applications where data files are loaded for multiple searches(Rubik's Mini Cube, DNA).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [a,val]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>a: vector [N large,1] of type uint32 that is unique and sorted ascending</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>val: The value to find in the \"a\" vector. Val will exist in \"a\".</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> [ptr]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>ptr: The index in array \"a\" where a(ptr) is val</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Score:</w:t></w:r><w:r><w:t> Time in msec to find 200 random values in a 12,000,000 long vector</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The basic find(a==val,1,'first') takes approximately 14 seconds (12M, 200 cases).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>High performance find_fast can find 200 values in 4 to 12 milli-seconds for a 12M vector.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Find time increases linearly with the array size. High performance methods don't appear to incur any increased processing time.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Hints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>There are multiple methods that significantly outperform find.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Bisect searches</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Predictive searches</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Combining Bisect/Predictive with a Linear Chaser</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A static goal vector find time could be enhanced by a Pre-Index array. Not applicable to this challenge.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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]<ul><li>a: vector [N large,1] of type uint32 that is unique and sorted ascending</li><li>val: The value to find in the "a" vector. Val will exist in "a".</li></ul>Output: [ptr]<ul><li>ptr: The index in array "a" where a(ptr) is val</li></ul>Score: Time in msec to find 200 random values in a 12,000,000 long vectorThe 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:<ul><li>There are multiple methods that significantly outperform find.</li><li>Bisect searches</li><li>Predictive searches</li><li>Combining Bisect/Predictive with a Linear Chaser</li><li></li></ul>A static goal vector find time could be enhanced by a Pre-Index array. Not applicable to this challenge.

Solve

Solution Stats

132 Solutions
27 Solvers

Last Solution submitted on Jul 16, 2018

Last 200 Solutions

Problem Comments

Solution Comments

Solution 897471

1 Comment

1 Comment

Tom Purcell on 27 May 2016

Yay, 10 msec! Any way to compare solutions by timing performance?

Problem Recent Solvers27

Problem Tags

alternate enhancement find profiling speed optimization

Problem 934. Find: Faster Alternatives for Large Sorted/Unique Vectors

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers27

Suggested Problems

More from this Author236

Problem Tags

Problem 934. Find: Faster Alternatives for Large Sorted/Unique Vectors

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers27

Suggested Problems

More from this Author236

Problem Tags

Players