Re: Sparse arrays
From: Gordon Sande (g.sande_at_worldnet.att.net)
Date: 12/04/03
- Next message: Blue Cat: "Re: Newbie question about double precision"
- Previous message: beliavsky_at_aol.com: "Re: Very basic Fortran compiler question"
- In reply to: TimC: "Sparse arrays"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 04 Dec 2003 10:09:35 -0400
In article <slrnbsuc4h.rro.tconnors@tellurium.ssi.swin.edu.au>,
TimC <tconnors@no.astro.spam.swin.accepted.edu.here.au> wrote:
>Subject: Sparse arrays
>From: TimC <tconnors@no.astro.spam.swin.accepted.edu.here.au>
>Organization: Some weird and wacky place in the superconfusing place, Swinny.
>Date: Thu, 04 Dec 2003 13:03:15 GMT
>Newsgroups: comp.lang.fortran
>
>I have a wish to store an array in RAM that if left to it's own
>devices, would take up about 10GB. Clearly, this is impossible on x86
>architecture :)
>
>I don't want to do anything at all complex to it - I just want to
>access array element (i,j), set it, sit for a bit, and read it back
>later. No disk IO, matrix multiplications or diagonalisations etc.
>
>It's going to be a darn sparse array, but it's still going to have a
>lot of elements, so I'll like both accessing and storage to be as
>efficient as possible. I don't want to imagine what cache misses will
>look like if it does some tricky hash thing - but they will all be set
>and accessed in sequential order (with the setting being incomplete
>due to the holes in the arrays).
>
>Naturally, google aint telling me much (well technically, it is
>telling me 16000 different ways to do something that doesn't seem to
>resemble what I want), even though it is telling me just where to get
>these lovely linear algebra packages. Do *you* know of any fortran
>libraries that might suit my seemingly simple requirements?
>
>
>--
>TimC -- http://astronomy.swin.edu.au/staff/tconnors/
>"Nature is pretty" -- CmdrTaco
IF, and these things depend critically on the assumptions, your
ONLY operations are STORE and RETRIEVE with no structure to the
sequence of access then the classical solution is a scatter store,
also known as a hash table. If you can tolerate a bit of inefficiency
(its OK, just don't tell anyone other than your drinking buddies)
then keep a sorted list, sorted on i then j, and do a binary
search into the list. It is pretty quick and very easy. No need
to figure out what to do if you guess the sizes wrong, no extra
programming for hash collisions, it is easy to debug, etc, etc.
This makes the additional assumption that you tend to have
more stores before the retrieves to keep the sorts/updates
within reason.
And unless you are doing an awfull lot of this your can probably
even tolerate a fair bit of inefficiency. A lot of inefficiency
might become noticable and above that you probably need to think
about decent algorithms. A bubble sort and a linear probe for
more than 1000(?) elements will get you into the lot of
inefficiency territory.
I have codes that read in some values of a multiple index array
and store them for later access. A bit of minor fiddling and then
out they go. They live in sorted lists. The minor fiddling includes
setting of the constraint matrices for serious OR which is done
with different data structures that support the computational
operations. These are custom matrix generators in the OR usage.
- Next message: Blue Cat: "Re: Newbie question about double precision"
- Previous message: beliavsky_at_aol.com: "Re: Very basic Fortran compiler question"
- In reply to: TimC: "Sparse arrays"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
