Scheme - 非決定性プログラムの例(論理パズル、制限の順序と解、効率性)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田英一 (翻訳)

開発環境

OS X Lion - Apple(OS)
Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
Scheme (プログラミング言語)
MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.3(Scheme の変形 - 非決定性計算)、4.3.2(非決定性プログラムの例)、論理パズル、問題 4.39を解いてみる。

その他参考書籍

Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 4.39

本説の制限の順序の解と、制限の順序を変えた解が異なると仮定する。

ある本節の制限の順序の解(全ての制限が真)が制限の順序を変えた解には含まれない場合、制限の順序を変えたある制限ではその制限が偽になる。全ての制限が真ならば、制限の順序を変えても全ての制限は真になる。

ということで制限が偽かつ真という矛盾が発生。

ある制限の順序を変えた解が本節の制限の解に含まれない場合も同様に矛盾が発生する。

よって、多住居手続きの制限の順序は解に影響しない。

制限の順序を変更しても解に影響がないことが分かったので、制限の順序を変えて効率化することを考えてみる。

多住居手続きの制限の順序は解を見出す時間について。

まず、最初に特殊形式ambでbaker、copper、fletcher、miller、smithの値を取得しているので、requireの前の調べなければならない可能性の数は、制限の順序を変えても変わらない。

制限を並べ替える時、手続きrequireの引数の実行速度が遅いものの調べなければならない可能性の数を小さくなるように並べ替えれば、より速いプログラムになりそう。特に、distinct?は時間がかかりそうだから、なるべくrequireで使われる回数を少ないようにすれば効果的そう。

まず、本節の制限の順序での各制限順に調べなければならない可能性の数を調べてみる。

distinct?は、調べなければならない可能性の数は5^5で、この制限が真になるのは5!。

(not (= baker 5))は、調べなければならない可能性の数は5!で、この制限が真になるのは5! - 4! = 4*4!。

(not (= cooper 1))は、調べなければならない可能性の数は4*4!で、この制限が真になるのは4*4! - 3*3! = 3!*(16 - 3) = 13*3!。

(not (= fletcher 5))は調べなければならない可能性の数は13*3!で、この制限が真になるのは13*3! - 3*3! = 10*3!。

(not (= fletcher 1))は調べなければならない可能性の数は10*3!、この制限が真になるのは10*3! - 3*3! = 7*3!。

(> miller cooper)は調べなければならない可能性の数は7*3!、この制限が真になるのは7*3! - (3*3! + 2*2 + 3 + 2) = 7*3! - 27 = 15。

(not (= (abs (- smith fletcher)) 1))は調べなければならない可能性の数は15、この制限が真になるのは15 - ((2 + 1) + (1 + 1) + (1 + 1)) = 15 - 7 = 8。

(not (= (abs (- fletcher copper)) 1))は調べなければならない可能性の数は8、この制限が真になるのは8 - (2 + (2 + 1) + 2) = 1。

制限の順序を以下のようなコードの順序に変えた場合、本節の制御の順より(require distinct? (list …))が実行される回数が少なくて済む。

コード(BBEdit)

sample.scm

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= flechter 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith flecther)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (require
     (distinct? (list baker cooper fletcher miller smith)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))

まだ、Amb-Eval(amb評価器)の実装が完成してないので、完成したら実際に入力して確認してみることに。

とりあえず、Pythonで、filterを使った場合での速度の違いを計測してみる。

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

import timeit

print('本節　　: {0}'.format(timeit.timeit(
"""
def f1():
    all = [[a,b,c,d,e] for a in range(1, 6) for b in range(1, 6)
                       for c in range(1, 6) for d in range(1, 6) for e in range(1, 6)]
    def f(x):
        for i in range(len(x)):
            for j in range(i + 1, len(x)):
                if x[i] == x[j]:
                    return False
        return True
    all = filter(f, all)
    all = filter(lambda x: x[0] != 5, all)
    all = filter(lambda x: x[1] != 1, all)
    all = filter(lambda x: x[2] != 1, all)
    all = filter(lambda x: x[2] != 5, all)
    all = filter(lambda x: x[3]  x[1], all)
    all = filter(lambda x: abs(x[4] - x[2]) != 1, all)
    all = list(filter(lambda x: abs(x[1] - x[2]) != 1, all))
    return all
result = f1()
"""
, number=100)))

print('並び替え: {0}'.format(timeit.timeit(
"""
def f2():
    all = [[a,b,c,d,e] for a in range(1, 6) for b in range(1, 6)
                       for c in range(1, 6) for d in range(1, 6) for e in range(1, 6)]
    def f(x):
        for i in range(len(x)):
            for j in range(i + 1, len(x)):
                if x[i] == x[j]:
                    return False
        return True
    all = filter(lambda x: x[0] != 5, all)
    all = filter(lambda x: x[1] != 1, all)
    all = filter(lambda x: x[2] != 1, all)
    all = filter(lambda x: x[2] != 5, all)
    all = filter(lambda x: x[3]  x[1], all)
    all = filter(lambda x: abs(x[4] - x[2]) != 1, all)
    all = filter(lambda x: abs(x[1] - x[2]) != 1, all)
    all = list(filter(f, all))
    return all
result = f2()
"""
, number=100)))

入出力結果(Terminal)

$ ./sample.py
本節　　: 3.3797409939579666
並び替え: 1.6425217320211232
$

Pythonでfilterの順序を入れ替えることによりプログラムの実行速度が速くなったことを確認できた。

Kamimura's blog

ほしい物リスト

2013年10月1日火曜日

Scheme - 非決定性プログラムの例(論理パズル、制限の順序と解、効率性)

0 コメント:

コメントを投稿