Re: Binary Search Tree in Scheme

[Urs Liska]

Hi David,


Am 18.06.2018 um 12:25 schrieb David Kastrup:
> Urs Liska <address@hidden> 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).

Yes, I know that by now, and I was surprised to be confronted with my 
old code ;-)

> >   * 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.

OK.

> 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."

Yes, I knew that one.

> Except that you are looking for your performance where it's dark and
> dirty when you likely lost it under the street lamp.

Very good description !

> > 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.

OK, I'll take that as sound advice.

> 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".

Oh my, it's less than a year that I learned and successfully completed 
programming assignments on all of these - and already it's so far away ...
Of course I was aware that I'd actually need some regular practice to 
keep these things fresh and get to a more thorough understanding that 
helps me keep them in mind for longer. Probably it would have been good 
if I had made good on my intention to reimplement my Python solutions in 
Scheme. Would probably also have produced some tools ready for use ...

Best
Urs