On Sun, Feb 19, 2012 at 11:59 AM, David Kastrup <d...@gnu.org> wrote:
> "m...@apollinemike.com" <m...@apollinemike.com> writes: > > > I've now optimized the crap out of this sucker and cached as much as I > > can cache. > > I'm not sure the caching is of much help. What kind of information > would save recalculation? > > > For example, I get the sense that the new key signature skyline > > function is not much faster than the old, which means that either the > > lookups of cached accidental skylines or the merging of these skylines > > to create the signature takes a lot of time. > > "Merging" sounds like O(n^2) unless one takes precautions. > No, it's O(n + m). (m is the length of the other skyline). Building a skyline from scratch is O(n log n). However, there may be room for more heuristics that speed things up (see non_overlapping_skyline, which resulted in a measurable speedup).
_______________________________________________ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
