[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Gets vertical skylines from grob stencils (issue 5626052)

From: Joe Neeman
Subject: Re: Gets vertical skylines from grob stencils (issue 5626052)
Date: Sun, 19 Feb 2012 12:31:22 -0800

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]