Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!att!dptg!ulysses!andante!alice!pereira
From: pereira@alice.UUCP (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Summary: the devil in constant factors
Keywords: arrays, trees
Message-ID: <11248@alice.UUCP>
Date: 28 Aug 90 14:20:31 GMT
References: <90239.175243SCHMIED@DB0TUI11.BITNET> <9653@bunny.GTE.COM> <3629@goanna.cs.rmit.oz.au>
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs
Lines: 25

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