Learn from matrix transposition

This time, we will solve a common problem – matrix transposition.

Description and simple solution

Give matrix of n*n, return the transposed matrix.

We can come up with the simple solution from the definition of matrix transposition:

for x < n
    for y < x
        swap(a[x,y], a[y,x])

Different problem

It’s so easy, right? Now we move another similar problem:

how to efficient transpose a very large matrix(n*n) on the tape?

They are similar, both want to transpose a matrix. They are also very different for the data source affect how we can retrieve data effectively. When we have to read data from tape, element can’t be randomly accessed any more. Upper solution works, but too slow.

int n = 200;
// I use LinkedList to simulate the tape
LinkedList<Integer> matrix;
// init code
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        final int origin = i * n + j;
        final int sym = j * n + i;
        Integer f = matrix.get(origin);
        matrix.set(origin, matrix.get(sym));
        matrix.set(sym, f);
    }
}
System.out.println(System.nanoTime() - start);

// I run upper code on my machine, it cost almost 2 second when there only 40000 elements(n = 200).

So any better way?
We may find upper code use reference element by index four times which is slow in LinkedList and can be optimized to be only twice by using iterator:

for (int i = 0; i < n; i++) {
    for (int i1 = 0; i1 < i + 1; i1++) {
        it.next();
    }
    for (int j = i + 1; j < n; j++) {
        final int sym = j * n + i;
        Integer f = it.next();
        it.set(matrix.get(sym));
        matrix.set(sym, f);
    }
}

It indeed faster, but we can make better by sorting.

sort ?

Yes, we can transpose by sorting!

private static class IntIJ implements Comparable<IntIJ> {
    private final int content;
    private final int weight;

    IntIJ(int content, int r, int c, int n) {
        this.content = content;
        this.weight = c * n + r;
    }
}

By giving every position a weight, we can transpose matrix by sorting. In this way, we can not only finish in O(n^2 * log n)( when just using index, we need O(n^3) ), but also we can make use of cache effect, space locality to run faster.

The following is one comparison result of different implementations of transposition:

// n = 200
index transpose
2024508062
iterator transpose
751467034
sort transpose
26191352

Another variant – use antidiagonal as symmetric axis

simple way from definition

sum = 2*n - 2
for i, j of a[][]
    gap = i - j
    newi = (sum + gap) / 2
    newj = sum - newi
    swap(a[i][j], a[newi][newj])

sort

class Weight {
    int x, y;
    int weight = (2n-2-x) + (2n-2-y) * n;
}

Written with StackEdit.