From 5a7eab1d7fad7f5f23202f3631df0545cb7b47e2 Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Wed, 2 May 2007 21:05:40 +1000 Subject: [PATCH] Optimize Optimal_breaking::solve (). --- lily/include/page-breaking.hh | 2 + lily/optimal-page-breaking.cc | 104 ++++++++++++++++++++++++++++------ lily/page-breaking.cc | 69 +++++++++++++++++++++- 3 files changed, 157 insertions(+), 18 deletions(-) diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh index 21edde4a69..aefa1add24 100644 --- a/lily/include/page-breaking.hh +++ b/lily/include/page-breaking.hh @@ -104,6 +104,8 @@ protected: vsize system_count, Line_division lower_bound = Line_division (), Line_division upper_bound = Line_division ()); + void set_to_ideal_line_configuration (vsize start, vsize end); + vsize current_configuration_count () const; Line_division current_configuration (vsize configuration_index) const; Spacing_result space_systems_on_n_pages (vsize configuration_index, vsize n, vsize first_page_num); diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc index 282114d5c5..0e4f06dbcb 100644 --- a/lily/optimal-page-breaking.cc +++ b/lily/optimal-page-breaking.cc @@ -8,6 +8,7 @@ (c) 2006--2007 Joe Neeman */ +#include "international.hh" #include "optimal-page-breaking.hh" #include "output-def.hh" #include "page-spacing.hh" @@ -36,43 +37,114 @@ SCM Optimal_page_breaking::solve () { vsize end = breaks_.size () - 1; - vsize min_sys_count = min_system_count (0, end); + vsize min_sys_count = 0; + vsize ideal_sys_count = 0; vsize max_sys_count = max_system_count (0, end); - vsize max_page_count = INT_MAX; - vsize cur_page_count = 0; - Spacing_result best; + vsize page_count = 0; + Line_division ideal_line_division; Line_division best_division; - Line_division lower_bound; + Line_division bound; vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); - for (vsize sys_count = min_sys_count; - cur_page_count <= max_page_count && sys_count <= max_sys_count; - sys_count++) + /* find out the ideal number of pages */ + message (_ ("Finding the ideal number of pages...")); + set_to_ideal_line_configuration (0, end); + ideal_line_division = current_configuration (0); + + Spacing_result best = space_systems_on_best_pages (0, first_page_num); + page_count = best.systems_per_page_.size (); + best_division = ideal_line_division; + + for (vsize i = 0; i < page_count; i++) + ideal_sys_count += best.systems_per_page_[i]; + + min_sys_count = ideal_sys_count - best.systems_per_page_.back (); + if (page_count > 1) + min_sys_count -= best.systems_per_page_[page_count - 2]; + + message (_f ("Fitting music on %d (or one fewer) pages...", (int)page_count)); + /* try a smaller number of systems than the ideal number for line breaking */ + bound = ideal_line_division; + for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;) + { + Spacing_result best_for_this_sys_count; + set_current_breakpoints (0, end, sys_count, Line_division (), bound); + + for (vsize i = 0; i < current_configuration_count (); i++) + { + vsize min_p_count = min_page_count (i, first_page_num); + Spacing_result cur; + + if (min_p_count > page_count) + continue; + else if (min_p_count == page_count) + cur = space_systems_on_n_pages (i, page_count, first_page_num); + else + cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num); + + if (cur.demerits_ < best_for_this_sys_count.demerits_ || isinf (best_for_this_sys_count.demerits_)) + { + best_for_this_sys_count = cur; + bound = current_configuration (i); + } + } + + if (best_for_this_sys_count.demerits_ < best.demerits_ || isinf (best.demerits_)) + { + best = best_for_this_sys_count; + best_division = bound; + } + + if (best_for_this_sys_count.systems_per_page_.size () < page_count) + { + /* if the pages are stretched on average, stop trying to reduce sys_count */ + Real avg_f = 0; + for (vsize i = 0; i < best_for_this_sys_count.systems_per_page_.size (); i++) + avg_f += best_for_this_sys_count.systems_per_page_[i]; + if (avg_f > 0) + break; + } + + if (isinf (best_for_this_sys_count.demerits_)) + break; + } + + /* try a larger number of systems than the ideal line breaking number. This + is more or less C&P, but the loop bounds make it difficult to try something + like do {...} while (flip(&d) != UP). */ + bound = ideal_line_division; + for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++) { Real best_demerits_for_this_sys_count = infinity_f; - set_current_breakpoints (0, end, sys_count, lower_bound); + set_current_breakpoints (0, end, sys_count, bound); for (vsize i = 0; i < current_configuration_count (); i++) { - Spacing_result cur = space_systems_on_best_pages (i, first_page_num); - cur_page_count = cur.systems_per_page_.size (); + vsize min_p_count = min_page_count (i, first_page_num); + Spacing_result cur; + + if (min_p_count > page_count) + continue; + else + cur = space_systems_on_n_pages (i, page_count, first_page_num); + if (cur.demerits_ < best.demerits_ || isinf (best.demerits_)) { best = cur; best_division = current_configuration (i); } - if (cur.demerits_ < best_demerits_for_this_sys_count || isinf (best.demerits_)) + if (cur.demerits_ < best_demerits_for_this_sys_count || isinf (best_demerits_for_this_sys_count)) { best_demerits_for_this_sys_count = cur.demerits_; - lower_bound = current_configuration (i); + bound = current_configuration (i); } - - if (all_lines_stretched (i)) - max_page_count = min (max_page_count, cur_page_count + 1); } + if (isinf (best_demerits_for_this_sys_count)) + break; } + message ("Drawing systems..."); break_into_pieces (0, end, best_division); SCM lines = systems (); return make_pages (best.systems_per_page_, lines); diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc index 2cfb24bee7..662fb7d58c 100644 --- a/lily/page-breaking.cc +++ b/lily/page-breaking.cc @@ -433,6 +433,57 @@ Page_breaking::set_current_breakpoints (vsize start, lower_bound, upper_bound, &work_in_progress); + + /* we only consider a constant number of configurations. Otherwise, + this becomes slow when there are many small scores. The constant + 5 is somewhat arbitrary. */ + if (current_configurations_.size () > 5) + { + vector > dems_and_indices; + + for (vsize i = 0; i < current_configurations_.size (); i++) + { + cache_line_details (i); + Real dem = 0; + for (vsize j = 0; j < cached_line_details_.size (); j++) + dem += cached_line_details_[j].force_ * cached_line_details_[j].force_ + + cached_line_details_[j].break_penalty_; + + dems_and_indices.push_back (pair (dem, i)); + } + vector_sort (dems_and_indices, less > ()); + + vector best_5_configurations; + for (vsize i = 0; i < 5; i++) + best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]); + + clear_line_details_cache (); + current_configurations_ = best_5_configurations; + } +} + +void +Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end) +{ + current_chunks_ = chunk_list (start, end); + current_start_breakpoint_ = start; + current_end_breakpoint_ = end; + clear_line_details_cache (); + + Line_division div; + for (vsize i = 0; i+1 < current_chunks_.size (); i++) + { + vsize sys = next_system (current_chunks_[i]); + if (all_[sys].pscore_) + { + line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end); + div.push_back (line_breaking_[sys].best_solution (start, end).size ()); + } + else + div.push_back (1); + } + current_configurations_.clear (); + current_configurations_.push_back (div); } vsize @@ -615,8 +666,22 @@ Page_breaking::blank_page_penalty () const Spacing_result Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num) { - Spacing_result n_res = space_systems_on_n_pages (configuration, n, first_page_num); - Spacing_result m_res = space_systems_on_n_pages (configuration, n+1, first_page_num); + Spacing_result n_res; + Spacing_result m_res; + + if (n <= 2) + { + n_res = space_systems_on_n_pages (configuration, n, first_page_num); + m_res = space_systems_on_n_pages (configuration, n+1, first_page_num); + } + else + { + cache_line_details (configuration); + Page_spacer ps (cached_line_details_, first_page_num, this); + n_res = ps.solve (n); + m_res = ps.solve (n+1); + } + Real penalty = blank_page_penalty (); n_res.demerits_ += penalty; n_res.force_.back () += penalty; -- 2.39.2