4
\$\begingroup\$

Working through CodeEval's Interrupted Bubble Sort, I have a working algorithm, but there's a speed issue. I'm trying to do this with Ruby and I keep getting an error that it's timing out after 10 seconds. I'm not sure what else I could be doing here to speed things up.

def bubble(arr, interrupt)

    i = 0
    while i < interrupt
        for x in 1..arr.length-1
            if arr[x-1] > arr[x]
                arr[x-1], arr[x] = arr[x], arr[x-1]
            end
        end
        i += 1
    end

end


File.open(ARGV[0]).each_line do |line|

    line = line.chomp.split(" ");
    interrupt = line.pop.to_i
    line.pop

    line.map do |x| x = x.to_i end
    bubble(line, interrupt)
    puts line.join(" ")

end
\$\endgroup\$
6
\$\begingroup\$

There shouldn't be a speed issue (so far as I can tell), but there is an outright bug:

line.map do |x| x = x.to_i end

You're not storing the result of the map, you're just throwing it away. So line doesn't change, and you end up comparing the elements lexicographically, i.e. as strings. So "48" ends up being less "5" and such.


Other notes:

  • The Ruby convention is to use 2 spaces for indentation. Not 4 spaces, not tabs.

  • You don't need semicolons.

  • When writing a single line block, use {..} instead of do..end

  • When simply invoking the same single method on all elements in an array, you can use a shortcut: line.map(&:to_i)

  • You can exclude the last element in a range with 3 dots (...), so 1..arr.length-1 becomes just 1...arr.length

With that and a few other things you get:

def bubble(array, iterations)
  iterations.times do
    (1...array.length).each do |i|
      if array[i-1] > array[i]
        array[i-1], array[i] = array[i], array[i-1]
      end
    end
  end
end


File.open(ARGV[0]).each_line do |line|
  line = line.chomp.split(" ")
  iterations = line.last.to_i

  values = line[0...-2].map(&:to_i)
  bubble(values, iterations)

  puts values.join(" ")
end

Now, this is just a challenge, but for production code, I'd avoid the side-effects of bubble, and return a new array instead. But that's a different story.


Edit: Since it's still too slow, maybe it's because the input is crafted to trick you. For instance, a line that calls for billions of iterations on a relatively small set of values will, with the code above, cause waaay too many pointless iterations. I.e. the list may be sorted already, but the algorithm will keep loop through it the specified number of times.

A pretty simple solution would be something like:

def bubble(array, iterations)
  iterations.times do
    sorted = true
    (1...array.length).each do |i|
      if array[i-1] > array[i]
        sorted = false
        array[i-1], array[i] = array[i], array[i-1]
      end
    end
    break if sorted
  end
end

Additionally, you can skip stuff by checking the number of iterations before calling bubble. If it's zero, there's no need for the map:

File.open(ARGV[0]).each_line do |line|
  line = line.chomp.split(" ")
  iterations = line.last.to_i

  unless iterations.zero?
    values = line[0...-2].map(&:to_i)
    bubble(values, iterations)
  end

  puts values.join(" ")
end

Now of course it may just be that the input is just huge, and Ruby isn't the fastest thing. But one has to assume that the challenge can actually be solved.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Our answers are similar, but yours is more in-depth, you are missing a ! on your map as it should work in-place. I really like the point about avoiding side-effects \$\endgroup\$ – Caridorc Sep 1 '15 at 17:38
  • \$\begingroup\$ Edit: the ! Is not missing as the map does not work in place, I misread :). Still a literal bug-fix would use the in-place map! \$\endgroup\$ – Caridorc Sep 1 '15 at 17:40
  • \$\begingroup\$ @Caridorc Yeah, you can just use the map-bang method instead. I just tend to avoid those. I prefer to assign stuff to a new variable since it's been transformed; keep input and output separate, so to speak. On the other hand, the code already uses pop, so the "damage" is done, I suppose. Meh, I'll change that, actually. And yeah, the answers are similar. I was writing mine in an editor, so I didn't see yours until I'd already written it. \$\endgroup\$ – Flambino Sep 1 '15 at 17:52
  • 1
    \$\begingroup\$ I also tend to avoid in-place operations, if memory-usage were such a concern, I would not be using Ruby in the first place. About the similarity, great minds think alike :) \$\endgroup\$ – Caridorc Sep 1 '15 at 17:54
  • \$\begingroup\$ @Flambino - thanks for the detailed response. Even with the changes you suggest the test is failing for taking longer than 10 seconds to run. \$\endgroup\$ – John Halbert Sep 2 '15 at 9:01
3
\$\begingroup\$

while with manual incrementing should be avoided at all costs in Ruby, the following reads much more easily:

interrupt.times do
    for x in 1..arr.length-1
        if arr[x-1] > arr[x]
            arr[x-1], arr[x] = arr[x], arr[x-1]
        end
    end
end

You can simplify this line:

line.map!(&:to_i)

As ! Makes methods work in place. &: converts a method to a block.


(minor) remove that semicolon, it is really weird:

line = line.chomp.split(" ");
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks. Will it execute faster as well? \$\endgroup\$ – John Halbert Sep 1 '15 at 17:27
  • \$\begingroup\$ @JohnHalbert Probable, built-ins are written in C, and are very fast to use. \$\endgroup\$ – Caridorc Sep 1 '15 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.