Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!bionet!csd4.milw.wisc.edu!schaefer!larry!jwp
From: jwp@larry.sal.wisc.edu (Jeffrey W Percival)
Newsgroups: comp.unix.wizards
Subject: Algorithm needed: reading/writing a large file
Message-ID: <205@larry.sal.wisc.edu>
Date: 6 Jul 89 18:16:29 GMT
Organization: Space Astronomy Lab, Madison WI
Lines: 19

I am writing a C program (Ultrix, VAXstation 2000) to re-arrange a
large disk file.  The file contains a large number of fixed length
records.  My current method is this: read through the file, building 2
arrays in memory:  array1 is an array of some attribute I want to sort
on, and array2 is just array of ascending integers (record numbers in
the first file).  Then I sort array1, with array2 tracking the
movements in array1.  I end up with array2 being a mapping of record
numbers between the input file and the sorted file.  Finally, I loop
through array2 doing a read on file1, record array2[i] and writing to
file2, record i.

Now, I'm not looking for help in the sorting of array1;  my sorting
algorithm is fast and efficient.  What is taking a long time are the
quasi-random seeks in file1 as file2 is sequentially built.

I cannot have all of file1 in memory, but can have more than the one
record I am currently using in this shuffle.  How can I speed this up?
-- 
Jeff Percival (jwp@larry.sal.wisc.edu)