search

willow-ahrens / Finch.jl

Sparse tensors in Julia and more! Datastructure-driven array programing language.
http://willowahrens.io/Finch.jl/
MIT License
159 stars 15 forks source link

Exponential Scansearch #569

Closed kylebd99 closed 4 months ago

kylebd99 commented 4 months ago

Small update to the scansearch function which replaces the linear + binary search with an exponential search algorithm.

willow-ahrens commented 4 months ago

oh cool! just a small comment here: There may be a few situations (e.g. a follow protocol on a sparse list) where we assume the destination is random, not nearby, so we may want to put a normal binary search in the codebase as well.

kylebd99 commented 4 months ago

Added a binary search back in as binary_scansearch!

willow-ahrens commented 4 months ago

Thanks Kyle! Did this lead to any speedups?