enbug diary

_ PythonでSICP

何だか気分的に煮詰まってしまったので、 気分転換に SICP の問題でも解いてみる。 C++で解く という強者もいらっしゃるようだが、 私は屁垂れなので、 Python でやってみる。 疲れた時にわざわざ蛇の道を歩むこともなかろう... SICP in other languages にPythonの例もあるみたいだが、 それは見なかったことにする。

Exercise 1.3. 三つ引数を取って、大きい方の二つの数字の自乗の和を求める関数を書け。 これぐらい簡単でないと頭は休まらないよな。

def f(a, b, c):
  l = [a, b, c]
  l.remove(min(l))
  return sum([x * x for x in l])

思わずbrute-forceでやってしまったが、

def f(a, b, c):
  return sum([x * x for x in (max(a, b), max(min(a, b), c))])

これと比べて、速度差なんて出るんだろうか。

Exercise 1.11. n が3未満なら、f(n) = n で、 3以上なら、f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) となる関数を、再帰と繰り返しの両方で書け。

再帰だとそのまんまだ。Pythonは簡単だ。

def f(n):
  if n < 3: return n
  return f(n-1) + 2*f(n-2) + 3*f(n-3)

繰り返し。無意味に generator を使ってみる。

def f(n):
  def g():
    a = []
    while 1:
      l = len(a)
      if l < 3:
        a.insert(0, l)
      else:
        a.insert(0, a[0]+2*a[1]+3*a[2])
        a.pop()
      yield a[0]
  i = g()
  for c in xrange(n - 1):
    i.next()
  return i.next()

全然分かりやすくもならないし、速くもならないな。 ベタで書いた方がマシ。

def f(n):
  if n < 3: return n
  a = [2, 1, 0]
  for i in xrange(n-2):
    a.insert(0, a[0]+2*a[1]+3*a[2])
    a.pop()
  return a[0]

Exercise 1.16. 自乗しまくって、対数ステップ数で指数を計算する関数を繰り返しで書け。

def f(b, n):
  a = 1
  while n:
    if n % 2:
      a *= b
      n -= 1
    else:
      b *= b
      n /= 2
  return a

ヒントそのまんまで書けてしまって、ちっとも面白くない。 だからと言って、これより効率的な方法も思い付かないのがくやしい。

Exercise 1.32. sum とか product を一般化するのに、 accumulator を書け。 再帰と繰り返しの両方で。

繰り返し。

def accumulate(combiner, null_value, term, a, next, b):
  r = null_value
  while a <= b:
    r = combiner(r, term(a))
    a = next(a)
  return r

再帰。

def accumulate_r(combiner, null_value, term, a, next, b):
  if a > b:
    return null_value
  return combiner(term(a), accumelate_r(combiner, null_value, term, next(a), next, b))

当然再利用できる。

def sum(term, a, next, b):
  return accumulate(lambda x, y: x + y, 0, lambda x: x, a, next, b)

def product(term, a, next, b):
  return accumulate(lambda x, y: x * y, 1, lambda x: x, a, next, b)

なんか本当にそのまんまだよな。

Exercise 1.37. k-term finite continued fractionを書け。 再帰と繰り返しの両方で。 これって日本語で何て言うんだっけ？ k次有限連分数？

繰り返し。ケツから行くだけ。

def cont_frac(n, d, k):
  r = 0.0
  for i in xrange(k, 0, -1):
    r = n(i) / (d(i) + r)
  return r

再帰。 うまい手が思い付かなかったので、 中に関数作って、変数を余分に足してしまった。 もうちょっとマシな方法はある？

def cont_frac_r(n, d, k):
  def f(i):
    if k == i:
      return n(k) / d(k)
    else:
      return n(k) / (d(k) + f(i + 1))
  return f(0)

この辺で飽きてしまった。 はっきり言って、Pythonでやると簡単過ぎて、 何のネタにもならないようである。

SICPを見るのって久しぶりだったけれど、 案外これに載っているネタって、 Lispじゃないと意味を為さない部分が多いんだなあ。