I'm trying to solve the four color theorem in Ruby.A map is like this:ccaaaabaaadcbabcdcbbbcdcabccccI have this, but it's slow. How can I make it better?#!/usr/bin/env rubyclass 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    endendclass 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    endendif __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_colorend
Four color theorem
optimization;ruby
I/O bottleneckYour 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 bottlenecksOnce 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     totaltime   seconds   seconds    calls  ms/call  ms/call  name40.57    0.71      0.71     2082     0.34    10.12  ColoredMap#each_direction15.43    0.98      0.27    55881     0.00     0.00  Array#[]6.86     1.10      0.12     1141     0.11     0.14  Array#select6.86     1.22      0.12     2082     0.06    10.28  ColoredMap#color_region5.14     1.31      0.09     8219     0.01     0.03  String#colored?.....0.00     1.89      0.00        1     0.00     0.00  Kernel.puts0.00     1.89      0.00        1     0.00  1890.00  #toplevelruby -rprofile colors.rb biggermap  1,90s user 0,13s system 99% cpu 2,034 totalI 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.