On Jul 5, 2011, at 12:30 PM, David Kastrup wrote: > "m...@apollinemike.com" <m...@apollinemike.com> writes: > >> On Jul 5, 2011, at 9:58 AM, m...@apollinemike.com wrote: >> >> >> >> >> 3) Make the lines_ of a constrained breaker a sparse binary tree >> (see below) of matrices, not a single matrix, that stores the >> information above. Each node of the tree would branch off into >> break/noBreak for a single point in breaks. >> >> >> >> Errata - the binary tree nodes would hold either null (no break) or >> vectors (break), where each vector represented the forces of the >> previous lines. Or maybe not even this...essentially, it'd be a data >> structure that holds the forces associated with a lot of different >> line breaking configurations in a way that eliminates redundant >> storage.* >> >> Cheers, >> MS >> >> * I know nothing about best practices in data management, but I'd be >> willing to learn if there isn't anyone who is good at this and would >> be willing to take on this project with me :) > > Well, the task sounds like the typical shortest path graph traversal. > Basically, you keep a list of all feasible breakpoint sequences up to > the currently examined breakpoint, including a set of characteristics > that can still interact with the following breakpoints/lines, like the > bottom skyline, and a (possibly discontinuous, like when skylines may > interlock, but partly continuous) set of vertical dimensions and > associated scores that the material above can assume. > > If one partial possibility can't be part of a solution scoring better > than a solution using a different scored partial possibility, the > inferior candidate is pruned from consideration. > > -- > David Kastrup >
I did a series of upper-bound calculations to see how many extra runs of the spacing spanner would be necessary for volatile sections (sections whose horizontal spacing is dependent on the horizontal spacing of other lines). A fully-volatile piece would be one where every line's spacing was interdependent. The bad news is, in a 300 measure piece with volatile sections between measure 140 and measure 149 and then again between measure 154 and 158, one would need to run the simple spacer's solve method a maximum of 517,292,878 times instead of the 45,150 times one would run it for a normal 300 measure piece. If the piece is particularly volatile to the tune of volatility in mm. 4-9,10-19,20-49,80-91,107-150,211-213,291-298, then one would need to run the simple spacer's solve method a maximum of 1,930,043,738,999,861,217,481,055,941,620,129,849 times. Of course, these are upper bounds. The if (!spacer.fits ()) on line 451 prunes this down a good deal, and it could even be pruned down more if there were some sorta spacer.too_bloated () function that established a bound on the other end. To this end, I tweaked the Python script and set an artificial high limit of 20 measures max per line. For a 300 measure piece with volatile sections from 140-145 and 215-220, the simple spacer would need to run 16750 times compared to its normal 5810 (these numbers may be off by a couple hundred in either direction - I got lazy as I started to understand orders of magnitude). This is reasonable, but up the measures to 140-150 and 215-225 and you'll need 314,790. For a 300 measure piece with nothing but volatile passages, using this upper bound of 20 measures per line, one would need 5,505,024 runs of the spacing spanner, which would take just over two years to compile. That said, if the maximum line length is 5 measures, one needs a meager 31,270 runs of the spacing spanner for a 300 measure fully-volatile piece. Cheers, MS _______________________________________________ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
