From: Lionel Bouton <lionel-subscription@...>
Date: 2008-04-30T01:15:03+09:00
Subject: Re: Transpose a large file(>2GB)

Ken Bloom wrote:
> On Sun, 27 Apr 2008 05:32:52 -0500, Ams Lo wrote:
> 
>> Hi -
>>
>> What is the fast and ruby way to transpose a large file(>2GB)??
>>
>> I can't read the whole file into memory due to the file sizes..
> 
> I assume all of the lines in the file are the same length, and the line
> length is a multiple of the disk block size.

 From the rest of the algorithm, you assume that the OP wants to 
transpose in place, and indeed your algorithm is probably one of the 
best in this case (and is more or less Pascal Bourguignon's algorithm 
tuned for disk access). I'm not sure this is what the OP wants (wasn't 
specified). He seemed memory constrained but didn't report any disk 
space constraint, so he may benefit from an algorithm writing another file.

In short I wonder if it's the best in the general case.

For a data point a 20000 * 20000 64 bit integer matrix is >2GB but only 
160kb-wide, splitting it in narrower chunks will take a huge toll on the 
reading/writing speed compared to the huge sequential reads (or writes 
depending on the choices I left open) I proposed. The slow writes (or 
reads) due to numerous seeks would even be faster than in your algorithm 
as you advise a block size access which is only 512bytes, with 2G of RAM 
you can write/read in ~ 2 * 10^9 / 20000 * 8 = 12500 bytes (12288 bytes 
is the nearest multiple of 512), so it should be around 24 times faster 
(assuming inverse proportion of bandwidth vs number of seeks).

The problem with splitting the matrix in submatrix (though an elegant 
solution) is that it doesn't try to minimize disk seeks. Rectangular 
portions as high or wide as the matrix are better suited to disk access 
as they minimize the number of seeks in at least one of the read/write part.

Lionel