Optimizing a Manual String Reversal

written in ruby, technical

Sometimes it’s nice to figure out what the logic is behind Ruby’s object classes.

Last night I was working on a string_reversal method which as the name says is meant to return a reversed string. As always start by writing things out, how would I do this? Obvious first step create a suitably named method and take in an argument (optional), then retrieve the last element of the string and place it at the front until the entire string is reversed. Simple in writing but so many choices in how to code it!

Let me post my original code, don’t laugh it gets better I promise.

[original.rb]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  def reverse_string(arg)
    if arg.is_a?(String)
      new_str = ""
      chars = arg.chars
      i = 1
      while (i <= chars.length)
        new_str += chars[chars.length-i]
        i+=1
      end
      new_str
    else
      "Send a string next time!"
    end
  end

Let me explain this method, it takes in an argument and proceeds to check if the argument is a string before it proceeds. If it is a string then three new variables are initialized in the scope of the method, new_str, chars, and i. new_str will be used to hold the reversed string, chars is the return value of Ruby String method chars() that creates an array of characters from the string, [“h”,“e”,“l”,“l”,“o”], and lastly i is a counting variable. My first thought was to grab elements from the end of the array to the beginning, chars.length - 1 would give me “o” so i was set to 1. I concatenated each element of the array, from the last element to the first, to the new_str variable. Afterwards, I incremented the i varibale by 1 and outside of the while loop I returned the new_str.

Using my previous example of “hello”, if this string were to be sent to this method then we would receive “olleh”. Now, from just looking at the method you would assume that this is working to the best of it’s abilities but there is one big flaw, the time. The way this method is written there are three logic points, “is it a String?”, calling upon chars to receive an array of characters, and comparing each element of the character array. Right now this method has a Big O Notation value of ‘n’ as it needs to traverse each element of the array.

The first alternate way to reverse a string can be seen in the following first_alternate_reverse method. Similarly to my previous reverse_string method this will receive a string as an argument and create an array of characters from the string. Then by using the Array pop() method we remove the last element from chars(self) and return it. This is runs as many times as the length of the character array.

[first_method.rb]
1
2
3
4
5
6
  def first_alternate_reverse(string)
    word = ""
    chars = string.each_char.to_a
    chars.size.times{word << chars.pop}
    word
  end

Like the original reversal method this first alternative method has a Big O Notation of ‘n’, the method must go through each element to of the array. We can optimize this logic further by bringing the Big O Notation down to ‘n/2’.

The second alternate way to reverse a string can be seen in the following second_alternate_reverse method. From first glance this method seems different from the first two as it doesn’t have an argument but it’s quite similar. What is happening here is we are creating a reverse method that can be called on a string, exactly like the reverse() method Ruby has already defined.

Let me walk you through this code. The second_alternate_reverse method is taking in the variable x in test.rb and this becomes ‘self’. At the beginning of the method self = “hello” and half_self = 2. Keep in mind 5/2 != 2.5, Ruby rounds when it’s dealing with integers (if you did want a float then you would need to make the ‘2’ into a ‘2.0’).

Looking at the next line you can see the code inside the curly brackets is only being run as many times as half_self is equal to, in this case it’s “2”. Inside the curly brackets we are swapping mirrored characters in the string such as “h” and “o” or “e” and “l” until we reach the center of the string.

[test.rb]
1
2
  string = "hello"
  string.second_alternate_reverse
[second_method.rb]
1
2
3
4
5
6
7
  class String
    def second_alternate_reverse
      half_self = self.length / 2
      half_self.times {|x| self[x], self[-x-1] = self[-x-1], self[x] }
      self
    end
  end

If you wanted a permanent solution like reverse!() you could add an exclamation mark after the method name as such “second_alternate_reverse!”

I hope you’ve found this informative and useful in your programming endeavors!

Keep on being badass programmers!


Comments