Joe Neeman escreveu:
On 11/14/06, *Han-Wen Nienhuys* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
Joe Neeman escreveu:
>
> If there are any references about skylines around, I'd be
interested in
> seeing them; I just made things up as I went. Your suggestion (which
There is one thing: you base the structure on lists, which makes for
easy merging, but is relatively expensive if you do lots of point
queries (ie. how high is the skyline at point X). I'm not sure if it is
an issue, and things are definitely better than the previous
version, of
course. It should be possible to use a (binary) tree, with the X
position of each event as a sort-key.
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.
--
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
