Re: Binary Search Tree in Scheme

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

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