Han-Wen Nienhuys escreveu: >> I'm not (yet) convinced that it's worth the effort. It seems that >> querying at a point is the only thing that gets improved speed. >> Merging and distance are still O(sum of length of skylines) because we >> need to at least look at every point in every skyline. Building a >> skyline is still O(n log n). > > I think you can do better on merging and distance, if you also store > min/max heights in nodes; with that you could skip looking at an entire > branch of points. However, you're right in that it is premature to > optimize this.
Hi, I have added scripts for profiling, see buildscripts/build-profile.sh. It turns out that the skyline related routines have replaced Grob::get_property() as the top-contender in the profile. Can you have a look to see if this can be optimized? Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ms/call ms/call name 16.39 6.36 6.36 10977483 0.00 0.00 Building::conceals_beginning(Building const&) const 16.37 12.72 6.36 666756 0.01 0.01 common_refpoint_of_array(std::vector<Grob*, std::allocator<Grob*> > const&, Grob*, Axis) 6.21 15.13 2.41 1757179 0.00 0.01 Skyline::internal_merge_skyline(std::list<Building, std::allocator<Building> >*, std::list<Building, std::allocator<Building> >*, std::list<Building, std::allocator<Building> >*) 5.69 17.34 2.21 18440608 0.00 0.00 skyline_trailing_part(std::list<Building, std::allocator<Building> >*, double) 5.62 19.52 2.18 15397616 0.00 0.00 Building::conceals(Building const&) const 4.05 21.09 1.57 6362790 0.00 0.00 Building::precompute() 3.79 22.56 1.47 1694853 0.00 0.00 Page_spacer::calc_subproblem(unsigned int, unsigned int) 1.21 23.03 0.47 27360933 0.00 0.00 Interval_t<double>::length() const 1.20 23.49 0.47 5219812 0.00 0.00 Grob::extent(Grob*, Axis) const 1.13 23.93 0.44 26448697 0.00 0.00 Grob::internal_get_property_data(scm_unused_struct*) const 0.84 24.26 0.33 20164826 0.00 0.00 Grob::get_offset(Axis) const -- Han-Wen Nienhuys - [EMAIL PROTECTED] - http://www.xs4all.nl/~hanwen LilyPond Software Design -- Code for Music Notation http://www.lilypond-design.com _______________________________________________ lilypond-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/lilypond-devel
