Finding the transpose of a very, very large matrix

Question

I have this huge 2 dimensional array of data. It is stored in row order:

A(1,1) A(1,2) A(1,3) ..... A(n-2,n) A(n-1,n) A(n,n)

I want to rearrange it into column order

A(1,1) A(2,1) A(3,1) ..... A(n,n-2) A(n,n-1) A(n,n)

The data set is rather large - more than will fit on the RAM on a computer. (n is about 10,000, but each data item takes about 1K of space.)

Does anyone know slick or efficient algorithms to do this?

Answer 1

Create n empty files (reserve enough space for n elements, if you can). Iterate through your original matrix. Append element (i,j) to file j. Once you are done with that, append the files you just wrote.

Answer 2

You need a Matrix class, such that your whole app accesses a matrix through an instance of the class. Then a transpose can just be setting a flag that reverses the indexes when accessing an element. Instant transpose!

Answer 3

The naïve way is to just read through the file 10000 times and find the corresponding columns for each row. This should be easy to implement but I don't know how much time it will take to run the program.

In your comments you mentioned outputing another file which you then should sort with sort. That's a bad idea since it will take forever to sort such a large file. Sorting is a complex (or at least resource-heavy) problem, so generalizing the transpose into a sort is probably the wrong way to do it.