Buttercola: Reverse Large String

Buttercola: Reverse Large String
Reverse a string byte by byte. However, the string is too large to fit into memory, so it is stored in a file on disk. How do you reverse that string?

Analysis:
Since the string is stored on disk, if each time we load one character from front and end of the string, from the disk to memory, swap and store it back, it will involve too many I/O operations. So the idea is to load the string chunk by chunk. 

  public String reverseString(String s) {

    if (s == null || s.length() == 0) {

      return "";

    }

     

    final int chunkSize = 3;

    char[] temp = s.toCharArray();

    int len = s.length();

     

    int start = 0;

    int end = len - chunkSize;

     

    while (start < end) {

      int len1 = Math.min(chunkSize, end - start);

      int len2 = chunkSize;

      char[] buf1 = new char[len1];

      char[] buf2 = new char[len2];

      fread(temp, buf1, start, len1);

      fread(temp, buf2, end, len2);

       

      reverse(buf1, buf2);

       

      fwrite(temp, buf1, start, len1);

      fwrite(temp, buf2, end, len2);

       

      // update start and end

      start += len1;

      end -= len2;

    }

     

    if (start >= end) {

      end += chunkSize - 1;

      char[] buf = new char[end - start + 1];

      fread(temp, buf, start, end - start + 1);

      reverse(buf);

      fwrite(temp, buf, start, end - start + 1);

    }

     

     

    return new String(temp);

  }

   

  // Read size of len bytes from the starting index, from s to buf

  private void fread(char[] s, char[] buf, int start, int len) {

    for (int i = 0; i < len; i++) {

      buf[i] = s[i + start];

    }

  }

   

  // Write size of len bytes from the staring index, from buf to file s

  private void fwrite(char[] s, char[] buf, int start, int len) {

    for (int i = 0; i < len; i++) {

      s[i + start] = buf[i];

    }

  }

   

  // Reverse the chars in the two bufs

  private void reverse(char[] buf1, char[] buf2) {

    int start = 0;

    int end  = buf2.length - 1;

     

    for (start = 0; start < buf1.length; start++) {

      char temp = buf1[start];

      buf1[start] = buf2[end];

      buf2[end] = temp;

      end--;

    }

     

    if (end > 0) {

      start = 0;

      while (start < end) {

        swap(buf2, start, end);

        start++;

        end--;

      }

    }

  }

   

  // Revserse the chars in one buf

  private void reverse(char[] buf) {

    int start = 0;

    int end = buf.length - 1;

     

    while (start < end) {

      swap(buf, start, end);

      start++;

      end--;

    }

  }

   

  private void swap(char[] buf, int i, int j) {

    char temp = buf[i];

    buf[i] = buf[j];

    buf[j] = temp;

  }

Follow-up: What if the system is crashed/down in the meanwhile, how can we know the position we need to re-start next?
One possible solution could use a transaction log. Specifically, when we read two chunks from the file, we may log
START
start = xxx
end = xxx
And AFTER we finish writing the reversed string into the file, we log an END, e.g.
START
start = xxx
end = xxx
END

So the next time when the system gets restarted, it first checks if the pair of  <START, END> is completed. If not, we re-wind the position and reverse the chunk again. 

But this solution is not 100% safe. If it safe if the system is crashed before wring the final results. In this case, since the final reversed chunks are not written into disk i.e., the original string has not been changed, it is safe to re-play and reverse the chunk again. 

But what if the system is crashed when we write the result into file. e.g. 
ABC DE FGH
after we reverse the first and the last chunk, the two chunks become
HGF and CBA, and then we should write the two chunks into the file. 
If the system is down right after we write the H and C, it is not correct to rewind the start and end pointer and reverse the chunks again because the string has been already partially reversed. 

There could be two solutions to solve this issue. One solution is do out-of-place reverse, that is, store the reversed string into a new file. In this case, since the input string has not been modified, it's always safe to re-wind the start and end pointer and reverse the chunk again. 

Another solution could be do a more detailed transaction log. That is, instead of logging right before and after the chunk is loaded and stored, we log the position of start and end after each character in the chunk has been stored into the disk. So if the system is crashed in the meanwhile, we know the last position we have successfully reversed the string. 

Read full article from Buttercola: Reverse Large String