From 3bd8002b58b0408bf9d0f796744fb012b40ba47d Mon Sep 17 00:00:00 2001 From: Han-Wen Nienhuys Date: Mon, 31 Jan 2011 23:37:04 -0200 Subject: [PATCH] Optimize beam scoring. Use a priority queue of scores. This allows us to drop the arbitrary reasonable_score threshold. On morgenlied.ly, this reduces the number of scoring passes from 13.5k to 10.7k. --- lily/beam-quanting.cc | 149 +++++++++++++++++---------- lily/include/beam-scoring-problem.hh | 11 +- 2 files changed, 100 insertions(+), 60 deletions(-) diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc index d5de148b3e..977e5755e0 100644 --- a/lily/beam-quanting.cc +++ b/lily/beam-quanting.cc @@ -20,12 +20,12 @@ #include "beam-scoring-problem.hh" +#include #include using namespace std; #include "align-interface.hh" #include "beam.hh" -#include "directional-element-interface.hh" #include "grob.hh" #include "international.hh" #include "main.hh" @@ -159,7 +159,6 @@ void Beam_scoring_problem::init_stems () lvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0); Drul_array dirs_found (0, 0); - for (vsize i = 0; i < stems.size (); i++) { Grob *s = stems[i]; @@ -186,6 +185,7 @@ void Beam_scoring_problem::init_stems () edge_dirs = Drul_array (stem_infos[0].dir_, stem_infos.back().dir_); } + is_xstaff = Align_interface::has_interface (common[Y_AXIS]); is_knee = dirs_found[LEFT] && dirs_found[RIGHT]; @@ -245,8 +245,6 @@ Beam_scoring_problem::generate_quants (vector *scores) cons unshifted_quants.push_back (i + base_quants[j]); } - - scores->clear (); for (vsize i = 0; i < unshifted_quants.size (); i++) for (vsize j = 0; j < unshifted_quants.size (); j++) scores->push_back (Beam_configuration::new_config (unquanted_y, @@ -254,76 +252,114 @@ Beam_scoring_problem::generate_quants (vector *scores) cons unshifted_quants[j]))); } -Drul_array -Beam_scoring_problem::solve () const { - vector configs; - generate_quants (&configs); - for (vsize i = configs.size (); i--;) +void Beam_scoring_problem::one_scorer (Beam_configuration* config) const +{ + score_count ++; + switch (config->next_scorer_todo) { + case SLOPES: + score_slopes_dy (config); + break; + case FORBIDDEN: + score_forbidden_quants (config); + break; + case STEM_LENGTHS: + score_stem_lengths (config); + break; + + case NUM_SCORERS: + case ORIGINAL_DISTANCE: + default: + assert (false); + } + config->next_scorer_todo++; +} + + +Beam_configuration * +Beam_scoring_problem::force_score (SCM inspect_quants, const vector &configs) const +{ + Drul_array ins = ly_scm2interval (inspect_quants); + Real mindist = 1e6; + Beam_configuration *best = NULL; + for (vsize i = 0; i < configs.size (); i++) { - score_count ++; - score_slopes_dy (configs[i]); + Real d = fabs (configs[i]->y[LEFT]- ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]); + if (d < mindist) + { + best = configs[i]; + mindist = d; + } } + if (mindist > 1e5) + programming_error ("cannot find quant"); - Real reasonable_score = (is_knee) ? 200000 : 100; - for (vsize i = configs.size (); i--;) - if (configs[i]->demerits < reasonable_score) - { - score_count ++; - score_forbidden_quants (configs[i]); - } + return best; +} - for (vsize i = configs.size (); i--;) - if (configs[i]->demerits < reasonable_score) - { - score_count ++; - score_stem_lengths (configs[i]); - } +Drul_array +Beam_scoring_problem::solve () const { + vector configs; + generate_quants (&configs); - int best_idx = best_quant_score_idx (configs); + Beam_configuration *best = NULL; -#if DEBUG_BEAM_SCORING SCM inspect_quants = beam->get_property ("inspect-quants"); if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))) && scm_is_pair (inspect_quants)) { - Drul_array ins = ly_scm2interval (inspect_quants); - - Real mindist = 1e6; - for (vsize i = 0; i < configs.size (); i++) - { - Real d = fabs (configs[i]->y[LEFT]- ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]); - if (d < mindist) - { - best_idx = i; - mindist = d; - } - } - if (mindist > 1e5) - programming_error ("cannot find quant"); - } -#endif - - Interval final_positions; - if (best_idx < 0) - { - warning (_ ("no feasible beam position")); - final_positions = Interval (0, 0); + best = force_score (inspect_quants, configs); } else { - final_positions = configs[best_idx]->y; + std::priority_queue, + Beam_configuration_less> queue; + for (vsize i = 0; i < configs.size(); i++) + queue.push(configs[i]); + + + /* + TODO + + It would be neat if we generated new configurations on the + fly, depending on the best complete score so far, eg. + + if (best->done()) { + if (best->demerits < sqrt(queue.size()) + break; + while (best->demerits > sqrt(queue.size()) { + generate and insert new configuration + } + } + + that would allow us to do away with region_size altogether. + */ + while (true) { + best = queue.top (); + if (best->done ()) + break; + + queue.pop (); + one_scorer (best); + queue.push (best); + } } - + + Interval final_positions = best->y; + #if DEBUG_BEAM_SCORING - if (best_idx >= 0 - && to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))) + if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))) { - configs[best_idx]->score_card_ += to_string ("i%d", best_idx); - // debug quanting - beam->set_property ("quant-score", - ly_string2scm (configs[best_idx]->score_card_)); + int completed = 0; + for (vsize i = 0; i < configs.size (); i++) + { + if (configs[i]->done ()) + completed++; + } + + string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size()); + beam->set_property ("quant-score", ly_string2scm (card)); } #endif @@ -363,7 +399,6 @@ Beam_scoring_problem::score_stem_lengths (Beam_configuration* config) const ideal_score = pow (ideal_score, 1.1); score[d] += length_pen * ideal_score; - count[d]++; } diff --git a/lily/include/beam-scoring-problem.hh b/lily/include/beam-scoring-problem.hh index 8026f43061..755fb388f2 100644 --- a/lily/include/beam-scoring-problem.hh +++ b/lily/include/beam-scoring-problem.hh @@ -23,11 +23,11 @@ #include "interval.hh" #include "lily-proto.hh" +#include "lily-guile.hh" #include "std-vector.hh" #include "stem-info.hh" #include "main.hh" // DEBUG_BEAM_SCORING -// Unused for now. enum Scorers { // Should be ordered by increasing expensiveness. ORIGINAL_DISTANCE, @@ -41,7 +41,6 @@ struct Beam_configuration { Interval y; Real demerits; - #if DEBUG_BEAM_SCORING string score_card_; #endif @@ -58,9 +57,11 @@ struct Beam_configuration // Comparator for a queue of Beam_configuration*. class Beam_configuration_less { +public: bool operator() (Beam_configuration* const& l, Beam_configuration* const& r) { - return l->demerits < r->demerits; + // Invert + return l->demerits > r->demerits; } }; @@ -140,6 +141,10 @@ private: void init_stems (); + void one_scorer (Beam_configuration* config) const; + Beam_configuration *force_score (SCM inspect_quants, + const vector &configs) const; + // Scoring functions: void score_forbidden_quants (Beam_configuration *config) const; void score_slopes_dy (Beam_configuration *config) const; -- 2.39.2