Am 18.06.2018 um 10:57 schrieb Jan-Peter Voigt:
Hi Urs,
there are self balancing trees like AVL or Red-Black, but I'd say
implementation cost is quite for this purpose to sort n<1000 elements.
I might be wrong, but I'd prefer the sort method.
OK, this is why I ask.
(I assume with "implementation" cost you mean the additional time needed
for insertion/balancing, not the time *I* need for the implementation?)
The EE uses a tree that sorts by measure on the first level, by moment
on second and then by the edition-id-path. So there is a tree
structure, but on each level the child-list for each node is sorted by
the guile method sort, when it is displayed in order. To access the
elements it uses a hashtable.
In your case annotations should be at least partially sorted. The
question is, where/when do you need the sorted list?
When exporting annotations.
While typesetting music, you need to insert access the elements by a
path moment/context or the like.
Yes. When an acknowledged grob has an annotation attached it will be
prepended to the list or inserted into the tree.
To export a summary the order might be given by a path
piece/movement/measure/moment/context.
So do I get this right: you're suggestion that I *do* use a tree
structure, but not a BST but one where the hierarchy matches the musical
one?
This means that assuming my current movement has 1000 measures, and an
average of five annotations per measure I wouldn't have one list of 5000
annotations but one of 1000 (to sort) and 1000 of five each.
And when I have 1000 measures where only 37 include 1-2 annotations I'd
have that list of 37 measures with sublists of 1-2 each.?
To give a different view on the data I'd build another tree with the
desired scheme like type/mvmt/measure. If you have the primary tre in
insertion order you would have to visit some nodes more than twice so
a copy should be cheaper. (That is not a proof but an assumption!)
You mean: walk over the initial tree and insert each element into a new
tree with its own hierarchical structure matching the desired output
hierarchy?
Thanks
Urs
HTH
Jan-Peter
Am 18.06.2018 um 10:18 schrieb Urs Liska:
Hi all,
as you know I'm currently reviewing the scholarLY package, not only
for new features but also for its coding - which blatantly shows how
it was initially done directly from within my learning curve ;-)
One thing I'd like to change is the storage/handling of annotations.
The current implementation does the following:
* an engraver creates an annotation (an alist) and appends it to a
global "annotations" variable (OK, simple improvement: don't append
but cons to the beginning)
* in a later stage sort this "annotations" list and export the
annotations.
This looks very inefficient, and I think it should be much better to
store the annotations in a binary search tree and have them sorted
upon insertion already. (Or am I misunderstanding this? One thing I'm
unaware of is how efficient Guile's "stable-sort" works on a simple
(linked) list).
On https://gist.github.com/tushar-sharma/c476003598c03373e52c I found
a clean and simple implementation of a BST which looks like I can
very easily make if work in LilyPond (I can't test because I'm not at
my PC at the moment, but I'm talking about the general algorithms
anyway).
This should let me insert the annotations in sorted order (replacing
the <, >, and = with appropriate functions to sort annotations
according to the configured requests), and it's not hard to add a
function to walk the tree from left to right.
However - and now the question starts - if I'm not mistaken the
annotations encountered by the engraver will be somewhat (or
completely?) sorted by musical moment, which will be the requested
sort order most of the time but not always. And if elements that are
inserted in that BST are already sorted the tree will be totally
unbalanced, and the insertion time is as bad (or worse) as simply
appending to a list.
So if annotations would always be sorted by moment I would probably
go back to the simple linked list, but they may be sorted differently
and also by multiple keys (e.g. first by part, then by annotation
type and only then by moment).
I could make a switch and choose the storage data structure based on
the requested sorting (moment => list, everything else => BST), or I
could use a BST that realigns itself after each insertion.
I would be glad about any opinions/recommendations:
* Is it worth the effort looking into this (often there will be only a
couple of dozens of annotations per score, but three-digit numbers
shouldn't be unusual, and I have already encountered scores with
four-digit numbers of annotations)?
* Is my idea of a self-balancing BST the right direction?
* If so, which type of BST would be good to investigate (both in terms
of performance and implementation complexity)?
Thanks
Urs
_______________________________________________
lilypond-user mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/lilypond-user
_______________________________________________
lilypond-user mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/lilypond-user
_______________________________________________
lilypond-user mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/lilypond-user
