search

rjkroege / edwood

Go version of Plan9 Acme Editor
Other
380 stars 34 forks source link

Make reverse search faster #411

Closed rjkroege closed 2 years ago

rjkroege commented 2 years ago

Reverse search in Edwood is much slower than forward search. From a benchmark added in this CL:

BenchmarkFindForward-10            89755         11822 ns/op
BenchmarkFindBackward-10            1228        987333 ns/op

This is because reverse search ended up running in O(n^2) time instead of O(n). Improve reverse search by re-expressing it in terms of forward search. This fixes #301.

codecov[bot] commented 2 years ago

Codecov Report

Merging #411 (2b274d7) into master (925a3b0) will decrease coverage by 0.01%. The diff coverage is 84.21%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master     #411      +/-   ##
==========================================
- Coverage   53.84%   53.83%   -0.02%     
==========================================
  Files          55       55              
  Lines       10659    10678      +19     
==========================================
+ Hits         5739     5748       +9     
- Misses       4511     4519       +8     
- Partials      409      411       +2
Impacted Files Coverage Δ
regexp/runesb.go 83.03% <84.21%> (-7.29%) :arrow_down:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 925a3b0...2b274d7. Read the comment docs.