Urs Liska <[email protected]> writes: > 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)
That improvement is definitely something you should do. Reduces complexity from O(n^2) to O(n). > * in a later stage sort this "annotations" list and export the > annotations. > > This looks very inefficient, Why? Batch sorting once is in general more efficient than keeping data sorted during input. It's O(n log n). Which means that the time spent here will become insignificant compared to the time your "appends it to a global annotations variable" takes once you are talking about larger amounts of data. You know the joke about the drunk crawling on the ground under a street lamp looking for his keys? Someone helps him but no success, so he finally asks "are you sure that you lost your keys here?" "No, down there." "Why are we looking here?" "Well, there is better light here and it's not as dirty." Except that you are looking for your performance where it's dark and dirty when you likely lost it under the street lamp. > 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). Guile's stable sort is a merge sort. There is nothing better on linked lists. There is actually almost nothing in terms of total comparison operations regardless of data structure. If your access pattern needs the sorted data only once, it will be totally useless to try anything else. It's pretty much guaranteed to end up more expensive in execution time, let alone in programming and maintenance effort. Even for the task of intermittently requesting (and removing) the smallest element so far (a special case of access pattern mixing writes and reads), there are special data structures called "priority queues" that are cheaper than trees with guaranteed O(n log n) worst case behavior without balancing complications because they don't need to maintain complete order. Typically implemented using "heaps". -- David Kastrup _______________________________________________ lilypond-user mailing list [email protected] https://lists.gnu.org/mailman/listinfo/lilypond-user
