TSabc 発言

かわじ、です。


> 演習問題として、
> 数値を入力すると九九の数式を表示するプログラムを考えてみました。
> 
> ...が、とりあえず適当に作ったので、ちょっと(^^;)効率が悪い気がします。


以下、素人考えなので、もっといい方法があると思うのですが、
とりあえず考えてみましたので、出してみます。


九九位だったら、最初にハッシュテーブルか何か用意しておく、というのが
素直な答えですが、そういう演習問題では無さそうなので、テーブルは用意せず
にその都度計算で解くという前提で、以下のような方法を考えました。

 1) multiply
    その都度、全ての掛け算の組み合わせを調べる（例題と同じ）。
    1 から 81 を調べるのに必要な計算量は、81 * 9 * 9 = 6561 回。

 2) multiply2
    一つの列ごとに（有ったとしても）一つの答えしか存在しないから、
    例えば 2 * 3 が見つかったら、2 * 4, 2 * 5 以降はパスする。
    1 から 81 を調べるのに必要な計算量は、6237 回。（どういう風に回数を
    求めたらいいのかはちょっと分からないので、実際に計測しました）

 3) division
    掛け算したものが合致する、を逆に考えると、割り算して割り切れる、
    ということなので、一つの列に対して割り切れるかどうかを調べる。
    9 * 9 回調べなくても、（片側の列の）9 回で済むので、1 から 81 を調べ
    るのに必要な計算量は、81 * 9 = 729 回（＋割り算やチェックのコスト）。

 4) division2
    2 * 3 == 3 * 2 なので、「掛け算の左側が少ない場合」だけを調べれば、
    結果的に組み合わせの全部の数が分かる。また、例えば 4 を調べるのに、
    5 以上の列を調べる必要はないので、そのような計算も省くと、
    1 から 81 を調べるのに必要な計算量は、532 回。


ということの結果が以下の通りです。マシンは Celeron400, 言語は ruby です。

------------------------------------------------------------------------
$ ruby -v
ruby 1.6.7 (2002-03-01) [i386-openbsd3.1]

$ ruby -w tmp.rb
                 user     system      total        real
multiply:  151.080000   0.000000 151.080000 (151.178019)
multiply2: 145.070000   0.000000 145.070000 (145.396912)
division:   49.750000   0.000000  49.750000 ( 49.806758)
division2:  50.040000   0.000000  50.040000 ( 50.053586)
------------------------------------------------------------------------

(1) に比べ (3) は三分の一程度速くなっているようですが、
(1),(2) と (3),(4) はほとんど違いがないようです。

# 全体的に時間がかかっているのは、うちのマシンがショボイだけなので、
# 気にしないで下さい（インストールしている ruby が古いのも一因かも）。

もっと言語依存の形での最適化や「九九」そのものの構造に依存した最適化は
出来そうですが、とりあえず考えたところはこんな感じです。


以下がソースですが、九九以上の掛け算(10*10など)も扱えるようにしているた
め、かなり冗長です。

------------------------------------------------------------------------
require 'benchmark'

TEST_TIMES      = 5000
TEST_RANGE      = -10..100
TEST_MULTIPLIER = 9
TESTS = %w[multiply multiply2 division division2]

def count_by_multiply(n,m=9)
  result = 0
  if 1 <= n and n <= m ** 2
    1.upto(m){|i|
      1.upto(m){|j|
        if n == i * j
#          puts "#{n}=#{i}*#{j}"
          result += 1
        end
      }
    }
  end
#    puts "#{n} - ?" if cnt.zero?
  return result
end

def count_by_multiply2(n,m=9)
  result = 0
  if 1 <= n and n <= m ** 2
    1.upto(m){|i|
      1.upto(m){|j|
        if n == i * j
#          puts "#{n}=#{i}*#{j}"
          result += 1
          break
        end
      }
    }
  end
#    puts "#{n} - ?" if cnt.zero?
  return result
end

def count_by_division(n,m=9)
  result = 0
  if 1 <= n and n <= m ** 2
    1.upto(m){|i|
      q, r = n.divmod(i)
      if r.zero? and 1 <= q and q <= m
#        puts "#{n}=#{i}*#{q}"
        result += 1
      end
    }
  end
#  puts "#{n} - ?" if cnt.zero?
  return result
end

def count_by_division2(n,m=9)
  result = 0
  if 1 <= n and n <= m ** 2
    1.upto([n,m].min){|i|
      q, r = n.divmod(i)
      break if q < i
      if r.zero? and 1 <= q and q <= m
        if q == i
#          puts "#{n}=#{i}*#{q}"
          result += 1
        else
#          puts "#{n}=#{i}*#{q}"
#          puts "#{n}=#{q}*#{i}"
          result += 2
        end
      end
    }
  end
#  puts "#{n} - ?" if cnt.zero?
  return result
end

Benchmark.bm(11){|x|
  TESTS.each{|method|
    x.report("#{method}:"){
      TEST_TIMES.times{
        TEST_RANGE.each{|i|
          n = __send__("count_by_#{method}", i, TEST_MULTIPLIER)
#          puts "#{i} - #{n} patterns"
        }
      }
    }
  }
}