How can I improve the performance of this small Ruby function?

1

I am currently doing a Ruby challenge and get the error Terminated due to timeout for some testcases where the string input is very long (10.000+ characters).

How can I improve my code?

def alternatingCharacters(s)
counter = 0
s.chars.each_with_index { |char, idx| counter += 1 if s.chars[idx + 1] == char }
return counter

end

2

You don’t say what the challenge is, so I’m going to assume that the code shown is functionally correct - it counts the number of times two consecutive characters in the string have the same value. The each_with_index executes the block once for each character in the input string. So in your long string example, that’s 10K times. So let’s look at what is happening inside the loop.

  1. We convert the input string to an array of characters, and we know it has 10K characters
  2. We look up the next item and compare it to the char passed into the block
  3. On the last item in the array, idx + 1 is outside the bounds of the array, and in another less forgiving language it might have thrown an error

So as the string gets longer, the performance degrades exponentially, as we keep converting ever longer strings into arrays of characters, and we do it more times. With 10K, it takes about 7.4s on my ageing laptop. With 20K, it takes 33.1s, which probably explains your timeout issue.

I moved the conversion to the character array outside the loop so it only happens once:

  def alternating_characters_better(sample)
    counter = 0
    sample_list = sample.chars
    sample_list.each_with_index { |char, idx| counter += 1 if sample_list[idx + 1] == char }
    counter
  end

which brought the execution time down to 3.8ms for 10K and 7.3ms for 20K

I thought I could make it better by simplifying it further:

  def alternating_characters_not_as_good(sample)
    counter = 0
    prev_char = ''
    sample.chars.each do |char|
      counter += 1 if char == prev_char
      prev_char = char
    end
    counter
  end

but this came in slightly worse at 11.1ms for 20K (although it doesn’t go out of bounds at the end of the array).

3

I did it like this

sample = SecureRandom.alphanumeric(10_000).split ''
counter = 0
while sample.present? do
  matcher = sample.shift
  counter += 1 if matcher == sample[0]
end

counter

Virtually instantaneous on my MacBook Pro :slight_smile:

4

I ran this under ruby-profand it took 83ms on my machine. However, about 80% of that was consumed by the generation of the sample string for the test :roll_eyes: SecureRandom.alphanumeric() is a bit of a CPU hog, it would appear…

Anyway, I switched to ('AA' * 10_000).chars for the string generation and it dropped to 24ms. And although it’s slightly slower than the earlier attempts, it feels cleaner and more idiomatic, so if absolute performance isn’t the only goal I’d probably go with @itsterrys answer with a slight modification to avoid the dependency on present?

# frozen_string_literal: true

sample = ('AA' * 10_000).chars
counter = 0

while sample.length.positive?
  matcher = sample.shift
  counter += 1 if matcher == sample[0]
end

puts counter
1 Like