On Sun, Feb 19, 2012 at 11:59 AM, David Kastrup
<address@hidden> wrote:
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).