String reversing x times

Question

Inspired by CodeWars

We have a string s

Let's say you start with this: "String"
The first thing you do is reverse it: "gnirtS"
Then you will take the string from the 1st position and reverse it again: "gStrin"
Then you will take the string from the 2nd position and reverse it again: "gSnirt"
Then you will take the string from the 3rd position and reverse it again: "gSntri"

Continue this pattern until you have done every single position, and then you will return the string you have created. For this particular string, you would return: "gSntir"

The Task:
In this kata, we also have a number x
take the above reversal function, and apply it to the string x times.
Return the result of the string after applying the reversal function to it x times.

Note:
String lengths may exceed 2 million and x may exceed a billion. Be ready to optimize.

My solution works but times out and I am having trouble optimizing much further. The code contains a lot of useful comments but here is a summary of what I have attempted to do.

Cycle Length Calculation
Because the above algorithm generates cycles, we can calculate a strings cycle length and perform x % cycleLength to determine exactly how many iterations we must perform to get our end result, instead of having to calculate all the duplicate cycles. More on cycle lengths can be found here and here.

This method is better than nothing but can still get quite demanding on high cycle lengths. Potentially there is a better way of calculating the cycle length without so many iterations?

public final class XIterations {
 public static String xReverse(String s, long x) {
 // Using the cycle length and modular arithmetic,
 // We can find the exact number of reverse operations we will need to perform.
 // This way we will only perform operations we need to complete.
 long iterationsRequired = x % calculateCycleLength(s.length());
 // TODO: There may exist an algorithm that allows a linear transformation given x
 while (iterationsRequired > 0) {
 s = reverse(s);
 iterationsRequired--;
 }
 return s;
 }
 // The xReverse algorithm produces cycles and therefore duplicates.
 // This helper method determines the length of the cycle using the number of characters a string contains.
 // More detail on the algorithm can be found at:
 // https://oeis.org/A003558
 // https://oeis.org/A216066
 // TODO: There may exist an algorithm that requires less iterations to find the cycle length
 private static int calculateCycleLength(int n) {
 // Cache these so we only calculate them once.
 final int a = 2 * n + 1;
 final int b = 2 * n;
 int cycleLength = 1;
 while (true) {
 double c = Math.pow(2, cycleLength);
 if (c % a == 1 || c % a == b) {
 return cycleLength;
 }
 cycleLength++;
 }
 }
 public static String reverse(String s) {
 StringBuilder sb = new StringBuilder();
 int front = 0;
 int back = s.length() - 1;
 // Does not account for odd length strings. Will not add the middle character.
 while (front < back) {
 sb.append(s.charAt(back--));
 sb.append(s.charAt(front++));
 }
 // Account for odd length strings. Add the middle character that was never added by loop.
 if (front == back) {
 sb.append(s.charAt(front));
 }
 return sb.toString();
 }
}

I am mostly interested in optimization tips but of course any feedback is welcome.

• Veedrac: You don't need to actually run the algorithm, you can do this in one pass. Consider that each iteration you have one new character at the front that will never change position, and figure out how to get that value directly.

Answer 1

choice of language

Unfortunately Java is not the best choice for doing such tasks. Object creation, reference handling and alike simply takes time.

So to speed up we need to throw away some of the benefits provides by the JVMs standard lib and switch to procedural programming on arrays.

optimizations

The calculation of the cycle length is a clever trick. But there must be an algorithm without looping which would speed up this calculation too.

implementation

As mentioned a fast solution must avoid object creation at all and should work on an array of chars rather than on Strings. It should basically look like this:

public final class XIterations {
 public static String xReverse(String input, long iterations) {
 long iterationsRequired = iterations% calculateCycleLength(input.length());
 char[] chars = input.toCharArray();
 for(int i = 0 ; i < iterationsRequired ; i++)
 chars = reverse(chars);
 return new String(chars);
 }
}

In your code I cannot find how you handle the skipping of the start of the string. I would do this by using a recursive call like this:

private char[] reverse(char[] chars, int startIndex){
 if(chars.length == startIndex) {
 return chars;
 } else {
 // reverse chars in array starting at startIndex
 return reverse(chars, ++startIndex);
 }
}