Large Look-up Table question ?

Large Look-up Table question ?

[Nick Wilson]

I'm implementing a large matrix of values which is basically just a big
lookup table. What would be the best way to implement this in only ada83
code ? My initial idea is to use a static table for all the values but
this seems clunky, can anyone offer some advice ?

Thanks,

Re: Large Look-up Table question ?

[Steve Quinlan]

If the matrix is sparse, arrays may be "clunky", but are also the simplest
implementation. If the  matrix is not too big to be practically implemented
by an array, and if you can live with wasted storage (and possibly poor
performance) go with it. At least evaluate the tradeoffs.

If the matrix is not sparse, then an array is just as space efficient and
probably more time efficient than any of the normal ways of dealing with
sparse matrices.

Re: Large Look-up Table question ?

[czgrr]

In article <375299F4.CDEA8A81@hotmail.com>,
  Nick Wilson <snow_moose@hotmail.com> wrote:
> I'm implementing a large matrix of values which is basically just a
big
> lookup table. What would be the best way to implement this in only
ada83
> code ? My initial idea is to use a static table for all the values but
> this seems clunky, can anyone offer some advice ?
>
> Thanks,
>
Hi Nick.

Some ways of implementing a large table include:

1. A large (set of) constant(s). Fast to run, a pain to code, watch
those brackets!, good if you have a fixed size of matrix. Big
executable size if the data is stored that way. Might be clunky but
nothing wrong with it.

2. A linked list. Slower to run, easy to code, and few changes if the
matrix size needs to be different. Slower initialisation, but this may
not matter. A set of functions to access the data.

3a. A file. Use a linked list as in 2), but the data can be stored and
edited on disk in the most convenient format (especially useful if it
is automatically generated from something else). Initialisation
consists of loading the data from file, and again a set of functions
access the data.

3b. A file, again. Accessing the data reads the file each time, with no
list or any other structure being used to hold the data (except perhaps
some caching to speed things up). Or use Direct IO to get the speed.
This is only really necessary if the matrix is so huge that you get
memory problems.


There are other possibilities, depending on what the matrix actually
holds.

4. If it is a sparse matrix, a function is a possibility which
calculates the value each time, or some sort of sub-lookup using one of
the methods above. Hash functions spring to mind.

5. If there are patterns in the data, functions may again help. Indeed,
it might be possible to completely dispense with the matrix and code it
using formulae, but this is only really possible in very specialised
cases and you probably wouldn't be thinking of using a lookup matrix
anyway.


I'm sure you'll read about other methods, this list is not means to be
exhaustive. I tend to use 3a) for larger datasets.

HTH
czgrr

--
No email, please - reply to the newsgroup. Email may be made public.
My opinions are not necessarily those of my employer.
My suggestions might not be correct. Use at your own risk.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Large Look-up Table question ?

[Nick Roberts]

I think the main question here is: how much memory does/will the target
machine have?  If it will have enough memory, then use an array (as the
simplest and fastest implementation); otherwise, you will have to use
something else (maybe a hashed array), or get more memory.  Note that I use
the word 'memory' here, not RAM, since in virtual memory systems, I am
talking about virtual memory (not the same as RAM).

A huge array, particularly a linear (one-dimensional) one, can work on a
virtual memory machine very efficiently when implemented in the language as
a simple array: the virtual memory management system effectively converts
the array into a sparse array invisibly.  However, this strategy can sink
like the Titanic if the granularity of array usage (i.e. the typical gap
between used components) is similar to the granularity (i.e. the page size)
of the virtual memory system.

Sometimes a good hashing scheme can be very effective in delivering fast
access, but making very good use of memory.  Sometimes there's nothing for
it but a balanced binary tree, or even an indexed file or database table
(especially if the data is updated in place and precious).

Occasionally, a re-think about the structure of your data can mean you can
drastically reduce the size of the array.  Think, in particular, about the
use of redirection indexes or pointers.  If it is practical to impose some
serious limits on numbers of things, it may well be possible to use an index
array to map a big index type to a much smaller one.  Then your 'big' array
can become much, much smaller.

Quite often, you simply need to be devious about these things!  For example,
it may be perfectly acceptable to ask the user "please give a number between
1 and 100 to identify this book (the LLIN)", and then use the 'LLIN' to
index books (in a lending library), instead of say, the humungous ISBN.

There's never, ever, anything inherently 'clunky' about using a big array,
no matter how big.  It is only ever clunky to use an array that's bigger
than it could ever actually need to be (a common mistake), or to use an
array of any size when some other structure is called for.

-------------------------------------
Nick Roberts
http://www.adapower.com/lab/adaos
-------------------------------------

Nick Wilson wrote in message <375299F4.CDEA8A81@hotmail.com>...
|I'm implementing a large matrix of values which is basically just a big
|lookup table. What would be the best way to implement this in only ada83
|code ? My initial idea is to use a static table for all the values but
|this seems clunky, can anyone offer some advice ?
|
|Thanks,
|
|

Re: Large Look-up Table question ?

[Ehud Lamm]

On Wed, 2 Jun 1999, Nick Roberts wrote:

> A huge array, particularly a linear (one-dimensional) one, can work on a
> virtual memory machine very efficiently when implemented in the language as
> a simple array: the virtual memory management system effectively converts
> the array into a sparse array invisibly. 


I suggest trying things out!

Searching a large (~10^6 elements) array of floating point numbers, on a
PC using GNAT seems fast enough (to make life interesting I looked for
the sqrt).

This is part something I am playing with, so there is a good chance more
on this will come later in more detail.

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il

Re: Large Look-up Table question ?

[dennison]

In article <375299F4.CDEA8A81@hotmail.com>,
  Nick Wilson <snow_moose@hotmail.com> wrote:
> I'm implementing a large matrix of values which is basically just a
big
> lookup table. What would be the best way to implement this in only
ada83
> code ? My initial idea is to use a static table for all the values but
> this seems clunky, can anyone offer some advice ?

Well, if it's just a one-dimensional lookup, you can dynamicly allocate
an array of the correct size once you know what that size is. Is that
what you were looking for, or did you want something "sexier"?

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Large Look-up Table question ?

[Nick Wilson]

Thanks for all the replies people, I'm probably going to go with the idea of
reading all the data from the file as it's highly likely that the actual
entries of the matrix will change and so the easiest way to be able to set
them all is by having an external file rather than hardcoding them. It means
a longer initialisation time to read them into an array and if it's too slow
then I might have to go with a linked list of them. :)

Re: Large Look-up Table question ?

[dennison]

In article <375BB1C6.4E4B79A9@hotmail.com>,
  Nick Wilson <snow_moose@hotmail.com> wrote:
> reading all the data from the file as it's highly likely that the
actual
> entries of the matrix will change and so the easiest way to be able to
set
> them all is by having an external file rather than hardcoding them. It
means
> a longer initialisation time to read them into an array and if it's
too slow
> then I might have to go with a linked list of them. :)

We also have a problem here with initilization time reading several
large tables. The approach we *plan* on taking (supposedly it worked on
past projects) is to, in an offline mode, read in and parse the files
from their human readable format. Then we will dump the table's data to
another disk file (possibly using TableTypeName'Output). When we are
running online, we will just read the data files straight into the data
structure. That way we don't waste online time parsing human-readable
files.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Large Look-up Table question ?

[Mike Brenner]

If "static" means that these values are never changing, and if they are
character strings, the fastest way to look them up is probably to convert
them into a finite state machine and run the machine, if enough random
access memory is available for the machine. This was discussed last year in
the thread about GOTOs versus table implementation of finite state machines.




Nick Wilson wrote:

> I'm implementing a large matrix of values which is basically just a big
> lookup table. What would be the best way to implement this in only ada83
> code ? My initial idea is to use a static table for all the values but
> this seems clunky, can anyone offer some advice ?
>
> Thanks,