From: Pascal Bourguignon <pjb@...>
Date: 2008-04-27T20:30:04+09:00
Subject: Re: Transpose a large file(>2GB)

Ams Lo <rgowka1@gmail.com> writes:

> Exactly.. Sorry, I should have explained it better..

Wrong. It should be below.

> Xavier Noria wrote:
>> On Apr 27, 2008, at 12:59 , Xavier Noria wrote:
>> 
>>> 12
>>> 3
>>> 456
>>>
>>> You want
>>>
>>> 134
>>> 2 5
>>>   6

Like this:

> Exactly.. Sorry, I should have explained it better..

Either have a 64-bit machine, and do it naively,

or have a vector of file positions pointing to the beginning of each
line O(file_size), and then write the character pointed to by these
file position (or a space if they reached the end of line) on a single
output line, and advance the file positions (unless they reach the end
of line). Repeat until all have reached end of line.

Note: this may be bad on the disk, if the input file has a lot of
lines.  In this case, you may want to implement a recursive
transposition algorithm:

to transpose a matrix of dimension (c r) do
  if (c=1) and (r=1) 
  then return the matrix itself
  else
       return the matrix made of:
         | transpose of submatrix [0..(c/2)[,[0..(r/2)[   transpose of submatrix [0..(c/2)[,[(r/2)..r[  |
         | transpose of submatrix [(c/2)..c[,[0..(r/2)[   transpose of submatrix [(c/2)..c[,[(r/2)..r[  |

that is, you cut the matrix in four, transpose each part
independently, and combine the four parts, exchanging the parts on the
anti-diagonal.

With this algorithm disk accesses should be more localized, so you may
get better speed on very big files with very big lines.

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
----------> http://www.netmeister.org/news/learn2quote.html <-----------
---> http://homepage.ntlworld.com/g.mccaughan/g/remarks/uquote.html <---

__Pascal Bourguignon__                     http://www.informatimago.com/