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?
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.
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!
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.