In episode 138, Casey had to implement "un-interleaving" for audio channels, and someone noticed that it can be viewed as a matrix transposition algorithm.
I decided to play around a bit and measure how well different algorithms work.
I've implemented four matrix transposition algorithms (or three, if you are being pedantic).
The first two are naive matrix transposition, the difference is order of iteration - rows -> cols, or cols -> rows.
This algorithm is using a scratch matrix to copy values to and from, very simple to implement if you remove error checking.
The third algorithm is following cycles, described on wikipedia:
https://en.wikipedia.org/wiki/In-...re_matrices:_Following_the_cycles
But you have to take into account that you need to visit elements in cycle exactly once and you need to visit all cycles. In my version it is done by creating a byte array with each byte flagging node as visited, while iterating over all items in matrix to find new cycles and follow them.
The fourth algorithm is not using temporary memory, but it is VERY inefficient - for each element to test if the cycle has been visited, I do a dry-run in which I test if I land on the element before current. This algorithm has quadratic complexity.
The code is attached to the message and available at https://gist.github.com/m1el/2500c717043a475f4d9a
Please note that I don't expect this code to win any beauty contest.
The result on my machine is (in milliseconds):
naive cols: 193
naive rows: 180
cycles: 2971
cycles const space: 10899
So naive matrix transposition wins here :)
I tried to think about other smart ways to follow cycles but there might be no pretty way to do it, if anyone knows a mathematician, ask them how to locate loops for the formula: x_{i+1} = (x_i*w + floor(x_i/h)) mod (w*h) (look at a pretty formula)
I'd like to note that when transposing huge matrices (not 2*Huge but Huge*Huge) it is almost necessary to take caching into account, and there is an article on that: http://blog.netduma.com/2013/01/cache-money-hoes-attached-code.html
I decided to play around a bit and measure how well different algorithms work.
I've implemented four matrix transposition algorithms (or three, if you are being pedantic).
The first two are naive matrix transposition, the difference is order of iteration - rows -> cols, or cols -> rows.
This algorithm is using a scratch matrix to copy values to and from, very simple to implement if you remove error checking.
The third algorithm is following cycles, described on wikipedia:
https://en.wikipedia.org/wiki/In-...re_matrices:_Following_the_cycles
But you have to take into account that you need to visit elements in cycle exactly once and you need to visit all cycles. In my version it is done by creating a byte array with each byte flagging node as visited, while iterating over all items in matrix to find new cycles and follow them.
The fourth algorithm is not using temporary memory, but it is VERY inefficient - for each element to test if the cycle has been visited, I do a dry-run in which I test if I land on the element before current. This algorithm has quadratic complexity.
The code is attached to the message and available at https://gist.github.com/m1el/2500c717043a475f4d9a
Please note that I don't expect this code to win any beauty contest.
The result on my machine is (in milliseconds):
naive cols: 193
naive rows: 180
cycles: 2971
cycles const space: 10899
So naive matrix transposition wins here :)
I tried to think about other smart ways to follow cycles but there might be no pretty way to do it, if anyone knows a mathematician, ask them how to locate loops for the formula: x_{i+1} = (x_i*w + floor(x_i/h)) mod (w*h) (look at a pretty formula)
I'd like to note that when transposing huge matrices (not 2*Huge but Huge*Huge) it is almost necessary to take caching into account, and there is an article on that: http://blog.netduma.com/2013/01/cache-money-hoes-attached-code.html
Edited by m1el
on