Smalltalkのtは小文字です

id:sumim:about

オブジェクト指向の“モヤッと”の正体を知りたくなったら、id:sumim:20080415:p1id:sumim:20040525:p1 がお役に立つかも…。


 

2014-09-10

[] 久しぶりに竹内関数で JavaScript、PythonRubySchemeSmalltalk とを戦わせてみる



AO bench で味を占めたので。


今回は上のリンク先の結果と対比できるように tarai(y を返す)ではなく tak(z を返す)で tak(20, 10, 0) を手元の環境(Intel Core i7-4650U @1.7GHz/2.3GHz、Win8.1 64-bit)で計測してみました。インストールの手間もあって、必ずしも最新バージョンをそろえられなかったのはご容赦ください。



 言語  処理系  結果 
 Smalltalk  Squeak 4.5 CogVM  1.33 sec 
   Squeak 4.5 SpurVM  1.19 sec 
   Squeak 4.3 CogVM  0.741 sec 
   VisualWorks 7.10.1nc  3.87 sec 
   Dolphin Smalltalk X6 (6.0.3ce)  3.45 sec 
   GNU Smalltalk 3.1  14.1 sec 
 Python  Python 3.2.5  11.4 sec 
 Ruby  Ruby 2.2.0dev  4.52 sec 
 Scheme  Gauche 0.9.5_pre1  3.27 sec 
 JavaScript  Node.js 0.10.31  0.486 sec 
 C  gcc 4.8.3  0.217 sec 

いつの間にか VisualWorks より爆速になった Squeak(CogVM)は安定の結果ですが、その中でも AO bench で威力を発揮した SpurVM が期待したほどではなかったのが残念だったのに対し、思わぬ伏兵として Squeak 4.3 の古い CogVM が意外な好成績をたたき出したのが興味深いところです。Dolphin Smalltalk も入れたのでついでに計ってみたのですが、古い処理系のわりに健闘しています。

他言語では、JavaScript の V8エンジンが相変わらずバカっぱやいですね。勝てる気がしません。



Smalltalk で使用したコード(共通)

| tak res |
tak := nil.
tak := [:x :y :z |
   x <= y ifTrue: [z] ifFalse: [
      tak
         value: (tak value: x-1 value: y value: z)
         value: (tak value: y-1 value: z value: x)
         value: (tak value: z-1 value: x value: y)
   ]
].

(Time millisecondsToRun: [res := tak value: 20 value: 10 value: 0]) -> res


その他の言語のコードと出力

$ python3 -V
Python 3.2.5

$ python3 tak.py
11.36166000366211 1

$ cat tak.py
from time import time

def tak(x, y, z):
    if x <= y: return z
    return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) )

start = time()
res = tak(20, 10, 0)
print( time() - start, res )
$ ruby -v tak.rb
ruby 2.2.0dev (2014-08-26 trunk 47287) [x86_64-cygwin]
1
4.52072

$ cat tak.rb
def tak(x, y, z)
  if x <= y then
    z
  else
    tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y))
  end
end

start = Time.now
puts tak(20, 10, 0)
puts Time.now - start
$  gosh -V
Gauche scheme shell, version 0.9.5_pre1 [utf-8,pthreads], x86_64-unknown-cygwin

$ gosh tak.scm
;(time (display (tak 20 10 0)))
; real   3.274
; user   3.265
; sys    0.000
1

$ cat tak.scm
(define (tak x y z)
   (if (<= x y) z
     (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))

(time (display (tak 20 10 0)))
$ node -v
v0.10.31

$ node tak.js
486 1

$ cat tak.js
function tak(x, y, z){
   if(x <= y){ return z; }
   return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) );
}

var start = (new Date()).getTime();
var res = tak(20, 10, 0);
console.log((new Date()).getTime() - start, res)
$ gcc --version
gcc (GCC) 4.8.3
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


$ cat tak.c
#include <stdio.h>

int tak(int x, int y, int z){
   if (x <= y){
      return z;
   } else {
      return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) );
   }
}

int main(void){
   printf("%d\n", tak(20, 10, 0));
   return 0;
}

$ gcc -O3 tak.c -o tak_O3

$ time ./tak_O3
1

real    0m0.217s
user    0m0.171s
sys     0m0.015s

2014-08-26

[] ひさしぶりに AO bench を試したら Squeak/Pharo が(少しだけど 圧倒的に)VisualWorks より速くなっていたでござるの巻



Island Life - Gaucheでaobench再び に触発されて、マシンも処理系も前回から刷新されたことだしと試してみました。コードはいろいろとひどいのであらためて書き下ろしたい気持ちもありましたが、へんに Smalltalk っぽく書き換えたところで遅くなるだけなので、前回のまま使いました。使用したマシンのスペックは Intel Core i7-4650U @ 1.7GHz/2.30GHz、Win 8.1 (64 bit)です。


 処理系   時間 
 VisualWorks 7.10.1 (64 bit)  34 sec 
 Pharo 3.0 / Cog JIT VM  27 sec 
 Squeak 4.5 / Cog JIT VM  26 sec 
 Squeak 4.5 (trunk46-spur.image) / Cog Spur JIT VM  13.5 sec 
 Squeak 4.3 / Cog JIT VM  37 sec 
 Squeak 4.3 / 旧 非JIT VM  114 sec 
 Ruby 2.1.2  64 sec
 C  1.7 sec 

ざっと C の 15倍遅いくらいでしょうか。Cog VM おそるべし。


[追記] …と思ったら、id:squeaker さん情報によれば Cog VM はさらに進化しているらしく、最新の Spur というバージョンを使うと C の 8倍程度の遅さをたたき出したのでありました。すばらしい。


Cog Spur VM とそれに対応した仮想イメージは、こちらから入手可能です。

[追記ここまで]


参考まで Gauche-0.9.5_pre1 は GAUCHE_AVAILABLE_PROCESSORS = 1 で 54s 、この制約をつけないでコア全部使うと 29s でした(cygwin64 環境。前後しますが Ruby、C も同じ)。


あと、Gauche は 0.9.4 も 0.9.5_pre1 も cygwin64 では現状なぜか gc のあたりでビルドに失敗するので(trunk にはパッチが当たっているはずなのですが…)、C はよくわからないながらもエラーから判断して ./gc/include/gc.h の _data_start__ をのたぐいを __data_start__ に書き換えて無理矢理とおしたのを使っています(下はそのときのエラー)。

main.o:main.c:(.rdata$.refptr._bss_start__[.refptr._bss_start__]+0x0): `_bss_start__' に対する定義されていない参照です
main.o:main.c:(.rdata$.refptr._data_start__[.refptr._data_start__]+0x0): `_data_start__' に対する定義されていない参照です
main.o:main.c:(.rdata$.refptr._bss_end__[.refptr._bss_end__]+0x0): `_bss_end__' に対する定義されていない参照です
main.o:main.c:(.rdata$.refptr._data_end__[.refptr._data_end__]+0x0): `_data_end__' に対する定義されていない参照です
collect2: エラー: ld はステータス 1 で終了しました

2014-08-06

[] 九州の七つの県を三色で塗り分ける問題を Squeak Smalltalk



688 :デフォルトの名無しさん:2014/08/03(日) 16:21:36.50 ID:vVRF2pWw
お題:九州の七つの県を三色で塗り分ける。

プログラミングのお題スレ Part4

| 九州 配色 状態 待行列 |
九州 := {
   #福岡 -> #(佐賀 熊本 大分).
   #佐賀 -> #(福岡 長崎).
   #長崎 -> #(佐賀).
   #大分 -> #(福岡 熊本 宮崎).
   #熊本 -> #(福岡 大分 宮崎 鹿児島).
   #宮崎 -> #(大分 熊本 鹿児島).
   #鹿児島 -> #(熊本 宮崎)
}.

配色 := 九州 inject: Dictionary new into: [:辞書 :kv | 辞書 at: kv key put: #(赤 青 黄) asOrderedCollection; yourself].
配色 at: #福岡 put: #(赤) asOrderedCollection.
状態 := 九州 collect: [:kv | kv key -> (配色 at: kv key) -> (kv value collect: [:val | 配色 at: val])].
待行列 := OrderedCollection with: 状態.
[待行列 notEmpty] whileTrue: [
   | 県と候補色群 |
   状態 := 待行列 removeFirst.
   配色 := 状態 collect: #key.
   県と候補色群 := 配色 detect: [:kv | kv value size > 1] ifNone: [^配色 collect: [:kv | kv value: kv value first; yourself]].
   県と候補色群 value do: [:候補色 |
      | 次状態 |
      次状態 := 状態 veryDeepCopy.
      (次状態 detect: [:kv | kv key key == 県と候補色群 key]) key value removeAllSuchThat: [:val | val ~= 候補色].
      次状態 do: [:kv | kv key value size = 1 ifTrue: [kv value do: [:vals | vals removeAllFoundIn: kv key value]]].
      (次状態 noneSatisfy: [:kv | kv key value isEmpty]) ifTrue: [待行列 add: 次状態]]
]
=> {#'福岡'->#'赤' . #'佐賀'->#'青' . #'長崎'->#'赤' . #'大分'->#'青' . #'熊本'->#'黄' . #'宮崎'->#'赤' . #'鹿児島'->#'青'} 

読み下すとき、kv のキーが何で対応する値がなんなのかわからずピンとこないのでイマイチ。

2014-07-29

[] Coffee Time Challenges, Q13 How many を Squeak Smalltalk



ときどきの雑記帖″ 2014年7月(下旬) 経由で。(ネタバレ注意)


13) How many

Challenge: ABCDEFGHIJ is a ten-digit-number. All of the digits are distinct. If 11111 divides it evenly, how many possibilities are there for ABCDEFGHIJ?

Coffee Time Challenges

方針は合っているはずなので、あとはスタート値に注意ですね。

((1023456789 roundTo: 11111) to: 9876543210 by: 11111) count: [:each | each asString asSet size = 10]  "=> 3456 "

2014-05-27

[] Squeak Smalltalk で 配列を交互に分配




Squeak Smalltalk でならどう書くかなぁ…と、いろいろ考えてみたのですが、いまひとつしっくりくるものがないので、いくつか思いついた書き方をざっくばらんに晒しておきます。


お題は、#(x0 y0 x1 y1 x2 y2) を #( (x0 x1 x2) (y0 y1 y2) ) のように分配してまとめるというもの(元はリストなのですが Smalltalk なので配列に読み替えます)。


オーソドックスに #( (x0 y0) (x1 y1) (x2 y2) ) という中間生成物を介して作る方法だとこう書けます。

(#(x0 y0 x1 y1 x2 y2) groupsOf: 2 atATimeCollect: [:pair | pair])
   inject: #(() ()) into: [:sum :each |
      sum with: each collect: [:a :b | a, {b}]]  "=> #((x0 x1 x2) (y0 y1 y2)) "

こういうときは、入れ子の配列を二次元配列に見立てて、行と列を入れ替える #transpose とか #transposed みたいな節操のないメソッドが欲しくなります。

SequenceableCollection >> transposed
   | colns |
   colns := (self species new: self first size) collect: [:idx | self first species new].
   self do: [:each | colns := colns with: each collect: [:coln :elem | coln copyWith: elem]].
   ^colns
#('abc' 'def') transposed  "=> #('ad' 'be' 'cf') "
(#(x0 y0 x1 y1 x2 y2) groupsOf: 2 atATimeCollect: [:xs | xs]) transposed  "=> #((x0 x1 x2) (y0 y1 y2)) "

余談ですが、ここで引数を返すだけのブロック(無名関数)である [:xs | xs] をシンボル #yourself に置き換えられないのは、メソッド #groupsOf:atATimeCollect: が第二引数(通常はブロック)に対して numArgs をして 1 かそれ以外で条件分岐をしているというありがた迷惑な実装のためです。

SequenceableCollection  >> groupsOf: n atATimeCollect: aBlock 
   | passArray |
   passArray := aBlock numArgs = 1.
   ^(n to: self size by: n)
      collect: [:index | 
         | args |
         args := (self copyFrom: index - n + 1 to: index) asArray.
         passArray
            ifTrue: [aBlock value: args]
            ifFalse: [aBlock valueWithArguments: args]]

このため、ブロックはグループを配列としてまるごとを受け取る処理も、その要素を個別にブロック引数に受け取る処理としても書けるようになっていて便利ではあるのですが、あいにくブロックの代わりにシンボルを渡すと破綻します(なお、エラーにならないことからわかるようにシンボルも numArgs への応答はできているので、破綻しないように細工することは簡単です)。個人的にはこういう一見便利そうなカラクリにはなるほどっ!と思うよりはイラッ!とさせられることのほうが多いです。


ありがた迷惑といえば、最近の String>>#, の実装もそうで、引数を asString するようになってしまったため、文字列以外の物を文字列として結合するのには便利なのですが、

'abc', 123 "=> 'abc123' "

しかし、バイト列に見立てた配列を連結するとか以前の実装に依存したちょっと変態的なコードを書こうとしたときにそれが妨げられて脱力します。まあ難しいところです。

'abc', #(65 66 67)  "=> 'abc#(65 66 67)'。'abcABC' を期待 "

閑話休題。


Smalltalk の配列は要素の追加ができませんが、OrderedCollection や WriteStream のインスタンスを使えば破壊的に順次追加する処理を書け、さらに #atWrap: を使ってひとひねりできます。

| colns |
colns := #(() ()) collect: #asOrderedCollection.
#(x0 y0 x1 y1 x2 y2) doWithIndex: [:each :idx | (colns atWrap: idx) add: each].
^colns collect: #asArray  "=> #((x0 x1 x2) (y0 y1 y2)) "
| strms |
strms := #(() ()) collect: #writeStream.
#(x0 y0 x1 y1 x2 y2) doWithIndex: [:each :idx | (strms atWrap: idx) nextPut: each].
^strms collect: #contents  "=> #((x0 x1 x2) (y0 y1 y2)) "

もうひとひねりして、追加先のコレクションやストリームをローテートする書き方もできますが、これはちょっとやり過ぎでしょうね。^^;

| colns |
colns := #(() ()) asOrderedCollection collect: #asOrderedCollection.
#(x0 y0 x1 y1 x2 y2) do: [:each | (colns add: colns removeFirst) add: each].
^colns asArray collect: #asArray  "=> #((x0 x1 x2) (y0 y1 y2)) "

と、いいつつさらに悪のり。

| strm colns |
strm := #(x0 y0 x1 y1 x2 y2) readStream.
colns := #(() ()) asOrderedCollection collect: #asOrderedCollection.
[strm atEnd] whileFalse: [(colns add: colns removeFirst) add: strm next].
^colns asArray collect: #asArray  "=> #((x0 x1 x2) (y0 y1 y2)) "

目先を変えて Matrix のインスタンスを使う手もあります。が、Array2D の代替として導入されたわりに、いまいち頼りにならない Matrix のことなので、これを使って書ける処理もそれなりです。

| mat |
mat := Matrix rows: 3 columns: 2 contents: #(x0 y0 x1 y1 x2 y2).
^(1 to: mat columnCount) collect: [:idx | mat atColumn: idx]   "=> #((x0 x1 x2) (y0 y1 y2)) "

総じて、スマートに書くことができず残念な結果に終わりましたが、いろいろと考えたり考えさせられたりして楽しかったのでよしとしましょう。

 
2004 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 10 | 12 |
2013 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 11 | 12 |
2014 | 01 | 02 | 05 | 07 | 08 | 09 |

最近のコメント

1. 08/26 sumim
2. 08/26 squeaker
3. 08/07 sumim
4. 08/07 squeaker
5. 06/26 squeaker

最近のトラックバック

1. 01/30 no_orz_no_life - Erlangとジャンケン
2. 12/31 檜山正幸のキマイラ飼育記 - J言語、だってぇー?
3. 09/04 Twitter / @atsushifx
4. 07/06 みねこあ - オブジェクト指向 と FizzBuzz
5. 08/07 大島芳樹のカリフォルニア日記 - ランダムな文字列の中に隠された...

この日記のはてなブックマーク数
1321392