search

beeminder / road

Beebrain and Visual Graph Editor
http://graph.beeminder.com
Other
11 stars 3 forks source link

More efficient filtering of datapoints, redline segments, and isolines #143

Open saranli opened 3 years ago

saranli commented 3 years ago

Right now we're using Javascript's filter() function for filtering various data arrays such as datapoints, the graph matrix, and isolines. However, these arrays are already sorted, and filtering is usually done to figure out which elements are within the graph range. That could easily be done with binary search on graph boundaries within the array, potentially resulting in improvements in drawing efficiency and speed.

So, I think we need to assess which ones are bottlenecks, especially for goals with lots of datapoints and graph matrix rows and see if this will improve speed.

dreeves commented 3 years ago

Relatedly, we've implemented binary search in at least 4 different places in Beebrain:

  1. stepify
  2. findSeg
  3. isoside
  4. searchby (for finding isolines, etc)
dreeves commented 3 years ago

PS: I cleaned up all the binary searching and refactored all the binary searching to use a pair of functions: searchHigh & searchLow! It made a lot of things simpler and killed some ugly and conceivably slightly inefficient code that scooched indexes one by one to deal with weirdo special cases. And it even led to fixing at least one bug. 🎉

The actual gissue here -- not doing O(1) filters all over the place on already-sorted arrays -- remains open!