구글 입사 문제 그리고 Fixnum 확장 후 profile

우연히 구글 입사 문제 라는 블로그를 보다가 소스 코드에서 사용하고 있는  scan 함수가 왠지 어색해 보였다. 그래서 Fixnum 을 확장해 봤는데, 내가 만든 코드로 돌려보고 좌절했다.

 

Regexp::scan 함수는 c source 로 작성이 되어 있고, 내가 만든 코드는 ruby 를 확장한 거라서 코드를 읽기는 쉬우나 속도에 문제가 있다. 다시 한번 느끼는 거지만 속도가 중요하다면 반드시 c source 로 모듈을 개발해야 한다. 

- 원본 소스와 profile 결과

require 'profile'

i = 0
(1..999999).each do |m|
  i += m.to_s.scan(/1/).length
  if i == m and i != 1
    puts i
    break
  end
end

$ ruby quiz1.rb -r profile
199981
%   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
67.67    27.17     27.17        1 27170.00 40150.00  Range#each
7.97    30.37      3.20   199981     0.02     0.02  String#scan
6.45    32.96      2.59   199982     0.01     0.01  Fixnum#to_s
6.18    35.44      2.48   199981     0.01     0.01  Fixnum#+
6.13    37.90      2.46   199983     0.01     0.01  Fixnum#==
5.60    40.15      2.25   199981     0.01     0.01  Array#length
0.00    40.15      0.00        1     0.00     0.00  Kernel.puts
0.00    40.15      0.00        2     0.00     0.00  IO#write

- fixnum_ex.rb 를 사용한 소스와 profile 결과

class Fixnum
  def to_a
    number = self
    digits = []
    while true
      ret = number.divmod(10)
      digits.unshift(ret[1])
      break if ret[0] == 0
      number = ret[0]
    end
    digits
  end

  def each
    number = self
    while true
      ret = number.divmod(10)
      yield(ret[1])
      break if ret[0] == 0
      number = ret[0]
    end
  end
end

require 'profile'
require 'fixnum_ex'

i = 0
(1..999999).each do |m|
  m.each { |n| i += 1 if n == 1 }
  if i == m and i != 1
    puts i
    break
  end
end

$ ruby quiz2.rb -r profile
199981
%   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
64.79   202.36    202.36   199981     1.01     1.48  Fixnum#each
14.21   246.76     44.40  3066362     0.01     0.01  Array#[]
10.79   280.47     33.71  2377545     0.01     0.01  Fixnum#==
5.19   296.68     16.21  1088781     0.01     0.01  Fixnum#divmod
4.12   309.55     12.87        1 12870.00 312350.00  Range#each
0.90   312.35      2.80   199981     0.01     0.01  Fixnum#+
0.00   312.35      0.00        1     0.00     0.00  Kernel.puts
0.00   312.35      0.00        1     0.00     0.00  Fixnum#to_s
0.00   312.35      0.00        2     0.00     0.00  Module#method_added
0.00   312.35      0.00        1     0.00     0.00  Kernel.require
0.00   312.35      0.00        2     0.00     0.00  IO#write
0.00   312.35      0.00        1     0.00 312350.00  #toplevel