Again I have been coding some stuff and analysing the runtimes. This time was the two algorithms for rotating a vector left by N locations. This, a reverser algorithm, is used by Brian Kerningham and Plaugher in their text editor and also by Ken Thomson in the editor for Unix and by Bentley too. So, if ABCD is a vector you want to rotate it by 2 locations to the left, we get CDAB.
The first algorithm is a Juggler algorithm which juggles the values at indices similar to a shift. This is something that, I arrived at and so I will describe the other 'Reverser' algorithm. It goes like this. AB be the string. A is N units length and we want to rotate by N so the result is BA. First do a Ar B where Ar stands for the reverse of A. Then Ar Br. Then ( Ar Br )r. This should give you BA. Brian reported that, this worked first time. I also am glad to report that, it worked first time ;) :)). This is ofcourse if you have a reverse function to do the Ar and Br etc. In my case it is just a switch of array locations starting from the extremities and moving to the center of the array.
The general analysis of the two algorithms is not much a do to share on a blog. The reverser is always better than the Juggler algorithm. They did exhibit some minor changes in their runtimes of the order of 1 or 2 ms.
Well that said, *There is a general question of how the GCD of N and the length of the string figure in the analysis. So, this is what I did (open to questioning).
Input a 1248000 long string.
N is such that, N is the GCD.
At lower values of N (the GCD), both algorithms are the closest in terms of runtimes. Here is N = 4. Almost same. 10 ms and 10.7 ms.
At huge N for N = 1248, the Juggler takes almost twice the time of the Reverser. 6.99 and 13.1.
This seems to be consistent. Anyways, I think I will use the Reverser in my encrypting text editor Crystal. :)
No comments:
Post a Comment