Matrix Transpose

March 20, 2015

Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:

11 12 13 14 11 21 31
21 22 23 24 12 22 32
31 32 33 34 13 23 33
14 24 34

That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.

Your task is to write a program that transposes a matrix to large to fit in memory. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

5 Responses to “Matrix Transpose”

  1. Rutger said

    In Python, assuming that we cán fit one row in memory..

    file_like_object = []
    file_like_object.append([11,12,13,14,11,21,31])
    file_like_object.append([21,22,23,24,12,22,32])
    file_like_object.append([31,32,33,34,13,23,33])
    file_like_object.append([14,24,34])
    
    
    max_row_length = 1
    i = 0
    while i < max_row_length:
    	for row in file_like_object:
    		if len(row) > max_row_length:
    			max_row_length = len(row)
    		if i < len(row):
    			print row[i],
    	print
    	i += 1
    
  2. matthew said

    If it’s a square matrix with the row and column lengths 2^n, we can transpose in just n linear scans through the array, zipping together the front and back halves (like a riffle shuffle):

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []

    trans 0 m s = s
    trans n m s = trans (n-1) m (zipl (take m s) (drop m s))

    test n = trans n (2^(2*n-1)) [0..2^(2*n)]
    main = print (test 2)

  3. matthew said

    Actually, this will work for any matrix where the number of rows is a power of two. Tidying up the previous solution (now trans m n s expects m to be half the total array size, n is the number of rows, s is the array):

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []

    trans m 1 s = s
    trans m n s = trans m (n `div` 2) (zipl (take m s) (drop m s))

    main =
    print [0..23] >>
    print (trans 12 8 [0..23]) >>
    print (trans 12 4 [0..23])

  4. matthew said

    Just trying to get some nicer formatting:

    zipl (a:s) (b:t) = a:b:zipl s t
    zipl _ _ = []
    
    trans m 1 s = s
    trans m n s = trans m (n `div` 2) (zipl (take m s) (drop m s))
    
    main =
    print [0..23] >>
    print (trans 12 8 [0..23]) >>
    print (trans 12 4 [0..23])
    
  5. matthew said

    And where the number of columns is 2^n, we can invert the process – output all even elements, then all odd elements, repeat n times. In Haskell:

    pairs (a:b:s) = (a,b):pairs s
    pairs _ = []
    
    trans 0 s = s
    trans n s = trans (n-1) (uncurry (++) $ unzip $ pairs s)
     
    main =
         print [0..23] >>
         print (trans 1 [0..23]) >>
         print (trans 2 [0..23]) >>
         print (trans 3 [0..23])
    

    Or maybe this corresponds better to how we might do it with files:

    evens (a:s) = a : odds s
    evens _ = []
    odds (_:s) = evens s
    odds _ = []
    
    trans 0 s = s
    trans n s = trans (n-1) (evens s ++ odds s)
    
    main =
         print [0..23] >>
         print (trans 1 [0..23]) >>
         print (trans 2 [0..23]) >>
         print (trans 3 [0..23])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: