[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Binary Search Tree in Scheme
From: |
Jan-Peter Voigt |
Subject: |
Re: Binary Search Tree in Scheme |
Date: |
Mon, 18 Jun 2018 11:41:45 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 |
Am 18.06.2018 um 11:16 schrieb Urs Liska:
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?)
Yes I mean insertion cost, but I also mean weight of the code. You have
a complex structure to maintain.
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.
So this is a one time sorting task. Or twice, if you have two views.
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.
The list will be sorted for one view. I assume `reverse` a quite cheap
function.
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.?
Yes. The tree-structure is for creating different views and for
directory lookup. If all annotations are fetched by an engraver it might
be OK to first collect them in one large list. And if you drop them into
a tree with the scheme of the desired view you don't need to sort the
list, but just the tree. If you already know the scheme of the view
while fetching the annotation events you can of course insert the
annotations immediatly in the tree. That insertion might be hidden
behind a method of an insert-collect-object. That way you can
interchange the implementation without touching the engraver ... and
perhaps I didn't study the ScholarLY code and that is already the case ;-)
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?
Yes