From 24f492fd8de73ea9c30e8820da3d7ac6fdda194e Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 8 Sep 2018 16:03:27 +0200 Subject: Improve the speed of the positions search. --- ChangeLog | 7 +++++++ src/search.cc | 6 ++++-- 2 files changed, 11 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index d1e00a6..16fd502 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2018-09-08 Bruno Haible + + Improve the speed of the positions search. + Reported by Frank Wojcik in + . + * src/search.cc (Search::find_positions): Double the speed of step 4. + 2018-09-08 Bruno Haible Really prefer more efficient hash functions over less efficient ones. diff --git a/src/search.cc b/src/search.cc index 959580f..89d912b 100644 --- a/src/search.cc +++ b/src/search.cc @@ -413,11 +413,13 @@ Search::find_positions () Positions best; unsigned int best_duplicates_count = UINT_MAX; + /* Loop over all pairs { i1, i2 } of currently selected positions. + W.l.o.g. we can assume i1 > i2. */ for (int i1 = imax; i1 >= -1; i1--) if (current.contains (i1) && !mandatory.contains (i1)) { - for (int i2 = imax; i2 >= -1; i2--) - if (current.contains (i2) && !mandatory.contains (i2) && i2 != i1) + for (int i2 = i1 - 1; i2 >= -1; i2--) + if (current.contains (i2) && !mandatory.contains (i2)) { for (int i3 = imax; i3 >= -1; i3--) if (!current.contains (i3)) -- cgit v1.2.1