Prolog でコードをたびたび書いてはいますが、実用的なプログラムを Prolog で書けたためしがないというのが正直なところです。使い所がつかめていないのがその原因。
今もまだつかめているわけではないのですが、Prolog ならば自然に表現できて簡単に解ける例に遭遇して、そのような問題に適用すればよいのだということに気づかされました。残る課題はそのような問題であることを見極める自身の技量なわけですが。
矩形を見つける問題
実例として見つけた問題というのが、「どう書く」で出題された中にある矩形を求める部分。
XY平面上にある複数の点のうち、矩形の頂点の位置なる 4 点 {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} を見つけるというもの。
Prolog で愚直に書いた
実際に矩形探しをさせてみます。x, y とも 10〜40 の値からなり重複しない点 200 個を用意して実験。
points([ [18, 34], [32, 14], [21, 23], [24, 29], [37, 20], [40, 28], [16, 30], [13, 33], [40, 37], [28, 23], [30, 38], [23, 37], [29, 20], [34, 14], [25, 26], [12, 27], [10, 19], [30, 18], [13, 26], [18, 13], [10, 32], [13, 16], [15, 19], [17, 14], [38, 30], [36, 22], [22, 38], [18, 22], [29, 12], [17, 36], [20, 25], [27, 21], [21, 37], [33, 14], [28, 15], [15, 20], [37, 31], [37, 27], [20, 27], [24, 12], [18, 21], [32, 19], [33, 19], [27, 18], [32, 39], [10, 36], [37, 19], [28, 16], [32, 32], [31, 12], [36, 14], [19, 33], [15, 28], [35, 23], [27, 17], [26, 27], [22, 34], [24, 18], [13, 12], [31, 30], [28, 14], [24, 31], [31, 25], [33, 23], [29, 16], [20, 35], [13, 35], [30, 40], [36, 25], [35, 25], [11, 19], [26, 17], [37, 28], [10, 25], [20, 22], [35, 31], [20, 17], [31, 32], [33, 33], [35, 40], [37, 22], [39, 40], [31, 21], [38, 29], [17, 34], [38, 13], [35, 24], [21, 38], [24, 39], [29, 30], [35, 22], [25, 37], [14, 15], [13, 18], [17, 30], [24, 30], [12, 23], [10, 21], [33, 21], [13, 21], [32, 28], [26, 31], [27, 31], [23, 11], [14, 21], [33, 34], [12, 28], [30, 16], [12, 18], [28, 25], [23, 36], [10, 35], [27, 36], [15, 17], [37, 10], [37, 15], [24, 36], [26, 10], [11, 11], [23, 23], [24, 14], [13, 10], [37, 24], [32, 30], [14, 26], [24, 25], [29, 39], [26, 18], [13, 20], [24, 28], [11, 22], [16, 16], [27, 35], [16, 14], [15, 12], [17, 28], [25, 19], [33, 16], [24, 27], [32, 20], [16, 18], [19, 17], [39, 12], [18, 27], [27, 15], [15, 27], [20, 15], [12, 20], [15, 16], [37, 33], [33, 20], [12, 33], [16, 10], [22, 37], [24, 15], [13, 38], [37, 25], [17, 12], [18, 35], [29, 27], [29, 24], [32, 13], [13, 31], [16, 39], [20, 14], [32, 38], [25, 17], [35, 15], [28, 21], [23, 39], [34, 24], [17, 26], [32, 10], [33, 28], [13, 24], [29, 29], [28, 17], [14, 39], [20, 18], [13, 27], [40, 20], [11, 14], [22, 18], [28, 13], [32, 12], [37, 40], [11, 37], [25, 35], [11, 31], [18, 16], [19, 24], [29, 37], [34, 31], [26, 19], [34, 11], [37, 29], [20, 37], [24, 38], [35, 32], [30, 26] ]). rect(X1, Y1, X2, Y2) :- points(PS), member([X1, Y1], PS), member([X1, Y2], PS), member([X2, Y1], PS), member([X2, Y2], PS), X1 < X2, Y1 < Y2. rects(RS) :- findall([[X1, Y1], [X1, Y2], [X2, Y1], [X2, Y2]], rect(X1, Y1, X2, Y2), RS). main :- rects(RS), length(RS, L), format("~p~n~d~n", [RS, L]).
実行。
$ time gprolog --consult-file rect.pro --entry-goal 'main, halt' [[[32,14],[32,19],[33,14],[33,19]], ... (略) ... ,[[24,38],[24,39],[32,38],[32,39]]] 450 real 0m0.351s user 0m0.322s sys 0m0.023s
すぐに答えが表示されたのには、正直驚きました。
Ruby で愚直に書く
任意の 4 点を取得して、矩形の頂点になるものを選べばよいというのなら、combination で 4 点を選び条件に合うものを選べばよいだろうと、愚直に書き直したものです。
200 個の点は同じ値です。
def points [ [18, 34], [32, 14], [21, 23], [24, 29], [37, 20], [40, 28], [16, 30], [13, 33], [40, 37], [28, 23], [30, 38], [23, 37], [29, 20], [34, 14], [25, 26], [12, 27], [10, 19], [30, 18], [13, 26], [18, 13], [10, 32], [13, 16], [15, 19], [17, 14], [38, 30], [36, 22], [22, 38], [18, 22], [29, 12], [17, 36], [20, 25], [27, 21], [21, 37], [33, 14], [28, 15], [15, 20], [37, 31], [37, 27], [20, 27], [24, 12], [18, 21], [32, 19], [33, 19], [27, 18], [32, 39], [10, 36], [37, 19], [28, 16], [32, 32], [31, 12], [36, 14], [19, 33], [15, 28], [35, 23], [27, 17], [26, 27], [22, 34], [24, 18], [13, 12], [31, 30], [28, 14], [24, 31], [31, 25], [33, 23], [29, 16], [20, 35], [13, 35], [30, 40], [36, 25], [35, 25], [11, 19], [26, 17], [37, 28], [10, 25], [20, 22], [35, 31], [20, 17], [31, 32], [33, 33], [35, 40], [37, 22], [39, 40], [31, 21], [38, 29], [17, 34], [38, 13], [35, 24], [21, 38], [24, 39], [29, 30], [35, 22], [25, 37], [14, 15], [13, 18], [17, 30], [24, 30], [12, 23], [10, 21], [33, 21], [13, 21], [32, 28], [26, 31], [27, 31], [23, 11], [14, 21], [33, 34], [12, 28], [30, 16], [12, 18], [28, 25], [23, 36], [10, 35], [27, 36], [15, 17], [37, 10], [37, 15], [24, 36], [26, 10], [11, 11], [23, 23], [24, 14], [13, 10], [37, 24], [32, 30], [14, 26], [24, 25], [29, 39], [26, 18], [13, 20], [24, 28], [11, 22], [16, 16], [27, 35], [16, 14], [15, 12], [17, 28], [25, 19], [33, 16], [24, 27], [32, 20], [16, 18], [19, 17], [39, 12], [18, 27], [27, 15], [15, 27], [20, 15], [12, 20], [15, 16], [37, 33], [33, 20], [12, 33], [16, 10], [22, 37], [24, 15], [13, 38], [37, 25], [17, 12], [18, 35], [29, 27], [29, 24], [32, 13], [13, 31], [16, 39], [20, 14], [32, 38], [25, 17], [35, 15], [28, 21], [23, 39], [34, 24], [17, 26], [32, 10], [33, 28], [13, 24], [29, 29], [28, 17], [14, 39], [20, 18], [13, 27], [40, 20], [11, 14], [22, 18], [28, 13], [32, 12], [37, 40], [11, 37], [25, 35], [11, 31], [18, 16], [19, 24], [29, 37], [34, 31], [26, 19], [34, 11], [37, 29], [20, 37], [24, 38], [35, 32], [30, 26] ] end def rects points.sort.combination(4).select {|p1, p2, p3, p4| p1[0] == p2[0] && p1[1] == p3[1] && p3[0] == p4[0] && p2[1] == p4[1] } end rs = rects puts rs.to_s puts rs.size
実行。
$ time ruby rect1.rb [[[10, 19], [10, 21], [33, 19], [33, 21]], ... (略) ... , [[37, 20], [37, 28], [40, 20], [40, 28]]] 450 real 0m22.360s user 0m21.820s sys 0m0.187s
それほど速くはないだろうと思いつつも、これほど数字になるとは思っていなかったので結構驚きでした。
Ruby で工夫して書く
当然、工夫すれば速くなります。
def points [ # 上記と同じなので省略 ] end def rects points.group_by {|_, y| y } .map {|y, ps| [y, ps.map(&:first).sort] } .combination(2) .map {|(y1, xs1), (y2, xs2)| (xs1 & xs2).combination(2).map {|x1, x2| [[x1, y1], [x1, y2], [x2, y1], [x2, y2]] } }.reject(&:empty?).flatten(1) end rs = rects puts rs.to_s puts rs.size
実行。
$ time ruby rect2.rb [[[17, 34], [17, 14], [33, 34], [33, 14]], ... (略) ... , [[13, 24], [13, 10], [37, 24], [37, 10]]] 450 real 0m0.121s user 0m0.074s sys 0m0.041s
ずいぶん速くなります。しかし Prolog で愚直に書いた場合もこれの数倍程度の時間しかかからないということは、やはり驚きです。
いつか読むはずっと読まない：付き従う正義、付き従う剣、付き従う慈
2冊目の中間、ちょっど真ん中あたりを読んでいます。半分まで読み進めてみても「異質な感じ」が終わりません。
正直最初のうちは得体の知れない感じが苦痛に感じる時もありましたが、進むにつれその感じにのめり込んでいることに気がつかされます。
- 作者: アン・レッキー,鈴木康士,渡邊利道,赤尾秀子
- 出版社/メーカー: 東京創元社
- 発売日: 2015/11/21
- メディア: 文庫
- この商品を含むブログ (15件) を見る
- 作者: アン・レッキー,鈴木康士,大野万紀,赤尾秀子
- 出版社/メーカー: 東京創元社
- 発売日: 2016/04/21
- メディア: 文庫
- この商品を含むブログ (6件) を見る
- 作者: アン・レッキー,鈴木康士,赤尾秀子
- 出版社/メーカー: 東京創元社
- 発売日: 2016/10/31
- メディア: 文庫
- この商品を含むブログ (5件) を見る
