sumim #3166(2007/09/25 10:38 GMT) [ Smalltalk ] Rating2/2=1.00
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
!SequenceableCollection methodsFor: 'doukaku63'! genCond: perm using: memo on: stream self ifEmpty: [ stream nextPut: ${. perm do: [:var | stream nextPut: var] separatedBy: [stream nextPut: $.]. stream nextPut: $}. ^self]. perm ifEmpty: [^self allButFirst genCond: (self first: 1), memo using: '' on: stream]. stream nextPutAll: ('{1}<{2} ifTrue:[' format: {perm last. self first}). self allButFirst genCond: perm, (self first: 1), memo using: '' on: stream. stream nextPutAll: ']ifFalse:['. self genCond: perm allButLast using: (perm last: 1), memo on: stream. stream nextPutAll: ']'! ! !UndefinedObject methodsFor: 'doukaku63'! genSort: n | vars code | vars := ($a to: $z) first: n. code := FileStream forceNewFileNamed: 'sort.st'. code nextPutAll: '!!UndefinedObject methodsFor: ''doukaku63''!!'; cr. code nextPutAll: 'doukakuSort'; cr. code nextPutAll: '| in result '. vars do: [:var | code nextPut: var; space]. code nextPutAll: '|'; cr. code nextPutAll: 'in := FileStream fileNamed: ''in.txt''.'; cr. vars do: [:var | code nextPut: var; nextPutAll: ' := in nextLine asNumber.'; cr]. code nextPutAll: 'World findATranscript: nil.'; cr. code nextPutAll: 'result := '. vars genCond: '' using: '' on: code. code nextPutAll: '.'; cr. code nextPutAll: 'Transcript cr; show: result!! !!'. code close! ! | file | file := FileStream newFileNamed: 'io.txt'. (1 to: 10) asArray shuffled do: [:each | file nextPutAll: each printString; cr]. file close. { #generate -> [nil genSort: 4] timeToRun. #compile -> [(FileStream fileNamed: 'sort.st') fileIn] timeToRun. #perform -> [nil perform: #doukakuSort] timeToRun}
Rating2/2=1.00-0+
[ reply ]
sumim
#3166()
[
Smalltalk
]
Rating2/2=1.00
条件文の生成は、考えているうちに頭が痛くなってきたので自力解決は断念して shiro さんのを参考にさせていただきました。どうかお許しを。あと、残念ながら Squeak Smalltalk のバイトコードにおける仕様上の制約（1 KB 以上のジャンプができない…）から n = 5 以上では生成コードは、コンパイラにはじかれてしまうようです。
仕方がないのでコードの生成のみの測定（単位はミリ秒）の結果を。
(1 to: 9) collect: [:n | n -> [nil genSort: n] timeToRun]
"=> {1->11 . 2->8 . 3->12 . 4->29 . 5->151 . 6->720 . 7->4682 . 8->38510 . 9->362363}"
n = 9 で６分強、出力コードのファイルサイズは 14.5 MB でした（1 GHz PowerPC - OS X）。n = 10 は怖くて試していません(^_^;)。
!SequenceableCollection methodsFor: 'doukaku63'! genCond: perm using: memo on: stream self ifEmpty: [ stream nextPut: ${. perm do: [:var | stream nextPut: var] separatedBy: [stream nextPut: $.]. stream nextPut: $}. ^self]. perm ifEmpty: [^self allButFirst genCond: (self first: 1), memo using: '' on: stream]. stream nextPutAll: ('{1}<{2} ifTrue:[' format: {perm last. self first}). self allButFirst genCond: perm, (self first: 1), memo using: '' on: stream. stream nextPutAll: ']ifFalse:['. self genCond: perm allButLast using: (perm last: 1), memo on: stream. stream nextPutAll: ']'! ! !UndefinedObject methodsFor: 'doukaku63'! genSort: n | vars code | vars := ($a to: $z) first: n. code := FileStream forceNewFileNamed: 'sort.st'. code nextPutAll: '!!UndefinedObject methodsFor: ''doukaku63''!!'; cr. code nextPutAll: 'doukakuSort'; cr. code nextPutAll: '| in result '. vars do: [:var | code nextPut: var; space]. code nextPutAll: '|'; cr. code nextPutAll: 'in := FileStream fileNamed: ''in.txt''.'; cr. vars do: [:var | code nextPut: var; nextPutAll: ' := in nextLine asNumber.'; cr]. code nextPutAll: 'World findATranscript: nil.'; cr. code nextPutAll: 'result := '. vars genCond: '' using: '' on: code. code nextPutAll: '.'; cr. code nextPutAll: 'Transcript cr; show: result!! !!'. code close! ! | file | file := FileStream newFileNamed: 'io.txt'. (1 to: 10) asArray shuffled do: [:each | file nextPutAll: each printString; cr]. file close. { #generate -> [nil genSort: 4] timeToRun. #compile -> [(FileStream fileNamed: 'sort.st') fileIn] timeToRun. #perform -> [nil perform: #doukakuSort] timeToRun}Rating2/2=1.00-0+
[ reply ]