# How can I optimize this search routine? **URL:** \ **Category:** help\ **Created:** [March 22, 2019, 1:54am UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526 "2019-03-22T01:54:09Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 1:54am UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/1 "2019-03-22T01:54:09Z")
Hello, I'm making a datastructure (I called it `SparseArraySparseModeData`) to efficiently store a sparse vec. What it does is that it stores both the address, and the value of each element. To get the value at an index, it runs a hybrid binary-interpolation search on the vector of addresses. It's slow, though - the "hot" function is called `find_address`, which does the searching. The address vector is assumed to have 4 sections, each of which is piecewise linear. Any ideas on how to optimize it (just "for fun")? The code is [here](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=f57900196e1a9ae0a535a34cf62d1c32). Thanks, ndrewxie ---
**Author:** ![hellow](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/hellow/32/11281_2.png) [@hellow](https://users.rust-lang.org/u/hellow)\ **Post date:** [March 22, 2019, 11:01am UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/2 "2019-03-22T11:01:30Z")
Your playground is very unfriendly for testing. Let's please take a few steps back and do it properly. - First clean up the playground and remove everything unrelated (I managed to strip it down to ~140LOC). - Next, [add test cases](https://doc.rust-lang.org/book/ch11-00-testing.html) where on can assert, that one don't change anything unintended (we don't know the topic as well as you do, so we might screw things up). - Last, [add benchmarks](https://doc.rust-lang.org/1.7.0/book/benchmark-tests.html) so, we can proplery tell if we managed to do something. Only this way we can really help you. Also this will help you to write maintainable and reliable code. Also, please use `rustfmt` to properly format the code, add empty lines between two functions and don't sprinkle everything with `inline`. The compiler will automatically decide if it's worth inlining. The compiler is probably smarter than you (and me 😉 ). ---
**Author:** ![nakacristo](https://avatars.discourse-cdn.com/v4/letter/n/c0e974/32.png) [@nakacristo](https://users.rust-lang.org/u/nakacristo)\ **Post date:** [March 22, 2019, 1:14pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/3 "2019-03-22T13:14:17Z")
There is something wrong with the order of the operations in the interpolation. Setting loading=0 and some fixes I reduce the ratio to 4. > **[Rust Playground](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=2e419fa306c977bd4421630a0a6da149)** > > A browser interface to the Rust compiler to experiment with the language ---
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 1:39pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/4 "2019-03-22T13:39:38Z")
yeah, loading=0 is just pure interpolation search ---
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 1:43pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/5 "2019-03-22T13:43:32Z")
What's your estimate for the maximum size of an array such that binary search is faster than interpolation search (if the array is small enough, the fewer comparisons and less expensive arithmetic would make binary search faster, even though it only removes half of the array per iteration)? ---
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 2:00pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/6 "2019-03-22T14:00:42Z")
I made a program to empirically determine loading. Looks like 0 is really the best! > **[Rust Playground](https://play.rust-lang.org/?version=nightly&%3Bmode=release&%3Bedition=2018&%3Bgist=f5e1441bbb6314c8ade36df5df4806eb)** > > A browser interface to the Rust compiler to experiment with the language ---
**Author:** ![nakacristo](https://avatars.discourse-cdn.com/v4/letter/n/c0e974/32.png) [@nakacristo](https://users.rust-lang.org/u/nakacristo)\ **Post date:** [March 22, 2019, 3:04pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/7 "2019-03-22T15:04:57Z")
That seems right, at least for the average case. There must be some lists for which at some indices it works better binary search than interpolation. Depending the goal it could be useful to try to improve those worst cases. I was thinking that maybe for small slices it could be better to just check all locations. Have looked upon this? I have run a few tests and it is not clear. EDIT: Of course that interpolation is best and there is not difference with smaller threshold. If the example list is a list with constant stride then interpolation needs just one iteration to reach the solution. The situation is different if we use a random list as input, where strides can be different: [Rust Playground](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=d6bb8293818d326314f8da41e24c996b) ---
**Author:** ![ExpHP](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/exphp/32/13145_2.png) [@ExpHP](https://users.rust-lang.org/u/ExpHP)\ **Post date:** [March 22, 2019, 5:52pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/8 "2019-03-22T17:52:43Z")
No follow-up to your [last thread](https://users.rust-lang.org/t/faster-alternative-to-binary-search/26443)? I and several others asked many questions about your problem size and use case, and a number of us shared the sentiment that splitting your array was unlikely to solve anything regardless of the circumstances. I feel like we were ignored, and that makes it discouraging to try to provide further help. ---
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 5:55pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/9 "2019-03-22T17:55:50Z")
Sorry about that! I'll follow up as soon as possible (on mobile so typing's slow) ---
**Author:** ![ndrewxie](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/ndrewxie/32/9041_2.png) [@ndrewxie](https://users.rust-lang.org/u/ndrewxie)\ **Post date:** [March 22, 2019, 6:19pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/10 "2019-03-22T18:19:10Z")
I replaced the final binary search with linear search, and with loading = 50, I got a ratio of about 2 - [code is here](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=655a2d6119ae7f9d4daac035ae181b49) ---
**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\ **Post date:** [April 21, 2019, 6:19pm UTC](https://users.rust-lang.org/t/how-can-i-optimize-this-search-routine/26526/11 "2019-04-21T18:19:10Z")
Closed on April 21, 2019, 6:19pm UTC This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.