Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm trying to solve the four color theorem in Ruby.

A map is like this:

ccaaaa
baaadc
babcdc
bbbcdc
abcccc

I have this, but it's slow. How can I make it better?

#!/usr/bin/env ruby

class String
    def visit
        @visited = true
    end

    def visited?
        @visited == true
    end

    def color
        @color || "_"
    end

    def color=(newcolor)
        @color = (newcolor)
    end

    def colored?
        @color != nil
    end
end

class ColoredMap
    COLORS = %w(R G B Y)

    def initialize(map)
        @map = map
    end

    def color_map
        # go through each square and color the region if not already colored
        @map.each_with_index do |line, row|
            line.each_with_index do |cell, col|
                color_region(row, col, @map[row][col], {}) unless cell.colored? 
            end
        end
    end

    def color_region(x, y, name, colors_seen)
        # mark as visited
        @map[x][y].visit
        # pick a color that hasn't been seen
        chosen_color = nil

        # iterate over each neighboring cell - Recurse or note color
        each_direction(x, y) do |xp, yp|
            if (@map[xp][yp] == name) && !@map[xp][yp].visited?     # same region
                chosen_color = color_region(xp, yp, name, colors_seen) # recursive call
            elsif @map[xp][yp].colored?     # neighboring cell already colored
                colors_seen[@map[xp][yp].color] = true  
            end
        end

        # set to the color already chosen or to a color not yet seen
        @map[x][y].color = chosen_color || COLORS.select{|color| !colors_seen[color]}[0]
    end

    # Enumerator returning each available direction
    def each_direction(x, y)
        yield x-1, y if x > 0 #up
        yield x, y-1 if y > 0 #left
        yield x, y+1 if y < @map[x].length-1 #right
        yield x+1, y if x < @map.length-1 #down
    end

    def to_s
        @map.map do |line|
            line.join + "\n"
        end.join
    end

    def to_color
        @map.map do |line|
            line.map { |cell| cell.color }.join << "\n"
        end.join
    end

    def to_debug
        @map.map do |line|
            line.map do |cell|
                puts cell + cell.color + (cell.visited? ? "v" : ".") + " "
            end
        end.join
    end
end

if __FILE__ == $PROGRAM_NAME

    abort "NO ARGUMENTS GIVEN - map file must be provided" unless ARGV[0]

    begin
        mapfile = File.new(ARGV[0])
    rescue
        abort "Unable to open file '#{ARGV[0]}'"
    end

    # read in map file
    regions = []
    mapfile.each_with_index do |line, line_num|
        regions[line_num] = line.chomp.split(//)
    end

    # color map
    mymap = ColoredMap.new(regions)
    mymap.color_map

    # display colored map
    puts mymap.to_color
end
share|improve this question
    
How are you defining slow? The algorithm itself is optimal, and the code is fast! You could go for micro-optimizations, but how fast do you want the code to be? And for what map sizes? Have you consider writing this in a language like C? –  Quentin Pradet Feb 19 '13 at 12:23
    
Here, it is 0,01s user 0,01s system 91% cpu 0,018 total on an old Core 2 CPU. Profiling using ruby -rprofile shows that most of the time is spent in each_direction. But is it because of the tests? The Ruby VM? Something else? Hard to say! I can provide a few alternative ways to program color_region if you wish. –  Quentin Pradet Feb 19 '13 at 13:06
    
Don't remove the question! It's not stupid, it can happen to anyone. You can simply say that it was indeed an I/O issue. No worries, everybody is here to learn and every programmer can be bitten by such issues. –  Quentin Pradet Feb 19 '13 at 14:32
    
@Cygal Yeah Sorry, I was really thinking it was a stupid question after all but it might help others actually. –  bl0b Feb 19 '13 at 14:48

1 Answer 1

up vote 4 down vote accepted

I/O bottleneck

Your first bottleneck is not the algorithm. As you see from your time output (0.29s user 0.11s system 10% cpu 3.723 total), your program only spent 10% of his time in the CPU. This means that even if your program took 0ms, you would only gain 10%!

You need to understand what takes that much time. Is it because the disk was busy? Or is it full? How long does it take when you run the program a second time? Is it faster? Is it still only spending 10% of its time in the CPU? Measure the time taken in the three main parts (read file, color map, display map) and see where it is slow (using Time.now which takes into account I/O latencies that the Ruby profiler does not).

Other bottlenecks

Once the I/O bottleneck is solved, you can turn to other optimizations. They are called micro-optimizations since the algorithm doesn't change: you're trying to use a few tricks to make it faster. Since the your code was very fast with the provided map, I created a bigger one with a few copy/pastes and ran the standard Ruby profiler to see where it was spending time.

$ time ruby -rprofile colors.rb biggermap
(colored map)
%   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
40.57    0.71      0.71     2082     0.34    10.12  ColoredMap#each_direction
15.43    0.98      0.27    55881     0.00     0.00  Array#[]
6.86     1.10      0.12     1141     0.11     0.14  Array#select
6.86     1.22      0.12     2082     0.06    10.28  ColoredMap#color_region
5.14     1.31      0.09     8219     0.01     0.03  String#colored?
.....
0.00     1.89      0.00        1     0.00     0.00  Kernel.puts
0.00     1.89      0.00        1     0.00  1890.00  #toplevel

ruby -rprofile colors.rb biggermap  1,90s user 0,13s system 99% cpu 2,034 total

I don't know how the profiler works, so we need to be careful with the results. I think it works like gprof: it adds instrumenting code to every method call, and then reconstructs a table sorted by cumulative seconds which means that it's not too precise. Here, according to the profiler, 10ms/call is spent in each direction. I think it's mostly due to the yields.

  • The first candidates for slowness are all those yields. They are elegant, but you can try to unroll the loop manually to see how it improves.
  • The second candidate is the recursion. You can loop from (0,0) to (n,n) and look if there are existing neighbors with a color. If not, then assign a new color. This is essentially the same algorithm but this avoids having a huge call stack and only visits each node once.
  • Now that your code is iterative, you can try to minimize the number of checks like x > 0 and y < .... If you find a simple way to predict that you are in the middle of the loop, then no checks are needed.

The point is to run the profiler after each optimization and try to see if there is a new bottleneck arising.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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