Re: Adds dimension stencil command to correct with-dimension (issue 12957047)

[dak]

On 2013/08/27 06:58:05, mike7 wrote:
> On 27 août 2013, at 09:01, "Keith OHara" <mailto:address@hidden>
wrote:

> > How are skylines asked-for, and is it possible to know if they were
asked for
> while interpreting the markup ?
> > {c4-\markup \whiteout \pad-to-box #(-0.5 . 9) #(-0.5 . 1.5) \concat
{"Clarinet
> in B" \flat}}
> >

> class Stencil {
>    private :
>      Scheme expr_;
>      Box dim_;
>      Skyline_pair *vskys_; // set to 0 in the constructor
>      Skyline_pair *hskys_; // set to 0 in the constructor

>    public :
>      Skyline_pair* get_vskys () { if (!vskys_) create_vskys (); return
vskys_; }
> }

> So, the idea is that we only ever create the skylines if they are
asked for or
> if we use something like pad-to-box.  Then, if we are going to combine
two
> stencils and neither of them have skylines set already, we do not
calculate
> their skylines yet.

Either you don't listen or you don't think about your code.  Delaying
skyline calculation until it is needed does _nothing_ whatsoever with
regard to computational complexity if the skyline is needed eventually,
which it will almost always be.

What's much worse is that the performance drops drastically if the
evaluation is not done in bulk but structured along the lines of the
underlying expression.

Since the calculation of a total skyline rather than predetermined
sub-skylines is free to make more efficient choices for its subdivision
of the data, one wants to avoid calculating _any_ intermediate skylines.

Assigning individual skylines to the respective parts of a composite
stencil expression forces a particular evaluation order.  This leads to
the typical O(n^2) behavior for accumulating a skyline bit by bit rather
than by a size-driven divide-and-conquer approach taking O(n lg n).

https://codereview.appspot.com/12957047/