Well . . . Maybe there should be one more guideline: at the end of the input
process, the data should be in an array, in input order.
=
If the data is to be accessed by pointers, you could just make a linked list and
insert each new item at the root (ahead of the existing linked list items).
=
Not too easy to sort, however, unless you create some auxiliary lists. My
"advanced Fortran" text (soon to be downloadable for $10 from Walt Brainerd's
Fortran Market) shows how to build a "skip list" that is ordered during input.
The space overhead is only 2 pointers per datum, plus a "directory" of size
log2(N) that gets reallocated, copied, and deallocated whenever the amount of
data doubles.
=
Loren P. Meissner
[log in to unmask]

> -----Original Message-----
> From: [log in to unmask]
> [mailto:[log in to unmask]]On Behalf Of Friedrich R.
> Hertweck
> Sent: Sunday, November 08, 1998 12:09 AM
> To: Loren P. Meissner
> Cc: A Fortran 90 Mailing List; Bart Childs
> Subject: Re: A little advice, please
>
>
> On Sat, 17 Oct 1998, Loren P. Meissner wrote:
>
> > I have just been communicating with a person about the problem of
> > reading a "huge" file of data when you can't predict in advance how big
> > it will be. For purposes of illustration, suppose that the idea is to do
> > an internal sort (say, Quicksort) after the data has been read in. I am
> > trying to compare two options:
> >
>     . . .
>
> ! Here is a different solution to the "huge file problem"
> ! It has been constructed using the following guidelines:
> !
> ! (0) The solution should be "pure Fortran 90", i.e. run on
> !     an "abstract Fortran 90 machine", without reference to
> !     any operating system peculiarities
> !
> ! (1) We assume that the (virtual) size of the computer memory
> !     available to the user is large enough to hold the file
> !
> ! (2) The file should only be read once (reading it twice just to
> !     find out its length is considered a waste of resources)
> !
> ! (3) Unused memory overhead should be reasonably small (therefore
> !     first to allocate N units of memory, then 2*N units and to
> !     copy the data to the new memory is not really feasible
> !     because it uses up to 3 times the really needed memory and
> !     also the copy operation is wasteful.
> !
> ! (4) Dynamic memory extension is handled via a pointer listi p(:),
> !     each list element responsible for mm2 records, where mm2>>1
> !
> ! (5) The way the list is extended, only one copy needs to be done
> !
> ! (6) For accessing the records, a function "record" is supplied
> !     which returns the value of the required record
> !
> ! (7) If the file is to be sorted (to assume just some usage for it),
> !     one could generate a list of integers xlist = (/ 0, 1, ... n-1 /)
> !     and do sorting by a generic sort algorithm which might be fed
> !     the comparison function "greater(i,j)" (this is all it has to know
> !     about the nature of the objects to be sorted).
> !
> ! (8) It is assumed that the records are all of the same size. If
> not, the file
> !     should be read with ADVANCE="no" and stored differently. Things would
> !     get more complicated, but still could be done.
> !
> ! Below is a sample program which has been run on:
> !     IBM RS/6000, Cray T3E, NEC SX-4, SUN (NAG compiler).
> !
> !
> ! Regards,
> ! Friedrich Hertweck




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%