stst@cs.albany.edu (Stefan Strack) (06/26/91)
Here is the summary of the email responses I got in response to my question concerning "Array implementation in (PDC) Prolog". First of all, thanks very for your knowledgable help. I think I go play with trees for a little while .. :-) (1) John Garland (jgarland@kean.ucs.mun.ca) and Avery Andrews (ada612@csc.anu.edu.au) refer to the "Professional User Guide" from PDC, where an interface to "C" is described. A C-routine is linked into the Prolog program to provide pointer-based access into a dynamically-allocated array. Even if you don't own the PUG, you can get some example code by downloading ARRAY.ZIP from the PDC BBS (404-872-5358). This looks a little "dirty" to me, but I might look into this (unless I find a "pure" solution). (2) Tim Arnold (tja@cs.mu.oz.AU) and Richard O'Keefe (can't seem to find the email address) point out that an array-implementation as indexed database-facts should provide constant-time access in most Prologs. Unfortunately, PDC Prolog does not hash dynamic code on the first argument, and that seems to be my problem .. (3) ted.NMSU.edu mailed me an (almost) working piece of code for 3+4 trees (thanx), which I tweaked a little to work with PDC. This compares very favorably with the array-as-facts representation in terms of access/update speed. However, asserting/retracting the tree-predicate is an *enormous* overhead; this gets worse as more and more new nodes are added to the tree. Does anyone care to speculate on why? Carrying the 3+4 tree around as an argument (instead of asserting/retracting it for each access) speeds things up by orders of magnitude, but I am running out of heap space with >1500 integer array elements. No memory problems when I assert/retract the tree. I am at a loss, not knowing how PDC Prolog handles memory. Any ideas? - Stefan (stst@cs.albany.edu)