diff options
author | Canop <cano.petrole@gmail.com> | 2019-02-13 18:14:49 +0100 |
---|---|---|
committer | Canop <cano.petrole@gmail.com> | 2019-02-13 18:14:49 +0100 |
commit | 19b9dfea20ae2702d2d83e8175b11e239686a4e0 (patch) | |
tree | e30f1ac5a8fbdbffb980d6fbee12a405ce1798b1 | |
parent | 384adc6aac5500826a271432a4469f65a9765aaf (diff) |
faster regex search
We were applying the same logic to fuzzy patterns and regex patterns:
looking for more results than strictly necessary in order to then
sort them and keep only the best ones.
But today, as there's no way to decide which regex match is better
than another one (because regexes don't try all the possible ways to
match), all results have the same score, so there's no need to look
for more results.
-rw-r--r-- | src/fuzzy_patterns.rs | 7 | ||||
-rw-r--r-- | src/patterns.rs | 9 | ||||
-rw-r--r-- | src/regex_patterns.rs | 7 | ||||
-rw-r--r-- | src/tree_build.rs | 17 |
4 files changed, 27 insertions, 13 deletions
diff --git a/src/fuzzy_patterns.rs b/src/fuzzy_patterns.rs index a5c5164..8685700 100644 --- a/src/fuzzy_patterns.rs +++ b/src/fuzzy_patterns.rs @@ -8,7 +8,7 @@ use std::fmt::{self, Write}; // weights used in match score computing const BONUS_MATCH: i32 = 50_000; const BONUS_EXACT: i32 = 1_000; -const BONUS_START: i32 = 20; +const BONUS_START: i32 = 10; const BONUS_START_WORD: i32 = 5; const BONUS_CANDIDATE_LENGTH: i32 = -1; // per char const BONUS_LENGTH: i32 = -10; // per char of length of the match @@ -122,4 +122,9 @@ impl FuzzyPattern { } best_match } + // return the number of results we should find before starting to + // sort them (unless time is runing out). + pub fn optimal_result_number(&self, targeted_size: usize) -> usize { + 20 * targeted_size + } } diff --git a/src/patterns.rs b/src/patterns.rs index d132710..fd21af7 100644 --- a/src/patterns.rs +++ b/src/patterns.rs @@ -58,6 +58,15 @@ impl Pattern { pub fn take(&mut self) -> Pattern { mem::replace(self, Pattern::None) } + // return the number of results we should find before starting to + // sort them (unless time is runing out). + pub fn optimal_result_number(&self, targeted_size: usize) -> usize { + match self { + Pattern::Fuzzy(fp) => fp.optimal_result_number(targeted_size), + Pattern::Regex(rp) => rp.optimal_result_number(targeted_size), + Pattern::None => targeted_size, + } + } } /// A Match is a positive result of pattern matching diff --git a/src/regex_patterns.rs b/src/regex_patterns.rs index 912ff75..16d5e22 100644 --- a/src/regex_patterns.rs +++ b/src/regex_patterns.rs @@ -53,4 +53,11 @@ impl RegexPattern { None => None, } } + // return the number of results we should find before starting to + // sort them (unless time is runing out). + // In the case of regexes, there's no need to find more results, as + // their score is always 1 + pub fn optimal_result_number(&self, targeted_size: usize) -> usize { + targeted_size + } } diff --git a/src/tree_build.rs b/src/tree_build.rs index cd380c0..b3a9378 100644 --- a/src/tree_build.rs +++ b/src/tree_build.rs @@ -344,6 +344,7 @@ impl TreeBuilder { let start = Instant::now(); let mut out_blines: Vec<usize> = Vec::new(); // the blines we want to display (indexes into blines) let not_long = Duration::from_millis(600); + let optimal_size = self.options.pattern.optimal_result_number(self.targeted_size); out_blines.push(0); let mut nb_lines_ok = 1; // in out_blines let mut open_dirs: VecDeque<usize> = VecDeque::new(); @@ -351,17 +352,9 @@ impl TreeBuilder { self.load_children(0); open_dirs.push_back(0); loop { - if self.options.pattern.is_some() { - if (nb_lines_ok > 30 * self.targeted_size) - || (nb_lines_ok >= self.targeted_size && start.elapsed() > not_long) - { - break; - } - if task_lifetime.is_expired() { - info!("task expired (core build - outer loop)"); - return None; - } - } else if nb_lines_ok >= self.targeted_size { + if (nb_lines_ok > optimal_size) + || (nb_lines_ok >= self.targeted_size && start.elapsed() > not_long) + { break; } if let Some(open_dir_idx) = open_dirs.pop_front() { @@ -383,7 +376,7 @@ impl TreeBuilder { break; } for next_level_dir_idx in &next_level_dirs { - if self.options.pattern.is_some() && task_lifetime.is_expired() { + if task_lifetime.is_expired() { info!("task expired (core build - inner loop)"); return None; } |