stst@cs.albany.edu (Stefan Strack) (06/22/91)
This post is a bit lengthy, and concerns mostly PDC Prolog, so hit 'n' if
you're not interested .. also, I am not a research person, so no flames from
you Prolog-Gurus please ;-)
Prolog is great for recursive data-structures, such as lists, trees, etc..
Sometimes, though, I find myself needing a simple one-dimensional array.
What I mostly resort to is to implement an array as a collection of indexed
facts, such as:
array(0,Contents1).
array(1,Contents2).
...
Array-updates are implemented as assert/retract operation. The nice thing
about this implementation is that accesses by index and by contents are
possible. The bad news is that access speed is inversely related to the
"size" of the array. So, what I am looking for is a better implementation of
an array in Prolog. This implementation should:
- be reasonably memory efficient
- allow fast look-up by index (fast look-up by contents would
also be good, but isn't critical for my application)
- provide array-size independent access times (or at least with a
reasonable upper bound)
By now, it should be clear that I'm not talking about pure Prolog.
Specifically, I am looking for something that works with PDC Prolog (that's
the only Prolog I have access to). The best solution that I came up with so
far involves using "external databases" in PDC Prolog. In short, the array
contents would be stored in an external database, in no particular order. A
B+ tree would be used to maintain the indicices in ascending order. Nodes in
the B+ tree consist of a string-key (sorted) and a pointer into the external
database, such as:
B+ tree External database
Key Pointer
"0000" A ---------------> Contents1
"0001" B ---------------> Contents2
"0002" C ---------------> Contents3
... ...
In this implementation, an empty array starts out as an empty B+ tree and an
empty external database. As the array gets filled with elements, the external
database is simply appended to, and the new index is inserted into the B+
tree, converting the numerical index into its string equivalent to form the
key. Similarly, look-up of array[N] involves constructing the key-string "N",
and fetching the pointer to the external database element from the B+ tree.
Although I haven't tried this yet, it looks to me that this would be faster
than the array-as-collection-of-indexed-facts method in the beginning,
at least for the kind of large arrays I am interested in. It however requires
additional memory for the B+ tree.
Can you think of a more efficient solution? Maybe I am overlooking something
elegantly trivial here? Again, the keyword is "(largely) array-size
independent access-time". Although I am mostly interested in PDC Prolog, I
would also like to hear how you would do it in _your_ favorite Prolog. And
yes, I expect a few to say "if you want to use arrays, go program in C or
Pascal", but that's not what I am interested in. Also "interface your Prolog
program to a C routine that maintains the array" is also not acceptable,
because my array should hold compound objects.
In case you are asking what kind of program I am writing: it's an
implementation of A.K.Dewdney's "Core War" game, and I am looking for a good
representation of the Core memory array.
Please post or reply by email, I'll post a summary if there's interest (??).
Thanks, Stefan (stst@cs.albany.edu)ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/24/91)
In article <858@watson.albany.edu>, stst@cs.albany.edu (Stefan Strack) writes: > Prolog is great for recursive data-structures, such as lists, trees, etc.. > Sometimes, though, I find myself needing a simple one-dimensional array. > What I mostly resort to is to implement an array as a collection of indexed > facts, such as: > > array(0,Contents1). > array(1,Contents2). > ... > > Array-updates are implemented as assert/retract operation. The nice thing > about this implementation is that accesses by index and by contents are > possible. The bad news is that access speed is inversely related to the > "size" of the array. Let me tell you the *really* bad news. In other Prologs the access time is *not* related to the size of the array. In every commercial Prolog I have ever had my hands on (with the exception of one, running on PCs and Macs), a dynamic predicate is accessed via a hash table. If you cannot assert, retract, and access such facts in essentially constant time, complain to your vendor. In the case of Turbo/PDC, demand that they give you something as efficient as Prolog. > So, what I am looking for is a better implementation of an array in Prolog. There's a paper of mine from the Department of Artificial Intelligence at the University of Edinburgh which shows how array element access and update can be done in constant _amortized_ time using ordinary Prolog terms. I'm not sure if it's doable in Turbo/PDC Prolog, I never did quite grasp how to use 'reference's in that language. Don't bother asking me for a copy of that paper, I haven't any. > [Idea of using an external data base.] > A B+ tree would be used to maintain the indices in ascending order. > ... the keyword is "(largely) array-size independent access-time". But a B+ tree provides you only LOGARITHMIC access and update time. Why not use an internal tree? It will still be logarithmic, but the constant factor will be a heck of a lot lower. You might try using the N+K trees described in "The Craft of Prolog", tuning N and K for your application. > In case you are asking what kind of program I am writing: it's an > implementation of A.K.Dewdney's "Core War" game, and I am looking for a good > representation of the Core memory array. I would not have thought Turbo/PDC Prolog was the language of choice for that application. If you want a logic programming language which *would* make sense for that application, try Trilogy. -- I agree with Jim Giles about many of the deficiencies of present UNIX.