kskalb@faui1f.informatik.uni-erlangen.de (Klaus Kalb) (11/23/90)
Hello everybody !
I want to know how the HP48 implements the data type LIST.
Are they just plain, ordinary linked lists or is there something
more spohisticated going on ?
To my opinion, this is a importent issue to any programmer that wants
to use large lists for storing things.
Knowing details about the implemtation will answer questions like:
-- How do I append a item as fast as possible if I don't mind the order ?
If plain vanilla linked lists are used, appending to the front
is constant in time ( O(1) ), but appending to the tail is
linear ( O(n), to be exact ).
-- I have noticed that LIST\-> and \->LIST are quite fast, even
with lists of length >1000. Maybe the stack is just a list ?
-- How do you insert and delete arbitrary items ?
It seems that doing LIST\->, manipulating the stack and then
\->LIST ist quite fast, but is this true ?
By the way, thanks to the net for all those great programs and infos.
-KK
------------------------------------------------------------------------------
Klaus Kalb | mail : IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany
| email: kskalb@immd1.informatik.uni-erlangen.de
------------------------------------------------------------------------------bson@rice-chex.ai.mit.edu (Jan Brittenson) (11/24/90)
In article <kskalb.659353921@faui1f> kskalb@faui1f.informatik.uni-erlangen.de (Klaus Kalb) writes: > I want to know how the HP48 implements the data type LIST. Are they > just plain, ordinary linked lists or is there something more > spohisticated going on ? No, they're not cons cell lists, or linked in any way. Lists are simply a List data type (#2a74) followed by the contents and terminated with an End (#31b2). Like in a program, data may be of any type, either in-line or somewhere else. (I.e. there may be either data or pointers to data, or both randomly intermixed.) They can be regarded (sort of) as CDR-coded lists, or hunks, or functionally (not implementationally) like (make-array ... :element-type t) Common Lisp arrays. RPL arrays differ by being restricted to a single type - real or complex (has anyone attempted to synthesize an array of some other type, like Character?), which allows for faster element address calculations.
grue@batserver.cs.uq.oz.au (Frobozz) (11/24/90)
In <12017@life.ai.mit.edu> bson@rice-chex.ai.mit.edu (Jan Brittenson) writes: > RPL arrays differ by being restricted to a single type - real or >complex (has anyone attempted to synthesize an array of some other >type, like Character?), which allows for faster element address >calculations. I haven't tried this. I did try to change the number of dimensions in an array (on my old '28S) and it caused an interesting pattern on the display when I tried to display the thing. I never tried to do anything else with it (because the display was suffering really badly). I may have had to do a system reset (the ON-C equiv, I cannot even remember what key it was ummm up arrow?? :-). I don't think I suffered a memory lost playing around like this. Pauli seeya Paul Dale | Internet/CSnet: grue@batserver.cs.uq.oz.au Dept of Computer Science| Bitnet: grue%batserver.cs.uq.oz.au@uunet.uu.net Uni of Qld | JANET: grue%batserver.cs.uq.oz.au@uk.ac.ukc Australia, 4072 | EAN: grue@batserver.cs.uq.oz | UUCP: uunet!munnari!batserver.cs.uq.oz!grue f4e6g4Qh4++ | JUNET: grue@batserver.cs.uq.oz.au --
akcs.dnickel@hpcvbbs.UUCP (Derek Scott Nickel) (11/25/90)
I've played around with Arrays of odd types (even Ayyays of Code). The
message tables in HYDE are just Array of String. But the user-level
commands only recognize 1 and 2 dimensional arrays of Real Number or
Complex Number.
In case any body cares...
Array (029EB)
<prolog><size><item-prolog><#dims><dim-1>...<dim-n><item-1>...
<item-m>
<prolog> = 029EB (BIN5)
<size> = size of object in nibbles without the prolog (BIN5)
<item-prolog> = prolog of array elements (BIN5)
<#dims> = number of array dimensions (BIN5)
<dim-i> = i-th dimension (BIN5)
<item-j> = j-th item sans prolog (ANY)
n = <#dims>
m = <dim-1> * <dim-2> * ... * <dim-n>
Derek S. Nickel