🚀 go-pugleaf

In article <3629@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>Pretty well anything you might have done with Lisp-style arrays can be
>*expressed* the same way using library(arrays) or library(logarr); the
>remaining question is speed.  Trees (such as 3+4 trees) are surprisingly
>fast, and make multi-version structures easy to implement.

Unfortunately, not fast enough. I might be able to put up with the lg(N) part,
but my practical experience is that the constant factors in library(logarr)
and some other tree representations increase the running time of certain
graph algorithms between one and two orders of magnitude over similar
algorithms implemented with straight assignment. Algorithms such as
strongly connected components for directed graphs and DFA minimization
make essential use of assignment, and are impractical for large graphs/DFAs
(~10^5 nodes) if one uses trees in place of arrays. I wish I had better
news, but some kind of data structure with fast updates (which does not
necessarily push us outside logic, cf. the multiversion arrays of Eriksson
and Rayner) is needed for graph or automata algorithms with realistic data.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, Murray Hill, NJ 07974
pereira@research.att.com