Greenroom? 249421

検索：

臨時すれ：　部分和下書

1：_Kyle(1291004) :

2010/05/22 (Sat) 22:58:36

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274865324.png 「Excelの限界に挑戦」シリーズその２　(違

全部そうですがw　これも正真正銘チラシの裏です、念のため。

------------------------

回答するたびに毎回スクラッチから書いて
【そのたびに】なにかしらしくじるというのもいい加減芸がありませんし、
ときどき検索で跳んできて「遭難」しちゃう方がいらっしゃるようなので
「部分和まとめ」的なものを作ろう…と思ったのですが

大方の予想通り

　りふぁくたりんぐ　⇒　動作てすと　⇒　でばぐ　⇒　べんちまーくてすと　⇒
　りふぁくたりんぐ　⇒　動作てすと　⇒　でばぐ　⇒　…

という無限ループに陥って収拾がつかなくなりました　orz

おまけに「段階追って騙ろう」なんて無謀なこと思ったもんだから
各バージョンごとにそれぞれバージョン管理が要るという…　orz

------------------------

手元がいい加減ごちゃごちゃしちゃって、気力が萎えつつあるので
とりあえず「ある程度固まってる」部分から順次上げて行こうと思います。

突っ込み・ダメ出し【大歓迎】ですが
「あ、ソレはver.X.XXで解決済みデス」
みたいなことはあるかも。

落ち着いたらあらためてまとめる予定…です、一応。

------------------------

テーマがテーマなんで、べんちまーくに時間喰われるんですよね。

バージョンごとの性能差も激しいので
課題を重くすると、下位バージョンだと宇宙が消滅するまで終わらないし
課題を軽くすると、上位バージョンだと一瞬で片付くので数字取れないし…。

まぁ「算盤と電卓の性能比較」みたいなハナシで
そもそも較べるのが無茶なんですが、なぜか算盤の方を奨めるような人もいますし(ーー;)

------------------------

回答でコード書くときは
　「やっつけでも、ぐだぐだなスパゲッティでも、素人マクロでも、【解決しないよりはマシ】だろ、たぶん」
なスタンスですし、

実務でコード書くときは
　「とりあえず当座動けばいいや。どうせ余技だし、どうせサービス残(ry」
なスタンスなので、

適当なところで「えいやっ」と区切りつけて「Exit Do」するんですが
いざ時間掛けて「ちゃんと」書こうとするといつまでたっても完成しないという
素人ぷろぐらまに実にアリガチな……　orz

------------------------

なお、上で「りふぁくたりんぐ」とか「べんちまーくてすと」とか言ってるのは
無論【 冗談 】です。そういうレベルのハナシぢゃありませんw

------------------------

おっと、動作仕様書くの忘れてた(ぉ

どのコードも基本的に、アクティブシートの

　・A1セルに目標値
　・B1セル以下に要素

を入力して起動すると

　・A2セルに発見した解の個数
　・C列以降に解

を書き出します。

初期処理でC列以降をクリアするので注意。
120：_Kyle(1291004) :

2012/09/16 (Sun) 00:37:06

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347723805.gif D&Cは、
（ワークシート上でやるには）手数多くなりすぎ。
アルゴリズム的には単純なハナシだし
計算負担も見た目ほど大きくはないんだけど、埋め負担がね。

VBA使わずに、どうしても数式でやりたいなら
やっぱDPか総当りやね。

　※　[反復計算]は守備範囲外なのでパス

「反転」する前提で、
・要素数が少なく目標値が大きい場合には、総当り
・要素数が多く、目標値が小さい場合には、DP
・要素数が多く、目標値も大きい場合には、…ごめんなさい　<(_ _)>
でFA?

まぁ、
一口に「DP」と言っても色々なように
一口に「総当り」といっても色々だけどね。

------------------------------------------
ところで、今更だけど、Excel2003と2007で、
再計算のタイミングが随分違うのね　(ーー;)
119：_Kyle(1291004) :

2012/09/15 (Sat) 23:51:32

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347721548.png 動的計画法でやれるなら…ってことで。

　#　てこずったけど…　orz

課題Ａ(要素数30)の場合、ver.5.80のループ回数が４万程度なので
がっちり枝刈ればワークシート上ですべての解を出すこともできるよね、ってハナシ。

　#　すごくてこずったけど…　o.....rz

　#　で、てこずればてこずるほど、テキストが長くなるという…　o........rz
　#　フィルとか再計算とか削除とか再起動とか(w
　#　待ってる時間が退屈なのよね。

=============================================
■お約束♪

　【　総当りではありません　】

って、一応書いとかないとね。

「要素30の組合せは2^30で、十億以上になります。
　Excel2007の行数は百万ちょっとですから解けるわけありません。
　十億と百万、どっちが大きいか、わかります？？？
　小学生でもわかりますよ　wwwwww」

とか、読まずにダメ出しする人いるから。

　#　きみ、前回もまったく同じこと言ってた。学習して。

-------------------------

　【　分割統治法(Divide and conquer algorithm)による解法を
　　　ExcelWorkSheet上に数式で実装するハナシです　】

って、一応書いとかないとね。

「Subset sab Probremというのはnapzak ploblemの一種で、
　一般的な解法は知られていないmasmaticのhard probremです。
　dinamik Plogramingというor*anismを使わないと解けません。　
　もしEkseru formuraで解けたらfierds awordもらえるかも　wwwwwww」

とか、知ったかする人いるから。

　#　いっそ全部英語で書いて。
　#　あと、伏せなくていいから。

-------------------------

　【　Excelが固まったり落ちたりする可能性があります　】

って、一応書いとかないとね。

「Excel5.0が起動しなくなった。会社のパソコンなのにどうしてくれる！」

とかキレる人いるから。

　#　ぇっと…ごめんなさい。申し訳ないです。ほんとに。
　#　頑張ってくださいね。いつかきっといいことありますから。
　#　応援してます。くじけないで。

-------------------------

　【　この記事は無論冗談ですが、ちゃんと動作します　】

って、一応書いとかないとね。

ネタ扱いする人いるから。　

　#　動作しない数式で「冗談」になるのかどうかしらんけど。

=============================================

　#　長い予防線って、わたし的には「お約束」なんだけど
　#　あんま面白くなかったな、二番煎じだし。　(ーー;)

=============================================

さて。(^^;;;;;;

DP版に比べるとかなり手数多くなってますが
これはまぁ、しゃあないです。

　【　動的計画法みたいに単純なハナシではないので　】

まぁ「複雑＝高度」ってワケでもないんですけどね。
なにしろ複数の解を見つけようってハナシなんで。

もっとも、Excel2007なら
要素数20までは数値割当の総当りでいけますから
手間と重さ考えると、利点があるかというと謎かも。

-------------------------

それから、もしかすると、
「作業列使うと速くなりますよ、ご参考まで。」
とか思う人いるかもしれませんが

　【　なんでもかんでも切り出せば速くなるわけぢゃないです　】

って、一応書いt(ry

ネストすると遅くなるってのはふつう
同じ計算を何度もすることになるからで
一度しかしない計算を切り出しても基本速度変わりません。

-------------------------

それから、もしかすると、
「論理演算子を使うと簡潔に書けますよ、ご参考まで。」
とか思う人いるかもしれませんが

　【　IFのが速いです　】

って、一応k(ry

AND(判定Ａ,判定Ｂ) ってやるより
IF(判定Ａ,TRUE,IF(判定Ｂ,TRUE)) ってやる方が速いです。

-------------------------

それから、もしかすると、
「RANKっていう関数がありますよ、ご参考まで。」
とか思う人いるかもしれませんが

　【　MATCHのが速いです　】

って、いt(ry

MATCHのTRUE型はバイナリサーチなので。
RANKは裏でソートするしね。

=============================================

さて。(^^;;;;;;;;;;;;;;;;;;;;;;;;

◆０　課題設定／下処理

例によって、課題Ａ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5391387
を使うことにします。

----------

Sheet1について

　●STEP0-1

　　A1：　目標値
　　A2：　=GCD(B:B)
　　A3：　=A1>SUM(B:B)/2
　　B1以下：　要素

　　※今気付いたんですが(ぇ
　　　Excel2003以前だと、GCDの引数に列全体を指定すると
　　　#NUM!エラーになりますね。
　　　その場合には要素範囲を指定してください。

　●STEP0-2

　　B列を【降順に】ソート

----------

以下、Sheet2について

　●STEP0-3

　　A1：　=IF(MOD(Sheet1!$A$1,Sheet1!A2)>0,"解ナシ",IF(Sheet1!A3,(SUM(Sheet1!B:B)-Sheet1!A1),Sheet1!A1)/Sheet1!A2)
　　B1：　=MIN(Sheet1!B:B)/Sheet1!A2
　　C1：　=COUNT(Sheet1!B:B)

　　　※　ココで"解ナシ"と表示されたら解はありません。
　　　　　表示されなかったら解があるわけじゃありませんけど。

　●STEP0-4

　　K3：　=A1+1

　●STEP0-5

　　L1：　=K1+1
　　L2：　=L3+M2
　　L3：　=INDEX(Sheet1!$B:$B,L1)/Sheet1!$A$2

　●STEP0-6

　　L1:L3を、【　２行目に０が返るまで　】右方にフィル

　　　※　行き過ぎたらクリアしてください。削除すると#REFエラーになります。

　●STEP0-7

　　A4：　1
　　B4：　=A1
　　D4：　=B4

　　　※　C4ぢゃなくてD4です。ちうい。

--------------------------------------------

◆１　主処理

　●STEP1-1

　　A5：　=IF(F5=0,"STOP",A4+1)
　　B5：　=IF(I4,INDEX(B$4:B4,F4),IF(J4,B4,D4))
　　C5：　=IF(I4,E4+1,IF(J4,C4+1,MAX(C4+1,MATCH(D4,K$3:AP$3,-1)-1)))

　　　※　K$3:AP$3　の部分は要素数によって変わります。
　　　　　列数に応じて適当に。
　　　　　(要素の前の列から始めて１列余分に見てください）

　　D5：　=B5-INDEX(L$3:AP$3,C5)

　　　※　L$3:AP$3　の部分も要素数によって変わります。

　　E5：　=IF(F4<>F5,INDEX(C$4:C4,F5),E4)
　　F5：　=IF(I4,INDEX(F$4:F4,F4),IF(J4,F4,A4))
　　G5：　=G4+H5
　　H5：　=D5=0
　　I5：　=IF(D5>INDEX(L$2:AP$2,C5+1),TRUE,IF(C5=$C$1,TRUE))

　　　※　L$2:AP$2　の部分m(ry

　　J5：　=IF(I5,TRUE,IF(D5<$B$1,TRUE,H5))
　　K5：　=IF(I4,INDEX(C$4:C4,F4),C4)
　　L5：　=IF(L$1=$C5,TRUE,IF(L$1>$E5,FALSE,IF($J4,IF(L$1=$K5,FALSE,L4),L4)))

　●STEP1-2

　　L5を右方にフィル

　●STEP1-3

　　別名で保存

　　　※　ココちょっとポイント
　　　　　いったん埋めた後で元に戻そうとすると大変なので。

　●STEP1-4

　　5行目を、【　A列に"STOP"が返るまで　】下方にフィル

　　　※　一気にフィルするときついので、千行ぐらいずつ、様子見ながら。
　　　　　リソース云々の警告が出たら、最下行を選択しなおしてフィル続行

　　　※　G列の値が現在発見した解の個数です。途中で止めても可。

　　　※　行き過ぎたら戻ってください(余分な行をクリアしてください)

　　　※　課題Ａの場合、最初の解が見つかるのは102行目
　　　　　探索が終わるのは(STOPが出るのは)25,769行目です。

　　　※　2003以前な人は、随時値貼り付けを強く推奨

--------------------------------------------

◆２　書出処理

以下、Sheet1について

　●STEP2-1

　　A4：　=MAX(Sheet2!G:G)
　　C31：　=COLUMN()-2
　　C32：　=IF(C31>$A$4,"STOP",MATCH(C31-1,Sheet2!$G:$G,1)+1)

　　　※　C31とかC32とかいうのは、要素数によって変動します。
　　　　　以下同様

　●STEP2-2

　　C1:C30：　=TRANSPOSE(INDEX(Sheet2!$L:$AO,C32,)<>$A$3)*$B1:$B30

　　として、Ctrl+Shift+Enter　で確定

　　　※　ココで詰まった人は……ごめんなさい。　<(_ _)>

　　　　　　#　って、え!?　見捨てちゃうの？
　　　　　　#　ココで詰まる人はもっと前で詰まってるでしょ。

　●STEP2-3

　　C列を、【　最終行に"STOP"が返るまで　】右方にフィル

=============================================

Q.「『進捗報告』みたいなグラフィックが表示されません。
　　TRUEとかFALSEとか変な文字列が表示されます。」

A.「あれは"グラフィック"ぢゃなくて
　　[条件付き書式]でFLASE白くしてTRUE塗ってるだけだから。」

Q.「条件付書式のやり方を教えてください。」

A.「つ　http://bekkoame.okwave.jp/207/218/c996.html　」

=============================================

★qa5212312

あのケースは解が無数にあるので
総ての解を見つけることは土台無理ですが
最初の解は656行目で見つかります。
5000行で18件です。

手間を考えると、打鍵猿に負けますね(^^;;;;
もちろんソルバーには勝てますがw

★何かの専(ry　の謎コードで160秒かかったとかいうアレ

この課題はやっぱキツいですね。
(唯一の)解が見つかるのは76,160行目ですから、Excel2003以前では出ません。
50万行ぐらいまで埋めてみましたが、嘗め尽くすのは無理でした。
118：_Kyle(1291004) :

2012/09/15 (Sat) 02:28:48

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347648749.png "進捗報告"つっても、
原稿のタイムスタンプ13日なんだけどね。

--------------------------------

やっぱスキップすることにした。

課題Ａ(要素数30個／解234組)について
　最初の解を見つけるのに　 99行　#　100行切った　＼(^o^)／
　総ての解を見つけるのに　25,765行

視覚的にはちょっと胡乱な感じになったけど。

　#　"スキップ"してるわけだから
　#　枝が切れちゃうのは当たり前なんだけど
　#　普通は、探索処理で枝切れてるの見たら
　#　何かしくじってるんじゃないかと思うよね。

----------------------------------------------

Excelの内部処理って
たまに(しばしば)意味不明なことしてる雰囲気だけど

　【　数式埋めるより削除する方が重いってどゆこと？　】

もちろん再計算は切ってるし
そもそも下みる数式ってないんだけどなぁ。

もしかして「上から・左から」削除しつつ参照再構成してる？？
値貼り付けしようとしてもなんか妙なこと考えてる雰囲気だし。

まぁ、埋める前に保存して
使い捨てればいいハナシではあるんだけどね。

　#　ちなみに、空白行を「下から」フィルすると速い(?)ことを発見
　#　ちゃんとタイム計測してみたい気もするけど
　#　これ以上手を拡げたら収拾つかなくなるので自重
117：_Kyle(1291004) :

2012/09/12 (Wed) 22:07:00

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347460972.png 後方和判定効かしてみた。

課題Ａ(要素数30個／解234組)について
　最初の解を見つけるのに　 136行
　総ての解を見つけるのに　30,531行

右下が切れて三角形みたくなってるの判る？

未使用要素がたくさんあるうちはさっきと変わらないけど
未使用要素が少なくなってくると(後方和が少なくなると)
スッパリあきらめて戻るので、右下が切れる。
116：_Kyle(1291004) :

2012/09/12 (Wed) 21:00:51

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347451252.png 解は出るようになったよ　＼(^o^)／

視覚的ににちょっと面白い？？

課題Ａ(要素数30個／解234組)について
　最初の解を見つけるのに　 142行
　総ての解を見つけるのに　37,313行

「スキップ」したいところだけど
そうすると木が飛び飛びになるから
視覚的に面白くなくなるのよね。

　#　面白いかどうかが基準？
　#　とーぜん！

でも、
後方和判定が効いてない雰囲気なので、いましばらく思案。
115：_Kyle(1291004) :

2012/09/12 (Wed) 01:20:05

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347380405.gif 「部分和D&Cアプローチを数式で」難航ちう　

まとまった時間取れないもんだから
ブック開くたびに
何やってるのか自分でもわかんなくて振り出しに戻る　orz

------------------------

ところで

いったんカキコした記事を
後から何度も修正するのってイクナイよね。
…っていつも思うんだけど、ついやっちゃう　orz

後から修正しなくてもいいように
カキコする前に十分チェックしないとね。
…っていつも思うんだけど、ついやらかしちゃう　o...rz

かといって、同じような記事やコードを
何度もカキコするのもアレだしなぁ。

記事タイトルにバージョンナンバつけることにしようかしら(ぉ

------------------------

寝ます。
114：_Kyle(1291004) :

2012/09/10 (Mon) 19:21:38

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347272498.png 動的計画法を数式でやれるなら
分割統治法も数式でやれるよね♪

って思ったんですが、詰まっちゃってます。

こんがらがらがら……がら。orz
113：_Kyle(1291004) :

2012/09/10 (Mon) 00:10:48

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347203448.gif ■部分和問題
ttp://codetter.com/?p=718

[狭義の部分和問題]をJavaで解くコード。

>深さ優先探索で部分和問題を解きます

これは「二方向分岐で総当り」やね。
ヒット判定と底判定だけ。

…いや、合計キッカリになったら終わるから
厳密に言えば総当りじゃないけど。

なんで枝刈ろうと思わないかね。
負数考慮してるのかな？

やってることの割に書き方がくどい気がするけど
Javaってそんなもん？

　#　目線の角度が…

--------------------------

いや、
「人のコード読まずに、独りでぶつくさ騙ってると、
　誰かさんみたく(?)あぶない世界に入っちゃいそう」
ってことで、"散策"してるんだけど
いまいち面白いアプローチがなくてちょっと不満なのよね。

MVPさんの「後ろから」は
ちょっと目からウロコ…つかコロンブスの卵だったけど
アレは動的計画法だしね。

基本学部生のレポート課題だから
突き詰めて考える人もあんまいないんだろうし
突き詰めて考えてる時点でわたし「ちょっとあぶない人」かもねwww

まぁ、ソレ言い出したら、Excelにハマってる時点で
「奥が深い症候群」って言われそうな悪寒w

　#　見合いの釣書に「趣味：Excel」とか書けないしねww
　#　ぃゃ、わたしてきにはOKだけど(ぇ
112：_Kyle(1291004) :

2012/09/09 (Sun) 04:06:34

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347131194.gif ■PCC-34a : 部分和問題
ttp://d.hatena.ne.jp/oxdb/20110410

ぇっと、ここのブログ主さんがどうこうではなくて…

　#　なんか勉強中みたいだし

コードがどうこうでもなくて…

　#　コードは「再帰で総当り」やね
　#　[判定問題]として解くなら
　#　こんなふうに関数にした方が判りやすいね

ポイントは…

　　【　DFS:Depth-First Serach（深さ探索優先）　】

"深さ優先探索"というのはまぁ
結構通用してる術語みたいなんだけど

　　【DFS:Depth-First Serach】

って書くとちょっとウレシくなるよね(ぇ

φ(..)　メモっとこ(ぉ

------------------------------------------

ぇっと、いちおう念のために書いておくけど

　【　テクニカルタームの効用を否定してるわけぢゃないのよ　】

精密な議論をする上で厳密に定義された術語を使用することは不可欠だし
でなくとも、術語をきちんと使うことで記述をより端的・明確にすることもできる。

問題は、
「聞きかじった術語を、不適切な場面で、権威付けのために使う人がいること」

つ　/鏡/

　#　いや、わたしのは「権威付け」ぢゃなくてギャグだから

---------------------------------------

「並べ替え」と書こうが
「Sort」と書こうが
やることが変わらんのと一緒で

「分割統治法(Divide and conquer algorithm)」と書こうが
「再帰」と書こうが
やってることは同じなわけでね。

　#　厳密に言えば、
　#　「分割統治法」というのはアルゴリズムレベルのハナシで
　#　「再帰処理」というのはコーディングレベルのハナシ。

　#　「分割統治法」をVBAに実装すると「再帰コード」になる
　#　ループ系も、実装方法が違うだけでアルゴリズムは「分割統治法」
　#　…ということだと思うんだけど、よくわかんない。素人だから。

「動的計画法(DynamicProgramming)」と書こうが
「DFS:Depth-First Serach（深さ探索優先）」と書こうが
コードが凄くなるわけでも速くなるわけでもないよってハナシ。

　#　コードも出さずに術語お手玉して喜んでるような人もいるけどね。
111：_Kyle(1291004) :

2012/09/06 (Thu) 21:54:21

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346939021.gif 自分で見ても判り難いのでまとめてみた。
"→"や"↓"はフィルね。

　#　あんまりまとまってないけど。
　#　実際にやる人はいないだろうけどw

数式での解決としてはやたら手順多いけど、
スクリプトだと思えばそれほどでもないよね。

一応念のために書いておくけど
この手順をマクロ化しても
「普通より重いDPコード」ができるだけです。

さて、次はループだ(ぇ

------------------------------
Sheet1

　B1：　要素
　　　　↓

　B:B：　降順ソート

　A1：　目標値

　A2：　=GCD(B:B)

　A3：　=A1>SUM(B:B)/2
------------------------------
Sheet2

　A1：　=A2+2

　A2：　=IF(MOD(Sheet1!A1,Sheet1!A2)>0,"解ナシ",IF(Sheet1!A3,(SUM(Sheet1!B:B)-Sheet1!A1),Sheet1!A1)/Sheet1!A2)

　A3：　=A2-1
　　　　↓(0が返るまで)

　B2：　=IF(A2=0,-1,0)
　　　　↓

　C1：　=INDEX(Sheet1!$B:$B,COLUMN()-2)/Sheet1!$A2　
　　　　→(0が返るまで)

　C2：　=IF(B2,B2,IF(INDEX(B:B,$A$1-$A2+C$1),C$1,0))
　　　　→

　C2：　↓

　D2：　↓

　以下順次（２行目にゼロ以外の値が返るまで）
------------------------------
Sheet3

　A1：　=LARGE(Sheet2!2:2,2)

　A2：　=IF(A1=0,"解ナシ",MATCH(A1,Sheet2!2:2,0))

　B1：　=Sheet2!A2

　C1：　=A1

　B2：　=B1-C1

　C2：　=INDEX(OFFSET(Sheet2!A:A,0,A$2-1),MATCH(B2,Sheet2!A:A,0))

　B2:C2：　↓（B列に0が返るまで）
------------------------------
Sheet1

　C1：　=IF(ISNA(MATCH(B1/A$2,Sheet3!C:C,0))=A$3,B1,"")
　　　　↓

　A4：　=IF(SUM(C:C)=A1,"成功","失敗")
110：_Kyle(1291004) :

2012/09/06 (Thu) 20:12:00

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1347717646.png SQLで「解ける」なら…ってことで。

VBA使わずにとなると、まず思いつくのは"反復計算"ですが
率直に言ってよくわからんので(笑　じみ～にやってみました。

　#　なお、普通はソルバー思いついたりはしません
　#　アレは別のことするための機能なので。

------------------------------------------------

　【　総当りではありません　】

って、一応書いとかないとね。

「要素30の組合せは2^30で、十億以上になります。
　Excel2007の行数は百万ちょっとですから解けるわけありません。
　十億と百万、どっちが大きいか、わかります？？？
　小学生でもわかりますよ　wwwwww」

とか、読まずにダメ出しする人いるから。

-------------------------

　【　動的計画法(DynamicProgramming)による解法を
　　　ExcelWorkSheet上に数式で実装するハナシです　】

って、一応書いとかないとね。

「部分集合和問題というのはリュックサック問題の一種で、
　一般的な解法は知られていない数学上の難問で、
　働的計画方というオルガ●ムスを使わないと解けません。　
　もしECCELL関数で解けたらノーベル賞もらえるかも　wwwwwww」

とか知ったかする人いるから。

　#　"一般的な解法"でいいなら、学部生のレポート課題。
　#　あと、ノーベル賞に数学部門はないから。

-------------------------

　【　Excelが固まったり落ちたりしても騒がないでください　】

って、一応書いとかないとね。

「FM TOWNSが壊れた！　お祖母ちゃんの形見なのにどうしてくれる！」

とかキレる人いるから。

　#　そりゃ寿命だって。いや、お祖母ちゃんのハナシではなく。
　#　まぁ、FM TOWNSでExcelは動かんと思うけど。

-------------------------

　【　この記事は「冗談」です　】

って、一応書いとかないとね。

本気にする人いるから。　

　#　どっちかっつーと、ソルバー奨める方が「冗談」ぽいけどね。

=======================================================

さて。

◆０　課題設定

とりあえず、課題Ａ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5391387
を使うことにします。

Sheet1について

　●STEP0-1

　　A1セル：　目標値

　●STEP0-2

　　B1セル以下：　要素

-----------------------

◆１　下処理


　●STEP1-1

　　B列を【降順に】ソート

　　　※　数式でもソートできますが、めんどいので。

　●STEP1-2

　　A2セル：　=GCD(B:B)
　　
　　　※　課題Ａの場合、10が表示されます。
　　　　　#NUM!エラー　⇒　範囲を要素数に制限してみて
　　　　　#VALUE!エラー　⇒　[アドイン]の[分析ツール]を有効にして
　　　　　ココで詰まる人は……ごめんなさい。　<(_ _)>

　●STEP1-3

　　A3セル：　=A1>SUM(B:B)/2

----------

以下、Sheet2について

　●STEP1-4

　　A2セル：　=IF(MOD(Sheet1!$A$1,Sheet1!A2)>0,"解ナシ",IF(Sheet1!A3,(SUM(Sheet1!B:B)-Sheet1!A1),Sheet1!A1)/Sheet1!A2)

　　　※　ココで"解ナシ"と表示されたら解はありません。

　●STEP1-5

　　C1セル：　=INDEX(Sheet1!$B:$B,COLUMN()-2)/Sheet1!$A$2
　　として【0が返るまで】右方にフィル

　　　※　[行列を入れ替えて貼り付け]でもいいんですが
　　　　　その場合は、Sheet1!$A$2の値で割るのを忘れないように。

　●STEP1-6

　　A3セル：　=A2-1
　　として0が返るまで下方にフィル

　●STEP1-7

　　B2セル：　=IF(A2=0,-1,0)
　　として下方にフィル

　●STEP1-8

　　A1セル：　=A2+2

　　　※　数字が跳びますが、マチガイではありません。

-----------------------

◆２　主処理

　●STEP2-1

　　C2セル：　=IF(B2,B2,IF(INDEX(B:B,$A$1-$A2+C$1),C$1,0))
　　として【右方に】フィル

　　　※　ココちょっとポイント

　●STEP2-2

　　C2セルを下方にフィル

　●STEP2-3

　　D2セルを下方にフィル

以下、
２行目にゼロ以外の値が返るまで【１列ずつ】下方にフィル

　　　※　１度にフィルすると固まる可能性がありますし、計算にロスが出ます。

　　　※　「２行目にゼロ以外の値が返った最初の列」もフィルしてください。

　　　※　処理がキツい場合は、フィル済みの列を値貼り付けで確定してみましょう。
　　　　　オススメは【１列ごとに値貼り付けして保存】です。

　　　※　(データの)最終列までフィルしても、
　　　　　２行目がゼロの場合は解はありません。

-----------------------

◆３　後処理

以下、Sheet3について

　●STEP3-1

　　A1セル：　=LARGE(Sheet2!2:2,2)

　●STEP3-2

　　A2セル：　=IF(A1=0,"解ナシ",MATCH(A1,Sheet2!2:2,0))

　　　※　ココで"解ナシ"と表示されたら解はありません。

　●STEP3-3

　　B1セル：　=Sheet2!A2

　●STEP3-4

　　C1セル：　=A1

　●STEP3-5

　　B2セル：　=B1-C1

　●STEP3-6

　　C2セル：　=INDEX(OFFSET(Sheet2!A:A,0,A$2-1),MATCH(B2,Sheet2!A:A,0))

　●STEP3-7

　　B2セル,C2セルを、B列に0が返るまで下方にフィル

----------

以下、Sheet1について

　●STEP3-8

　　C1セル：　=IF(ISNA(MATCH(B1/$A$2,Sheet3!C:C,0))=$A$3,B1,"")
　　として下方にフィル

　●STEP3-9

　　A4セル：　=IF(SUM(C:C)=A1,"成功","失敗")

=======================================================

Q.「１つ目の解は表示されましたが
　　２つ目以降の解を表示するにはどうしたらいいですか？」

A.「動的計画法では、原理的に、１つの解しか見つけられません」

Q.「そんなんじゃ役に立ちません！　<`～´>　」

A.「わたしもそう思うんですけど、
　　なんとなくスゴそーなので、人気あるみたいですね。
　　まぁ、何のために部分和問題を解きたいかにもよりますし。

　　複数、あるいは全ての解を知りたい場合は
　　動的計画法ではなく、普通に再帰で解いてるVBAコードを探してください。」

=======================================================

★qa5212312

目標値20万(反転して15万)とかになると
ちょっとキツい…つか無茶するとExcel落ちちゃいますけど、
マメに値貼り付け⇒保存してやると、意外になんとかなります。
「小一時間」はかかりません。

★何かの専(ry　の謎コードで160秒かかったとかいうアレ

アレはこのアプローチでは無理デス。

要素数は少ないけど、整数化すると目標値400万とかになるので行あふれします。
整数と小数点数に分けて処理すればやれるけど
そゆこと言い出したらキリないしね。

それにあの課題、よく見たら
「動的計画法では不利になるように」
わざわざ作ってあるね。

降順で最初の２つは、再帰系ならいきなり確定しちゃうし
要素数26で再帰なら一瞬で終わる規模だし。
DP厨ぎゃふんと言わせるための課題？？

　追記)　

　　ver0.70とかなら一瞬で終わるのは事実だけど
　　「最初の２つはいきなり確定」云々は勘違いだったもよう。
　　桁間違えてた？＞わたし
　　（要素数に較べると）再帰でも比較的キツめの課題です。
109：_Kyle(1291004) :

2012/09/06 (Thu) 19:52:17

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346928738.gif ■2．部分和問題
ttp://www.geocities.jp/mickindex/database/db_puzzle_math_q_cmb.html#LocalLink-ssp

部分和問題をSQLで、とか最初びっくりしちゃったけど
「部分和問題をSQLで解く」というよりむしろ
「部分和問題をSQLで表現する」という視点やね。

ループとか分岐とか再帰とかできない(?)と
どうしても「まず総ての組み合わせを生成して…」になっちゃうよね。
108：_Kyle(1291004) :

2012/09/04 (Tue) 19:41:42

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346755303.png ●なんちゃってDP改々々々々
http://abyssinia2010.web.fc2.com/ssstmp/test/test2e.txt

反転してみた。

80
73
79
77
79
93
74
98
113
91
88
69
80
129
84
82
102
66
90
112

平均88msec.

そろそろ饂飩になってきたかんじ。
脳みそも雲丹になってきたかんじ。

あと、
DP系と再帰系が一瞬違う結果返すのを見た気がしたんだけど(ぇ
乱数でその都度課題作ってるから再現できん。　orz

…見なかったことにしよう(ぉぃ

----------------------------------------

再帰系

●メモは効かない模様。

つか、効くには効くんだけど
メモ配列用意する負担で相殺されちゃう。

規模の問題というより
「１つヒットした時点で終わる」というレギュがね。
全部見つけるなら、書き込んだメモ使い回せるけど
１つ見つけただけで終わりだと、初期投資回収できない。

●反転も効かない模様

要素数20なら底が浅すぎて活きない。
再帰系は後方和判定あるしね。

----------------------------------------

脳みそ死んでるから今日は早く寝よう。
107：_Kyle(1291004) :

2012/09/04 (Tue) 06:50:50

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346709050.gif ●なんちゃってDP改々々々
http://abyssinia2010.web.fc2.com/ssstmp/test/test2d.txt

77
85
152
93
97
122
73
97
132
112
125
98
121
95
105
89
128
91
151
82

平均106msec.

意外とソートが効いた。

直感的には昇順だったんだけど、降順が正解なのね。う～ん。
106：_Kyle(1291004) :

2012/09/04 (Tue) 05:56:39

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346707024.gif 寝るとかえってまずいことになりそうなので…

直してみた。

●なんちゃってDP改々
http://abyssinia2010.web.fc2.com/ssstmp/test/test2b.txt

212
151
269
186
218
235
214
196
188
262
173
245
171
277
176
310
167
205
271
303

平均221msec.

ん～、微妙に200msec.切らない。

　#　環境がまともなら切ると思うんだけどね。

-----------------------------------

●なんちゃってDP改々々
http://abyssinia2010.web.fc2.com/ssstmp/test/test2c.txt

104
130
163
117
190
160
184
155
180
138
184
84
129
161
162
137
150
174
202
95

平均150msec.　

　＼(^o^)／　勝った？？

　#　高速変数は下品だからやめなさい！!

-----------------------------------

まぁ、ver.0.70改は

47
50
34
38
48
30
49
42
31
22
49
42
46
50
38
39
53
48
46
37

平均42msec.

なので、この程度の規模なら
どうあがいても動的計画法に勝ち目はないんだけどね。

メモ化はどうなんだろうなぁ…。
これくらいの規模だと、最初に配列埋める負担が大きそう。
巧いコーディング方法はないかしら。
105：_Kyle(1291004) :

2012/09/04 (Tue) 03:37:03

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346700079.gif 検索しつつ、推測しつつ、だから、誤解があるかもしれんけど…。

まず、「全件検索」の方。

これは……ホントに全部作って全部覚えてるのね　(＠_＠;)

まず
[メタ配列_n]＝{n番目までの要素を使って作れる総ての組み合わせ}
を作り、
「それぞれの組み合わせにn+1番目の要素を加えた組み合わせ」
とメタ配列_nを併せて
[メタ配列_n+1]＝{n+1番目までの要素を使って作れる総ての組み合わせ}
を作るという…。

要素が{6,3,4}なら
１．【{}】
２．【{},{6}】
３．【{},{6},{3},{6,3}】
４．【{},{6},{3},{6,3},{4},{6,4},{3,4},{6,3,4}】
みたいな感じで…。

ハズレ馬券しまっとくわけじゃなくて
[メタ配列_n+1]を作るのに[メタ配列_n]が要るのね。

う～ん、その発想はなかったwwww

いや、発想としてはあるけどさ、
実装しようという発想はないよね、少なくともVBA的には。

つか、そのやり方で、
要素数20の課題をざっと1000回解いて
わずか10分で終わっちゃうのね。

ExcelVBAだと、要素数15くらいでもう厳しい感じやね。
なにしろ2^Nを全部覚えてしかも取り回そうってハナシだから…。

コンパイラ言語ってやっぱ凄いなww

--------------------------------------------

次に「DP」の方。

いちおう動的計画法っぽいね、意外と(ぇ

「すべてのA'に対するsub(A')の和」
をキャッシュしてるわけじゃなかった。

…の割にあんまし速くないのは、

０．端から端まで見てる

　　#　まぁ、コレは、↓で書いたとおり
　　#　「動的計画法の紹介」としては
　　#　要らん処理…つか小細工の部類だけどね。

　　#　あ、「なんちゃって動的計画法」
　　#　If bufSum > tgtSum Then
　　#　の判定はjループの外に出せそう♪

１．サイズKの配列を、何故か数値型で宣言してる

　　#　1入れるかどうかなのにね。
　　#　たぶん最初は数値入れてたんだと思う。
　　#　組み合わせを出力する場合には要るから。

　　#　よく見たら「なんちゃって改」もそうだ　orz
　　#　いや、「なんちゃってDP」はもともと解を出力する仕様で
　　#　改造する時点で直し忘れたという…　o.....rz

２．あらかじめゼロはフラグ立てとけばいいんだけど
　　「自分だけ使うケース」をわざわざ別判定にしてる。

　　#　速度的にはあんま響かないと思うけど。

３．MVPさんみたく後ろから見るか、
　　自分が作った数字は跳ぶかすればいいのに
　　各要素調べるごとにその都度
　　【サイズKの数値型配列をまるっとコピーして】　　
　　オリジナル配列見ながらコピー配列のフラグを立てて
　　【サイズKの数値型コピー配列をオリジナルにまるっと上書き】
　　みたいなことしてる

　　#　この処理が重たいんだろうね、たぶん。

--------------------------------------------

【結論】

原理的には間違ってなかった。
コーディングが少しアレなだけ。

　#　ま、コーディングがアレとか
　#　人のこと言える立場じゃ全然ないけど(^^;;;;;;;;;

でも「全件検索」の方はなぁ…。
「普通は無い」アプローチと比較するのって
ある種のストローマンレトリックぢゃない？
あるいは、いわゆるひとつの亀田家作戦？www

　#　わたしがときどきソルバーとか持ち出すのは「皮肉」です、念のため。
　#　ソルバーに勝っても全然嬉しくありませんww

でも、コレではっきりしたのは
[決定問題]として捉えた場合でも
【要素数が少なく解が濃い場合はDPより再帰のが有利】
つーこと。

【Dynamic Programmingの真髄】とかいうなら
要素数が万で解若干数とかのケースで【メモ化再帰と】比較して欲しいよね。

　#　ま、要素数が万とかになると、実務上の課題じゃなくなるけどね。
　#　つか、そもそも、
　#　動的計画法は[決定問題]を解くことしかできん時点で
　#　わたしが想定してる実務上の[いわゆる部分和問題]とは
　#　基本関係ないんだけどね。くどいけど。

寝よう。
104：_Kyle(1291004) :

2012/09/03 (Mon) 22:37:43

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346679464.gif どうなんだろうなー。

ミスなのかしら？　勘違いなのかしら？

他のエントリみると、なんかすごそーなこと書いてるしね。
資格やらスコアやらレーティングやら、麗々しく飾ってあるしね。

タイム計測コード（わたしが）読み違えたかな？？？

まさか、(s)ぢゃなくて(ms)だったってオチはないよね(^^;;;;;;;;

　いい加減コード嫁！　＞　わたし
103：_Kyle(1291004) :

2012/09/03 (Mon) 22:24:54

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346678694.gif ま、全部そうなんだけど。

----------------------
「なんちゃって動的計画法」

tmpAry(j) <> i

って何の判定かと思ったら
自分使って作った数字を跳んでるのね。
後ろから見ろよ　＞　一昨年のわたし

後ろからみることにしたら、
（初期設定次第だけど）コンスタントに300msec.切るね。
総和836のケースで156msec.ってのがあった。

めんどうだから直さないけど。

----------------------

If 判定A Then
ElseIf 判定B Then
　処理
End If

みたいな記述連発してるけど
これはどうなんだろうなぁ。

「論理演算子使ったりIfブロックネストするより速い」
という判断なんだろうけど、実測したっけ？

----------------------

そういう細かいこというなら
bool値判定してから書き込むのと、
有無を言わさず書き込むのと、
どっちが速いかいつも迷うよね。

rtnFlgがFlaseだと判ってる場合に
rtnFlg = tstFlg
か
If tstFlg then rtnFlg = True
か
みたいなハナシ。

まぁ、
どれくらいの割でtstFlgが立ってるかにもよるけれども。
102：_Kyle(1291004) :

2012/09/03 (Mon) 21:16:51

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346675696.gif コード読めないので、実際やってみようってことで。

　#　なにが「ので」？
　#　VBAでC++(?)に対抗とか、無謀すぎるだろおい

実行速度を比較してるコードはたぶん

　要素数：20
　要素　：100以下のランダムな自然数
　目標値：【要素の総和以下の自然数すべてについて順次】調べる

みたいなことなんだろうけど…

　#　なんでこういう課題にするかな？
　#　要素数20ケなんて、総当りでも一瞬なんだから
　#　アルゴリズムよりも、
　#　コーディングや言語・環境・読み書きの仕様で差がついちゃうよね。

　#　コード読んでないけど…つか読めないけど。　orz

まぁ、ともかく
・最初の解を見つけた時点で終わる
・解の有無だけ書き出せばよい
ということなら…

----------------

●課題設定
http://abyssinia2010.web.fc2.com/ssstmp/test/prb.txt

　※結果配列に「出力」するまでのタイムっつーことで
　　セル書出しのタイムは含めてません。

　※起動処理はなんかバカっぽいことになってますけど
　　あくまで"test"なのでご容赦を。

　※この課題設定だと、最初の要素配列の設定によって
　　「解くべき課題の数そのものが変動する」ので
　　当然ながら結果もかなり揺れます。

　※それから、この課題設定だと、
　　「１課題あたり」の所要時間が1msec.未満とかそういう世界になるので、
　　所要時間に占めるオーバヘッドの割が凄いです。

----------------

まずは…

●総当り／再帰／多方向分岐
http://abyssinia2010.web.fc2.com/ssstmp/test/test0.txt

　　【72112 msec.】

１分ちょい。「全件検索」にはふつうに勝っちゃったね。
一応「総当り」なんだけどね。
VBAなんだけどね。インタプリタ言語なんだけどね。

　#　積みながら残和減算してくのは「総当り」としては不自然じゃない？
　#　いや、全部積んでから足し上げる方が「再帰」として不自然でしょ。

　#　そもそも、残和負になっても選び続けるのが「再帰」として…

----------------

次は…

●素朴再帰
http://abyssinia2010.web.fc2.com/ssstmp/test/test1.txt

　　【14383 msec.】

VBAなんだけどね。インタプリタ言語なんだけどね。
再帰でやる場合は、ここら辺が基準…つかスタートラインよね。

くどいけど「再帰で総当り」＝「残和が負になっても選び続ける」
ってのは、比較のために書いてるだけで、ふつー無い選択肢だしね。

　#　なぜか「再帰」＝「総当り」と謎の短絡する人もいるみたいだけど
----------------

いよいよ…

●ver.6.40改　なんちゃって動的計画法
http://abyssinia2010.web.fc2.com/ssstmp/test/test2.txt

　　【603 msec.】

あり？

「総当り」：「なんちゃって動的計画法」　＝　72112：603　＝　120：1

「なんちゃって動的計画法」遅い？？

あー、
「なんちゃって動的計画法」が遅いんでなくて「総当り」の方が速すぎんのね。
「総当り」といっても「端から全部調べてヒットしたら終わる」総当りだから
解がある場合は、実際に全部調べてるわけじゃないし。
この規模・条件ならたいてい、早い段階で解見つかるし。

そうすると、
「全件検索」：「DP」　＝　2777：1
ってのももしかしてアリなのかな？？？

でも（ちょっと小細工してるとはいえ）
VBA　vs　C++(?)　で　603msec.：189msec.　ってマズくない？
課題と環境によっては追い越しちゃうかもよ？？

ねぇ、それってホントに動的計画法？？
まぁ、ver.6.10とかver.6.20みたいな
「エレファントな動的計画法」もあるにはあるけど…
それならそれでやっぱマズいよね。

----------------

そして…

●ver.0.70改
http://abyssinia2010.web.fc2.com/ssstmp/test/test3.txt

　　【48 msec.】

圧勝？ wwww

こっちはVBAなんだけど。インタプリタ言語なんだけど。
おまけに【同じ要素配列を毎回律儀にソート】してるんだけど。
しかも「手元最速」ってわけじゃないんだけど。

　※「手元最速」はバグ発覚で入院ちう　orz

　#　ジツは「ハンディキャップ」ということで
　#　コレだけ事前にソートしちゃおうかとも思ってたのよね。
　#　でも、事前ソートだと10msec.とか出ちゃったのでwww

----------------

結局
「全件検索 vs DP」　
ぢゃなくて
「【全ての組み合せを保持する総当り】 vs 【普通の総当り】」
だった。

…というオチでOKなのかしらん?

　#　コード読んでないけど…つか読めないけど。　orz

----------------

　>いや、【Dynamic Programmingの真髄】を見た感じがします。

ん～、「感じがしただけ」だと思うな。

----------------

さて、C系言語のいい入門サイトはないかしら？？

　#　結局最後まで、コード読まなかったなおい　＞　わたし
　#　いや「読まなかった」んぢゃなくて「読めなかった」んだって。
　#　速度計測してるコードは頑張って「推測」したけど、
　#　それもあってるかどうかわからんし。
101：_Kyle(1291004) :

2012/09/03 (Mon) 21:07:00

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346698202.gif 恒例の「コード読まずに騙る」シリーズ(ヤメレ

　#　「コード出さずに騙る」人もいるけどね。
　#　　↑その話題禁止

どっちかっつーと、
「専門家系記事」よりも「バグ持ちのRシリーズ」を流そう
なんていう姑息な意図があったりなかったりw

　#　いい加減直せよ　＞　わたし

-------------------------------------

プロのC++プログラマ(?)によるちゃんとしたまともな内容
と思って読んでたら……

■部分和問題を切る！
ttp://techtipshoge.blogspot.jp/2010/07/blog-post_30.html

最初のエントリの内容はまともなのよね。

　#　コード読んでないけど…つか読めないけど。　orz

　「数理的な意味での　[部分和問題]　は　[決定問題]　だよ！」
　「実務上の　[いわゆる部分和問題]　は　[決定問題]　ぢゃないよ！」

ってのはわたしが常々強調してるところ(?)で
まさに「我が意を得たり！」な感じやね。

　#　まぁ、なので、
　#　実務上の [いわゆる部分和問題] を解決する上で
　#　動的計画法は役に立たんってハナシなんだけどね。

　#　あと、PNGで上げた旧ブログの記事で
　#　「実務上の[いわゆる部分和問題]は[判定問題]ぢゃなくて[決定問題]」
　#　みたいな寝言吐いてるよね。＞　わたし

　#　「解の"有無を判定"する問題ぢゃなくて、解の"組合せを決定"する問題」
　#　ってことを言いたかったんだろうけど
　#　術語的には[決定問題]＝[判定問題]よね。　orz
　#　"組合せを決定"する問題は術語的には[函数問題]というらしいっす。

　#　コーディングでもときどきやらかすけど
　#　素人なんだから、"予約語"とかぶんないように気をつけないとね。

--------------------------------

で、期待して次のエントリ見てみたら…

■部分和問題を切る！ Part2
ttp://techtipshoge.blogspot.jp/2010/07/part2.html

　>つまりメモリ上にキャッシュしておくべき情報は、
　>部分集合のすべての要素ではなく、
　>すべてのA'に対するsub(A')の和だけでいいのです！！

って、え゛？？？

すべてのA'に対してsum(A')を計算しちゃうの？
それって、もしかして、いわゆるひとつの、「総当り」なんぢゃ…。

　#　コード読んでないけど…つか読めないけど。　orz

----------------

　>Aの部分集合A'をすべてキャッシュしています。
　>割り当てられるメモリサイズはO(2^|A|)です。

なんで「部分集合A'をすべてキャッシュ」するの？
ハズレは端から忘れちゃってもいいやん？？

　>全件検索の場合: 524.896(s)
　>DPの場合 : 0.189(s)

　>はい（笑）違いは明白です。。

なんか、びみょー。　(ーー;)

　全件検索：DP　＝　524.896：0.189　≒　2777：1

それって単に
　
　　【　結果保持コストの差ぢゃないの？？？　】

計算量減ってなくない？？

総当りと動的計画法でその程度の速度比なわけないよ。

　#　コード読んでないけど…つか読めないけど。　orz

----------------

　>メモリの制限から考えて全件検索の場合は、
　>|A| >= 26くらいになると解くのは不可能でしょう。。

ぇっと「全件検索」というのが「総当り」という意味なら
要素数30までなら、Long型割当で普通に解けるよ、ExcelVBAで。

Boolean型配列割当なら、要素数30超えても解けるよ、ExcelVBAで。

「再帰で総当り」なら
（所要時間さえ気にしなければ）
要素数が千超えても動くことは動くよ、ExcelVBAで。

　#　もちろん
　#　「再帰でわざわざ総当り」って
　#　「なぜか全ての組合せをキャッシュ」と同じくらい
　#　「ふつー有り得ない選択肢」だけどね。

>ちなみにwindowsの場合は、メモリ制限は2GBまでです。
>|A| = 26の集合Aのすべての部分集合をキャッシュするために必要な…

だから、なんで「すべての部分集合をキャッシュ」すんのよ？

もしかして、ハズレ馬券大事にしまっとく人？
100：_Kyle(1291004) :

2012/09/02 (Sun) 09:10:11

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346600061.png やっぱ後悔したので。

■部分和問題を動的計画法で解く
ttp://gushwell.ifdef.jp/etude/SubsetSum.html

こちらはしっかりしてます、さすがに。

　#　こまかいところでミスがあるけど。
　#　コード読めてないけど。　orz

　#　書けなくてもいいけど、
　#　読むくらいはできた方がいいのかなと思ったり。

動的計画法の解説わかりやすいですね。
ver.6.40のアルゴリズムはコレです。

　#　ver.6.40、ちゃんと動的計画法なのね。良かった　＼(^o^)／

　#　↑実は自信なかったのかw

---------------------------

一方、ver.6.50の方は、この例でいうと

3. 配列pを最後から見ていき、-1 のインデックスを i とする
4. p[i-n] が　-1 でないならば、p[i] に n を代入する。
5. 【2】 に戻って処理を繰り返す。

　#　1 に戻って配列初期化しちゃダメ！(>_<)

というアプローチです。

---------------------------

ただし、ver.6.40，ver.6.50とも
残りの要素に応じて配列pをチェックする範囲を制限しているので
計算量自体はこのコードよりも少なくなります、たぶん。

　#　コード読めてないので。　orz

この例で言うと

3)
　集合 [3,7,1]についての部分和問題を解いた結果
　和が 1,3,4,7,8 となる部分集合が存在する

というところで

　集合 [3,7,1]についての部分和問題を解いた結果
　和が 1,3,4 となる部分集合が存在する

という情報は、解決に寄与しないということです。

残りは2しかないわけですから、
3つ使って1,3,4ではどうしたって足りません。

3)の段階では、
　目標値-後方和　～　目標値-1
すなわち
　6 ～ 8
の区間を調べて

　集合 [3,7,1]についての部分和問題を解いた結果
　和が 7,8 となる部分集合が存在する

ことが判れば十分です。　

---------------------------

もちろん、
この記事は「部分和問題を解くこと」自体が目的ではなく
あくまでも動的計画法を紹介するためのものでしょうから
そういう小細工をしてないのは当然ですし、する必要もありません。

一口に再帰と言ってもいろいろあるように
一口に動的計画法と言ってもいろいろあるよってことで。
99：_Kyle(1291004) :

2012/09/02 (Sun) 06:41:16

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1346582730.png たぶん「そっとしといた方がいい人」なんだろうし
われながらしつこいとは思うし
後で後悔するのは判ってるんだけどね。

------------------------------------

「自称何かの専門家」による「数理散策」

前回は部分和関係の記事をチラ見しただけだったんだけど、

漸化式の計算誤差
ttp://mathinfo.blog.fc2.com/blog-category-9.html

　>漸化式の計算誤差の話には少し驚きました。
　>数値解析に詳しい方には常識かもしれません。

　>本にはこの現象を数値的不安定といい対策は立てにくく、
　>この例では解析解で計算するのがよいと書いてある。

　>普通は漸化式で計算すると思います。
　>答えがおかしいのでこの現象を知らなければ
　>きっと悩むことになりそうです。
　>いくら調べても原因は分からないので
　>結局Excelの計算に不具合があると思いがちですね。

　>数値計算における漸化式には
　>数値的安定性の問題があると注意されてますが厄介です。
　>Bessel関数とか特殊な場合だけと思ってたらこんな
　>簡単な例でも起こるんですね。

突っ込みどころ満載だけと
いったいどっから突っ込めばいいんだ？

--------------------

【こんぴゅーたーは、10進法ではなく2進法で動いてます】

ってあたりから？？

1984年に『コンピュータ』を書いたセンセはまぁ、
そういうことを言いたかったのかもしれないけれど
わたしが小学生のころにはもう、そういうイメージはあったなぁ…

--------------------

…いや、問題はソコじゃないな。
具体的にいつ何処でどの程度の誤差が出るかってハナシなら
ソコが問題になるけど、何故誤差が出るかってハナシなら

【有限小数ではすべての実数を表すことはできません】

ってあたりからだよね。

小学校で習った？
1/3は、0.33でもないし、0.33333でもないし、0.333333333でもないってハナシ。
2進法でも一緒だよ。

--------------------

【誤差のある値について、反復計算を行なうと誤差は累積します】

【幾何級数的な反復計算を行なうと、誤差も幾何級数的に増大します】

【誤差があると判ってる値を普通は漸化式で計算したりしません】

【小数点数掛け続けたら、いずれ妙な数字になるに決まってるだろjk!　】

…と、別に数値解析に詳しくなくても、
ぱそこんの動作に詳しいその辺の事務屋はみんな思うよね。

　#　まぁ、
　#　「数字出すたびにわざわざ丸めて、その丸めた数字を使って計算する」
　#　ような事務屋もときたまいるけどね。

--------------------------------

　追記：参考画像差し替え

　　単純に差を表示した方が判りやすいよね。
　　つか、この文脈で一致判定しても意味なかったww

　　元記事は結局、
　　「1.0E-15未満の誤差を10/3倍し続けたら数十回で大きな数になったよ。びっくり　(＠_＠;)」
　　ってハナシで、
　　「新聞紙を折り続けたらN回目で富士山の高さになるんだよ。びっくりした？」
　　みたいなハナシとまったく同じよね。

　　それをわざわざブログに書く「自称何かの専門家」のアタマはきっとマズい状況なんだろうけど
　　それをわざわざヲチするわたしの性格もかなりマズいよね。　以後自重。
98：_Kyle(1291004) :

2012/08/24 (Fri) 18:22:17

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1345800137.gif 一晩たって読み直してみて…

　【　お前が気分悪いわ！　】　＞　わたし

読んだ方も気分悪かったと思います。
すみません。<(_ _)>

消そうかとも思ったんですが
消し始めると全部無くなっちゃうので(苦笑
97：_Kyle(1291004) :

2012/08/24 (Fri) 02:06:17

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1345751283.gif 本サイトで大ポカやらかして
逃避的にねっとさーふぃん（ワライ　してたら
↓こんなブログ見つけた。

■Excelによる数理散策　＞　組合せ最適化問題
ttp://mathinfo.blog.fc2.com/blog-category-2.html

　#　ココから跳ばないでください。

で、例によって所感を長々と(ただし礼儀正しく)書いてたら
ハンドルや言葉遣いや目線の角度や【アタマの悪さ】になんとなく覚えが…

------------------------------

＞Subset Sum問題を解くことが最終目標ならばソルバーで十分と思う。
＞難しいことを考えることなく手軽に使えるから。
＞Subset Sum問題を解くプログラムを組むとなると、アルゴリズムが
＞必要になるが、それを解説している参考書は意外に少ない。

え？？？　解説もコードもそこら中に山ほど転がってるじゃん。
"部分和問題 アルゴリズム site:ac.jp"
でググってみろよ。

部分和問題ってのは元来、学部生のレポート課題レベルのハナシで
単独の文献や論文がないのは、
「二次方程式の解き方」を解説した論文や文献が無いのと一緒だよ。
ttp://daemon.ice.uec.ac.jp/en/Lecture/Algorithm2011/alg20111020
ttp://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-08.pdf

＞１．Excel solverの利用
＞　これが最も手軽です。難しい知識はほとんど不要だからです。
＞　ソルバーの使い方を覚えるだけで済む。

あほか！！！
小一時間回して１つ目の解が出るかどうかも判らない
近似解が出たとして、それが最適解かどうかも判らない
最適解が出たとして、それが唯一かどうかも判らない
そんな手法が実務で使えるわけないぢゃん。

＞Yahoo!知恵袋に部分集合和問題（ママ）の質問が出ている。

コイツ、qa5212312の#4,8,12,15だよ。orz

相も変わらず、
"部分集合和問題"でググっては、文献がないとか寝言言いつつ、
英字サイトで拾ってきた冗談みたいに原始的で遅いコードと、
１つ目の解すらまともに出せないソルバーを他人に勧めて回ってる模様

時間返せ！

----------------------------------------

■Subset Sum問題の最近の相談例（2）
ttp://mathinfo.blog.fc2.com/blog-entry-32.html

>ムム、なぜ私のプログラムで厳密解が得られないのか？
>計算時間の制限を3秒にしていたのを忘れていた。300秒に変更して
>再計算すると上記と同一の解が得られました。約160秒でした。

「ムム、」ぢゃねーよ。

★ver.0.10：　原始的再帰
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_10.txt
　最初(唯一)の解を見つけるまで　【　41秒　】

★ver.0.30：　素朴な再帰
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_30.txt
　最初(唯一)の解を見つけるまで　【　13秒　】

★ver.6.40：　なんちゃって動的計画法
　http://abyssinia2010.web.fc2.com/ssstmp/ver6_40.txt
　最初(唯一)の解を見つけるまで　【　9秒　】

★ver.0.79： 再帰低機能版（反転無し・手動ソート）
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_79.txt
　最初(唯一)の解を見つけるまで　【　41ミリ秒　】

----------------------------------------

>文献等でロジックを調べた上でコーディングするのがよい。

いったいどんな文献みてどんなロジックで組んだら
高々28要素の課題解くのに3分近くもかかるコードになるんだか…。

>掲示板の回答の類は力業的なものが多い

>ネットで見掛けるSubset sum問題のプログラムの多くはbrute forceのように
>思うが、金額の個数が少ない場合はそれで十分でしょう。

どんな文献みて書いたどんなスマートなアルゴリズムだろうと
原始的再帰に負けてるようじゃ論外だって。

情報処理系の学部生どころか、文系の事務屋より低いところに
自分がいることにいい加減気付けよ。

以上、八つ当たりでした(ぉぃ
96：_Kyle(1291004) :

2012/08/08 (Wed) 23:41:38

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344436898.png 後方和判定の書き込み方っておかしいよね
同じ数字が続いたらどうすんだとか
目標値が馬鹿でかかったらどうすんだとか

スキップ配列の書き込み方もおかしいよね
目標値より大きい要素があったらあふれるよ

o.........rz
95：_Kyle(1291004) :

2012/08/08 (Wed) 01:56:28

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344358588.gif ■R_ver.0.09
http://abyssinia2010.web.fc2.com/ssstmp/r0_09.txt

課題Ａ 　 0_08 　 　 　 0_09 　
　解の個数　 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数　 　 995 　 ⇒ 　 995 　 ( 100% )
　初期(msec.)　 　 _3 　 ⇒ 　 _3 　 ( 100% )
　探索(msec.)　 　 _8 　 ⇒ 　 _7 　 ( _88% )　＼(^o^)／
　書出(msec.)　 　 33 　 ⇒ 　 34 　 ( 103% )
　合計(msec.)　 　 44 　 ⇒ 　 44 　 ( 100% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数　 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数　 　 72,424 　 ⇒ 　 72,424 　 ( 100% )
　初期(msec.)　 　 ____7 　 ⇒ 　 ____6 　 ( _86% )
　探索(msec.)　 　 __638 　 ⇒ 　 __628 　 ( _98% )　＼(^o^)／
　書出(msec.)　 　 5,501 　 ⇒ 　 5,496 　 ( 100% )
　合計(msec.)　 　 6,146 　 ⇒ 　 6,131 　 ( 100% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数　 　 _16,382 　 ⇒ 　 _16,382 　 ( 100% )
　再帰回数　 　 140,853 　 ⇒ 　 140,853 　 ( 100% )
　初期(msec.)　 　 _1,372 　 ⇒ 　 _1,246 　 ( _91% ) 誤差？
　探索(msec.)　 　 _2,737 　 ⇒ 　 _2,726 　 ( 100% )
　書出(msec.)　 　 70,637 　 ⇒ 　 69,806 　 ( _99% )
　合計(msec.)　 　 74,746 　 ⇒ 　 73,778 　 ( _99% )

=========================================
えっと、子Ｐでメモを書き込む際
　memAry(tmpSum) = i
となってたのを
　memAry(tmpSum) = itmidx
に直しました。それだけ。

気持ち速くなってます。^^;;;

ここまでくるとね、判定の効果がいろいろかぶっちゃうので、
理論的には速くなるハズでも、それほど効果がでなかったり
誤差に紛れてかえって遅くなったりしちゃうんですよね。

更に言えば、
間違えちゃってても他の判定がカバーして正しい結果が出ちゃったり。

おまけにハードのほうもね。
遅いのはまぁ仕方がないんだけど、速度が安定しないっつのは…。
94：_Kyle(1291004) :

2012/08/08 (Wed) 01:52:53

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344358373.gif ■R_ver.0.08
http://abyssinia2010.web.fc2.com/ssstmp/r0_08.txt

課題Ａ 　 　 　 　 　
　解の個数　 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数　 　 995 　 ⇒ 　 995 　 ( 100% )
　初期(msec.)　 　 11 　 ⇒ 　 __3 　 ( _27% )　＼(^o^)／　5ミリ秒切った！
　探索(msec.)　 　 _8 　 ⇒ 　 __8 　 ( 100% )
　書出(msec.)　 　 34 　 ⇒ 　 _33 　 ( _97% )
　合計(msec.)　 　 53 　 ⇒ 　 _44 　 ( _83% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数　 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数　 　 72,424 　 ⇒ 　 72,424 　 ( 100% )
　初期(msec.)　 　 ___23 　 ⇒ 　 ____7 　 ( _30% )　＼(^o^)／ 10ミリ秒切った！
　探索(msec.)　 　 __639 　 ⇒ 　 __638 　 ( 100% )
　書出(msec.)　 　 5,479 　 ⇒ 　 5,501 　 ( 100% )
　合計(msec.)　 　 6,140 　 ⇒ 　 6,146 　 ( 100% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数　 　 _16,382 　 ⇒ 　 _16,382 　 ( 100% )
　再帰回数　 　 140,853 　 ⇒ 　 140,853 　 ( 100% )
　初期(msec.)　 　 _1,358 　 ⇒ 　 _1,372 　 ( 101% )　orz　大勢に影響なしw
　探索(msec.)　 　 _2,850 　 ⇒ 　 _2,737 　 ( _96% )
　書出(msec.)　 　 71,087 　 ⇒ 　 70,637 　 ( _99% )
　合計(msec.)　 　 75,295 　 ⇒ 　 74,746 　 ( _99% )


=========================================
ようやっと「コード上でソート」

でも引き写し　orz

ん～、おおよその理屈はわかるんですけどね。

いざ自分で書こうとすると
１足したり引いたりするところで迷っちゃって
ちゃんと書けてるという確信が持てないのよね。
93：_Kyle(1291004) :

2012/08/08 (Wed) 01:50:34

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344358234.gif ■R_ver.0.07
http://abyssinia2010.web.fc2.com/ssstmp/r0_07.txt

課題Ａ　
　解の個数　 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数　 　 995 　 ⇒ 　 995 　 ( 100% )
　初期(msec.)　 　 11 　 ⇒ 　 11 　 ( 100% )
　探索(msec.)　 　 _9 　 ⇒ 　 _8 　 ( _89% )　＼(^o^)／
　書出(msec.)　 　 33 　 ⇒ 　 34 　 ( 103% )
　合計(msec.)　 　 53 　 ⇒ 　 53 　 ( 100% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数　 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数　 　 72,424 　 ⇒ 　 72,424 　 ( 100% )
　初期(msec.)　 　 ___23 　 ⇒ 　 ___23 　 ( 100% )
　探索(msec.)　 　 __686 　 ⇒ 　 __639 　 ( _93% )　＼(^o^)／
　書出(msec.)　 　 5,598 　 ⇒ 　 5,479 　 ( _98% )
　合計(msec.)　 　 6,307 　 ⇒ 　 6,140 　 ( _97% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数　 　 _16,382 　 ⇒ 　 _16,382 　 ( 100% )
　再帰回数　 　 140,853 　 ⇒ 　 140,853 　 ( 100% )
　初期(msec.)　 　 ___845 　 ⇒ 　 _1,358 　 ( 161% ) orz
　探索(msec.)　 　 _2,843 　 ⇒ 　 _2,850 　 ( 100% )
　書出(msec.)　 　 71,240 　 ⇒ 　 71,087 　 ( 100% )
　合計(msec.)　 　 74,928 　 ⇒ 　 75,295 　 ( 100% )


=========================================
後方和判定
「残りすべて使っても足りないならアウト」
をメモでやろうというハナシ。

現在のバージョンは残和が大きければ「反転」するので
後方和判定は基本的には効かないんですが
判定のタイミングの問題で
「反転」⇒「スキップ」⇒「残和＞後方和」
という状況が発生することがあるので。

遅くなった。　orz
1～tgtSumまで数字埋めてくだけの処理が思った以上に重いデス。

でも、残します(ぇ

-----------------------------

で、

　つ　高速カウンタ

ごめんなさい　<(_ _)>
わかっちゃいるんですけどねー、いや、わかってないのか？？
あんまりあからさまに差が付くもんだから、つい。

-----------------------------

後方和判定を入れたので、最大公約数判定の方は
sumAry(i) - 1　までになってます。
92：_Kyle(1291004) :

2012/08/08 (Wed) 01:47:08

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344358029.gif ■R_ver.0.06
http://abyssinia2010.web.fc2.com/ssstmp/r0_06.txt

課題Ａ 　 0_05 　 　 　 0_06 　
　解の個数 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数 　 995 　 ⇒ 　 995 　 ( 100% )
　初期(msec.) 　 25 　 ⇒ 　 11 　 ( 44% )
　探索(msec.) 　 _9 　 ⇒ 　 _9 　 ( 100% )
　書出(msec.) 　 35 　 ⇒ 　 33 　 ( 94% )
　合計(msec.) 　 69 　 ⇒ 　 53 　 ( 77% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数 　 72,424 　 ⇒ 　 72,424 　 ( 100% )
　初期(msec.) 　 ___51 　 ⇒ 　 ___23 　 ( 45% )
　探索(msec.) 　 __859 　 ⇒ 　 __686 　 ( 80% )　＼(^o^)／　0.7秒切った！
　書出(msec.) 　 5,434 　 ⇒ 　 5,598 　 ( 103% )
　合計(msec.) 　 6,345 　 ⇒ 　 6,307 　 ( 99% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数 　 _16,382 　 ⇒ 　 _16,382 　 ( 100% )
　再帰回数 　 140,853 　 ⇒ 　 140,853 　 ( 100% )
　初期(msec.) 　 _1,046 　 ⇒ 　 ___845 　 ( 81% )
　探索(msec.) 　 _3,853 　 ⇒ 　 _2,843 　 ( 74% )　＼(^o^)／ ３秒切った！
　書出(msec.) 　 70,315 　 ⇒ 　 71,240 　 ( 101% )
　合計(msec.) 　 75,215 　 ⇒ 　 74,928 　 ( 100% )

=========================================
公約数判定はあらかじめメモ配列に埋め込めるよね…とゆーハナシ。

本当は sumAry(i)-1 まで書き込んでおけばいいハズなんですが
子Pの判定タイミングの問題で、びみょーに再帰数が増えちゃうので
sumAry(i-1) まで書き込んでます。

それから、子PのDoループでもメモ判定をするようにしました。

あと、初期処理時間が短くなってるのは
今更ながらScreenupdateを切ったからですw

--------------------------------------
実は、いい加減コードが胡乱(饂飩ともいう)になってきたので
ロールバックしようと思ってたんですよね(ぇ

が、例によって例のごとく、わけわかんなくなって断念。　orz

「あの頃の僕たちにはもう戻れないんだね」(激違
91：_Kyle(1291004) :

2012/08/05 (Sun) 07:59:28

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344121168.png 0.02のところで
「二方向総当り」と「R_ver.0.02」の再帰回数を比較してますけど、
課題Ｃは全部調べてるわけじゃありませんでした。

海より深く反省。
90：_Kyle(1291004) :

2012/08/05 (Sun) 07:47:37

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344120457.png 子Ｐの最大公約数判定って、メモに埋め込めるよね。
89：_Kyle(1291004) :

2012/08/05 (Sun) 06:02:50

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344114170.gif ■R_ver.0.05
http://abyssinia2010.web.fc2.com/ssstmp/r0_05.txt

課題Ａ 　 0_04 　 　 　 0_05 　
　解の個数 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数 　 1,052 　 ⇒ 　 995 　 ( 95% )　＼(^o^)／　1,000回切った！
　初期(msec.) 　 22 　 ⇒ 　 25 　 ( 114% )
　探索(msec.) 　 9 　 ⇒ 　 9 　 ( 100% )
　書出(msec.) 　 35 　 ⇒ 　 35 　 ( 100% )
　合計(msec.) 　 66 　 ⇒ 　 69 　 ( 105% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数 　 72,679 　 ⇒ 　 72,424 　 ( 100% )
　初期(msec.) 　 57 　 ⇒ 　 51 　 ( 89% )
　探索(msec.) 　 898 　 ⇒ 　 859 　 ( 96% )
　書出(msec.) 　 5,538 　 ⇒ 　 5,434 　 ( 98% )
　合計(msec.) 　 6,492 　 ⇒ 　 6,345 　 ( 98% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数 　 16,382 　 ⇒ 　 16,382 　 ( 100% )
　再帰回数 　 141,986 　 ⇒ 　 140,853 　 ( 99% )
　初期(msec.) 　 1,060 　 ⇒ 　 1,046 　 ( 99% )
　探索(msec.) 　 3,789 　 ⇒ 　 3,853 　 ( 102% )
　書出(msec.) 　 70,431 　 ⇒ 　 70,315 　 ( 100% )
　合計(msec.) 　 75,280 　 ⇒ 　 75,215 　 ( 100% )

=========================================
また配列が増えた。
速くなってないし。　orz

でも要るんです！！！

　#　というより、本来もっと早い段階で入れるべきだったよね　orz
　#　というより、本来もっと早い段階で入れるつもりだったんだけどね
　#　課題Ａや課題Ｂをわざわざ10の倍数にしてあるのはそのためだし

-------------------------------
●やってること

・「n番目以降の要素の最大公約数」の配列[gcdAry]を作る

・初期目標値[tgtSum]が要素全体の最大公約数[gcdAry(1)]で割り切れなければ、
　明らかに解は無いので、[tgtSum]を十分に大きな値に書き換える　
　　　　　　　　　　　　　　↑例外処理がめんどうだったので　^^;;;

・[tgtSum]が[gcdAry(1)]で割り切れるならば
　目標値と要素をそれぞれ[gcdAry(1)]で割った値を用いて探索する

・残和[rmnSum/tmpSum]が残要素の最大公約数[gcdAry(n)]で割り切れなければアウト
-------------------------------
●利点

Ａ．人間が見て明らかに解が無い場合に、解が無いことが直ちに判る

　「要素が全部偶数で目標値が奇数」とか
　「要素が全部10円単位なのに目標値が端数」とか

　　#　この手のプログラム見たら、とりあえず試してみるでしょ。


Ｂ．スキップ配列やメモ配列のサイズを小さくできる

　スキップ配列やメモ配列は目標値に応じて定義する必要があるので
　目標値が小さくなれば、それだけ小さくできます。
　逆に、要素と目標値が1,000円単位だったり100万円単位だったりすると
　0.04以前のバージョンでは悲惨なことになります。

　　#　「事前に最小単位で割ってください」といっても、きっと割ってくれないし。


Ｃ．再帰回数をびみょーに削れる

　課題Ａ，Ｂ，Ｃとも、再帰回数が気持ちだけ減っています。

　課題Ａの要素の最後は{…，1160，1140，780，560}なので
　26番目まで消化した時点で、残和が20で割り切れなければアウトです。

　課題Ｂの要素の最後は{…，13740，13140，12320}なので
　97番目まで消化した時点で、残和が20で割り切れなければアウトです。

　課題Ｃの要素の最後は{…，10544，10488，10442，10128}なので
　996目まで消化した時点で、残和が奇数ならばアウトです。

　そういうハナシ。

　　#　ただし、
　　#　親Ｐでの判定は【 必須 】なんだけど
　　#　子Ｐの方は、回数が減っても判定が増えて重くなるので、
　　#　速度的にメリットがあるかというと微妙。
-------------------------------　
●その他

・プロシージャ名を変更しました
・orgAryの用途が変わってます
　「割る前の値」⇒orgAry
　「ソート前の順序」⇒odrAry
88：_Kyle(1291004) :

2012/08/04 (Sat) 12:10:25

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344049826.gif ■R_ver.0.04
http://abyssinia2010.web.fc2.com/ssstmp/r0_04.txt

課題Ａ 　 　 　 　 　
　解の個数 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数 　 1,057 　 ⇒ 　 1,052 　 ( 100% )
　初期(msec.) 　 31 　 ⇒ 　 22 　 ( 71% ) ＼(^o^)／
　探索(msec.) 　 9 　 ⇒ 　 9 　 ( 100% )
　書出(msec.) 　 35 　 ⇒ 　 35 　 ( 100% )
　合計(msec.) 　 75 　 ⇒ 　 66 　 ( 88% )　＼(^o^)／　0.07秒切った！
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数 　 72,679 　 ⇒ 　 72,679 　 ( 100% )
　初期(msec.) 　 65 　 ⇒ 　 57 　 ( 88% )
　探索(msec.) 　 938 　 ⇒ 　 898 　 ( 96% )
　書出(msec.) 　 5,481 　 ⇒ 　 5,538 　 ( 101% )
　合計(msec.) 　 6,484 　 ⇒ 　 6,492 　 ( 100% )
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数 　 16,382 　 ⇒ 　 16,382 　 ( 100% )
　再帰回数 　 134,361 　 ⇒ 　 141,986 　 ( 106% )
　初期(msec.) 　 2,888 　 ⇒ 　 1,060 　 ( 37% ) ＼(^o^)／
　探索(msec.) 　 3,115 　 ⇒ 　 3,789 　 ( 122% )
　書出(msec.) 　 70,647 　 ⇒ 　 70,431 　 ( 100% )
　合計(msec.) 　 76,650 　 ⇒ 　 75,280 　 ( 98% )

=========================================
えー、たいしたハナシではないんですが、
課題Ａや課題Ｃのように、
要素の総和に対して初期目標値が大きい場合には
子Ｐを呼ぶ前に、初期処理の段階で『反転』しちゃえば
skpAryやmemAryのサイズを小さくできます。

課題Ｃの場合
(1 to 40,000,000)で定義すべきところが
(1 to 17,845,548)で済むというハナシです。

てか、0.01の段階でそうしとくべきだったんですが　(^^;;;

ちなみに、
子Ｐでは、最初の『反転』を行なう前に最初に使う要素を選びます。
初期処理で『反転』すると、最初に選ぶ要素が0.03と変わるので再帰回数も変わります。
課題Ｃでは、再帰回数がむしろ増えていますが、ここらへんは成り行きの問題で、
平均的には0.03より0.04の方が再帰回数は減るハズです。
87：_Kyle(1291004) :

2012/08/04 (Sat) 09:14:09

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344039249.gif ■R_ver.0.03
http://abyssinia2010.web.fc2.com/ssstmp/r0_03.txt

課題Ａ　
　解の個数 　 234 　 ⇒ 　 234 　 ( 100% )
　再帰回数 　 5,324 　 ⇒ 　 1,057 　 ( 20% )　＼(^o^)／
　初期(msec.) 　 24 　 ⇒ 　 31 　 ( 129% )　orz
　探索(msec.) 　 17 　 ⇒ 　 9 　 ( 53% )　＼(^o^)／10ミリ秒切ったぁ！
　書出(msec.) 　 35 　 ⇒ 　 35 　 ( 100% )
　合計(msec.) 　 77 　 ⇒ 　 75 　 ( 97% )
　 　 　 　 　
課題Ｂ 　 　 　 　 　
　解の個数 　 15,801 　 ⇒ 　 15,801 　 ( 100% )
　再帰回数 　 3,311,869　 ⇒ 　 72,679 　 ( 2% )　　＼(^o^)／10万回切ったぁ！
　初期(msec.) 　 57 　 ⇒ 　 65 　 ( 114% )　orz
　探索(msec.) 　 10,273 　 ⇒ 　 938 　 ( 9% )　　＼(^o^)／１秒切ったぁ！
　書出(msec.) 　 5,219 　 ⇒ 　 5,481 　 ( 105% )
　合計(msec.) 　 15,549 　 ⇒ 　 6,484 　 ( 42% )　 ＼(^o^)／10秒切ったぁ！
　 　 　 　 　
課題Ｃ 　 　 　 　 　
　解の個数 　 16,382 　 ⇒ 　 16,382 　 ( 100% )
　再帰回数 　 6,963,586　 ⇒ 　 134,361 　 ( 2% )　　＼(^o^)／100万回切ったぁ！
　初期(msec.) 　 333 　 ⇒ 　 2,888 　 ( 867% )　orz
　探索(msec.) 　 35,977 　 ⇒ 　 3,115 　 ( 9% )　　＼(^o^)／５秒切ったぁ！
　書出(msec.) 　 71,030 　 ⇒ 　 70,647 　 ( 99% )
　合計(msec.) 　 107,339 　 ⇒ 　 76,650 　 ( 71% )　 ＼(^o^)／90秒切ったぁ！


=========================================
wwwwwwwwwwwwwwww

劇的ですね。　
課題Ａ、探索時間10ミリ秒切ってるし。
課題Ｂも探索時間１秒切ってるし。
課題Ｃすら、探索時間３秒ちょっとって…。
こんなことならもっと早くやればよかった。orz　

『メモ化再帰』
知らなかったわけじゃないんですが、あまり深く考えずに
　「一々覚えてたらキリないだろ！」
って思ってました。

まぁ、実際、
　「残和xをn番目以降の要素で作る『作り方』を全部覚える」
ってのはメモリ的にどう考えても無茶なんですが
　「残和xをn番目以降の要素では『作れないこと』を覚える」
くらいならなんとかやれるみたいです。

　１．再帰呼出をかける前に、現時点の解の個数(rtnCnt)を覚える
　２．再帰呼出
　３．戻ってきた時rtnCntが増えていなければ
　　　「その枝には解がない」ということなので
　　　枝の入り口(残和-要素番号)を覚えて「塞ぐ」
　４．再帰呼出する前に、その枝が「塞がれていないこと」を確認する

枝(残和x，要素n)には「nを使わない枝」も包含されるので、
枝(残和x，要素n)がアウトなら
枝(残和x，要素n+1)も、枝(残和x，要素n+2)も、
「残和xをn番目【以降】の要素で作る」枝は全部アウトです。
ですから、xとnだけ覚えれば足ります。

直感に反して「その枝に解がある」ことを覚えるのは意味ないです。
解の「作り方」は覚えきれませんし、
解の「有無」を調べるだけであれば、
最初の解が見つかった時点で終わりです。
探索を端折ることはできますが、
仕様上、後で「作り方」を調べなおす必要あります。

一方、「解がない枝」を覚えておけば
枝(残和x，要素n)で解が【見つかった】場合も
その枝の分枝のうち「解に至らない枝」はすべて塞がれます。
したがって、再度、枝(残和x，要素n)を探索する場合
所要時間は大幅に短縮されることになります。

ただし、skpAryと同じく、
目標値と同じ要素数のLong型配列（課題Ｃなら要素数40,000,000!)を作る必要があるので、
かなりメモリは喰いますし、最初に値をitmCnt+1で埋める作業だけでも相当時間使います。

　#　う～ん、skpAryもそうだけど
　#　「要素数４千万の配列」ってちょっと、いやかなりバカっぽいなぁ。
　#　まぁ、皆さんお気に入りの「どーてきけーかくほー」の場合は
　#　【原理的に】「要素数４千万の配列」が要るんだけどね。

　#　Dictionaryとかどうなんだろうなぁ…。
　#　最初に有無を調べないといかん分、探索速度に響きそう。←試せよ。
86：_Kyle(1291004) :

2012/08/04 (Sat) 09:04:01

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344120777.png ■R_ver.0.02
http://abyssinia2010.web.fc2.com/ssstmp/r0_02.txt

課題Ａ 　 　 　 　
　解の個数 　 234 　 ⇒ 234 　 ( 100% )
　再帰回数 　 20,233 　 ⇒ 5,324 　 ( 26% ) ＼(^o^)／
　初期(msec.) 　 24 　 ⇒ 24 　 ( 100% )
　探索(msec.) 　 18 　 ⇒ 17 　 ( 94% )
　書出(msec.) 　 35 　 ⇒ 35 　 ( 100% )
　合計(msec.) 　 78 　 ⇒ 77 　 ( 99% )
　 　 　 　
課題Ｂ 　 　 　 　
　解の個数 　 15,801 　 ⇒ 15,801 　 ( 100% )
　再帰回数 　 17,324,071　 ⇒ 3,311,869　 ( 19% )＼(^o^)／
　初期(msec.) 　 49 　 ⇒ 57 　 ( 116% )
　探索(msec.) 　 11,142 　 ⇒ 10,273 　 ( 92% )
　書出(msec.) 　 5,201 　 ⇒ 5,219 　 ( 100% )
　合計(msec.) 　 16,391 　 ⇒ 15,549 　 ( 95% )
　 　 　 　
課題Ｃ 　 　 　 　
　解の個数 　 16,382 　 ⇒ 16,382 　 ( 100% )
　再帰回数 　 74,505,692　 ⇒ 6,963,586　 ( 9% ) ＼(^o^)／
　初期(msec.) 　 331 　 ⇒ 333 　 ( 101% )
　探索(msec.) 　 41,530 　 ⇒ 35,977 　 ( 87% )
　書出(msec.) 　 70,999 　 ⇒ 71,030 　 ( 100% )
　合計(msec.) 　 112,860 　 ⇒ 107,339 　 ( 95% )

=========================================
「潜る前に判定」です。

再帰回数大幅減！　＼(^o^)／

…のわりに、探索時間があまり減ってないのは、
「１階潜った後にやってた判定を、潜る前にやることにしただけ」
「全体の判定の数は変わってない／子Ｐの呼出コストが減っただけ」
だからです。

にしてもね、
たとえば課題Ａの場合、「２方向分岐の総当り」なら【 2^30=1.07E+09回 】呼ぶところを
【 5,324回 】で済ませてるのって我ながらちょっとしたもんだと思うのよね。

課題Ａ　2^30 =1.07E+09 回　⇒ 5,324回
課題Ｂ　2^100 =1.27E+30 回　⇒　3,311,869回
課題Ｃ　2^1000=1.07E+301回　⇒　6,963,586回　×

　　#　追記：課題Ｃは全部調べてるわけぢゃなかった;;;
　　#　　　　忘れてください　orz　8/5 07:52

コードにしてもさ
再帰呼出部分は50行足らず、全体でも200ちょっと超えたくらいだしね。
別にとりたてて凝ったことしてるわけじゃないし、つか、凝ったことできないし(^^;;;;　
85：_Kyle(1291004) :

2012/08/03 (Fri) 03:29:59

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343932199.png ＞DP系のver.6.20／ver.6.30の結果見ると
＞もしかしてジャグ配列よりStringの方が速いんじゃないかという疑惑(ぇ
＞そんなハズはないと思いつつも…う～ん。

そんなハズは無いですね(苦笑

旧ver.6.20より旧ver.6.30のが速いのは、
あのアルゴリズム(DP)では、ひたすら状態データのスワップを繰り返すので、
データサイズが小さい方が有利ってことだったようです。

反転しない場合であれば
"1","0"を直接リテラルで書き込めるので
「Boolean⇒ジャグ配列」とタメはる可能性もありますが(ぇ
反転する場合は、rvsFlgに応じて書き込む値を選ぶ必要があるので
String型で状態を管理するのはかなりキビシイです。

　#　って、んなことわざわざ確かめなくても…w

寝よう。

----------------------------

會澤、ヤバいんじゃないかと心配してたけど、大事に到らずよかった。
つか、「命に別状なくてよかった」なレベルだよね、アレ。
84：_Kyle(1291004) :

2012/08/03 (Fri) 01:46:04

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343925964.gif ■R_ver.0.01
http://abyssinia2010.web.fc2.com/ssstmp/r0_01.txt

課題Ａ 　 　 　
　解の個数 　 234 ⇒ 234 　 ( 100% )
　再帰回数 　 20,233 ⇒ 20,233 　 ( 100% )
　初期(msec.) 　 23 ⇒ 24 　 ( 104% )
　探索(msec.) 　 19 ⇒ 18 　 ( 95% )
　書出(msec.) 　 35 ⇒ 35 　 ( 100% )
　合計(msec.) 　 78 ⇒ 78 　 ( 100% )
　 　 　
課題Ｂ 　 　 　
　解の個数 　 15,801 ⇒ 15,801 　 ( 100% )
　再帰回数 　 17,324,071 ⇒ 17,324,071 　 ( 100% )
　初期(msec.) 　 43 ⇒ 49 　 ( 114% )
　探索(msec.) 　 12,083 ⇒ 11,142 　 ( 92% )
　書出(msec.) 　 5,238 ⇒ 5,201 　 ( 99% )
　合計(msec.) 　 17,365 ⇒ 16,391 　 ( 94% )
　 　 　
課題Ｃ 　 　 　
　解の個数 　 16,382 ⇒ 16,382 　 ( 100% )
　再帰回数 　 74,505,692 ⇒ 74,505,692 　 ( 100% )
　初期(msec.) 　 170 ⇒ 331 　 ( 195% )
　探索(msec.) 　 43,723 ⇒ 41,530 　 ( 95% )
　書出(msec.) 　 70,663 ⇒ 70,999 　 ( 100% )
　合計(msec.) 　 114,556 ⇒ 112,860 　 ( 99% )

=========================================

再帰呼び出し中にループでスキップ先を判定するのは重たいので
あらかじめ残和に応じた跳び先を調べておこうというハナシです。

探索時間【　５％　】削減に成功！　←びみょーｗ

　※ただし、誤差ではなく、はっきり有意な差です。

無論、スキップ先配列を作るために初期処理に要する時間は増えてますが
課題Ｃでも0.2秒ほどの差です。むしろメモリの方がキツいかも…。

コーディング的には
　Ｂ案：　If×２　（ヒット判定と最小要素判定をそれぞれ別個に）
　Ｃ案：　Select Case　（ヒット判定と最小要素判定をまとめて）
　Ｄ案：　Ifネスト　（スキップ・選択ブロックもIfに埋め込む）
も試しましたが
　Ａ案：　If ～ Elseif
が速いみたいです。(呼び出し負担の問題？）

あと、
↓で「最小要素判定要らなくなるし」とかほざいてますが…要りました。orz　
残和が思いっきり負になる瞬間があるので。
83：_Kyle(1291004) :

2012/08/03 (Fri) 01:04:52

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343923493.gif ■R_ver.0.00
http://abyssinia2010.web.fc2.com/ssstmp/r0_00.txt

課題Ａ 　 　
　解の個数 　 234 　
　再帰回数 　 20,233 　
　初期(msec.) 　 23 　
　探索(msec.) 　 19 　
　書出(msec.) 　 35 　
　合計(msec.) 　 78 　
　 　
課題Ｂ 　 　
　解の個数 　 15,801 　
　再帰回数 　 17,324,071 　
　初期(msec.) 　 43 　
　探索(msec.) 　 12,083 　
　書出(msec.) 　 5,238 　
　合計(msec.) 　 17,365 　
　 　
課題Ｃ 　 　
　解の個数 　 16,382 　
　再帰回数 　 74,505,692 　
　初期(msec.) 　 170 　
　探索(msec.) 　 43,723 　 ←書出時間よりも短いことに注目！
　書出(msec.) 　 70,663 　
　合計(msec.) 　 114,556 　

=========================================

叩き台…つか、ほぼ旧ver.0.80のままデス。
　・再帰
　・多方向分岐
　・降順ソート
　・潜ってから判定
　・スキップ(順次判定)
　・反転
タイマとかカウンタとか残してあるのは仕様デス。

ちなみに、RはRecursiveのRね。
82：_Kyle(1291004) :

2012/08/01 (Wed) 06:14:15

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344359232.gif 朝起きて、昨晩書いたものを見直したら、
何書いてるのか自分でさっぱりわからんといういつもの流れ　orz
----------------------------
んっと…

　要素：　=(INT(RAND()*10000)+1)*10　×1,000コ
　目標：　=SUM(B:B)/2+1

の場合

ver.6.40（なんちゃって動的計画法）であれば
「解が無いこと」が分かるのに手元のノートで10分程度やね。
ファンがガラガラうるさいけどww

ちょこっとイジれば「目標値以下の最近似解」も出る。

その時点の「ベストスコア(最小誤差)」をステイタスバーに表示するのもアリかな。

　#　↑前に回答でやったことがある気が。
　#　「誤差が十分小さくなった時点で手動でESCしてください」
　#　みたいなwwww
---------------------------------
でも、まとめ用メモに書いた
「最初にDPで解の有無を調べてから…」ってのはどうだかなぁ。

課題Cみたいなパターンだと、
DPが最初の解見つけるまでにン十分もかかる一方、
再帰なら２分で１万６千見つけちゃうもんなぁ…。
予備探索にならん。

　#　あ、今気付いたけど、ver.6.40は反転しないから課題C遅いのか。
　#　反転すれば１０分切るな、たぶん。

「DP⇒再帰」ではなくて「再帰⇒DP⇒再帰」にするかな。
再帰でちょろっと回して解が見つからないようなら
「動的計画法(Dynamic Programming)による探索に切り替えますか？（ワライ）」
みたいなMsgbox出すとかww

DPで解ナシ
　⇒　最近似解を表示して終了
DPで解発見
　⇒　「分割統治法(Divide and conquer algorithm)による探索を再開しますか？（ワライ）」
==================================
メモ　φ(..)

ver.6.40（なんちゃって動的計画法）

アルゴリズムはともかくとして
コーディング上はもうちょい速くなりそうな雰囲気。

未だに何やってるかわからんけど(ぉぃ　…解読しなきゃ。

あと、たぶん
　○ver.6.40
　×ver.6.50
「できて無いもの」の方が圧倒的に多いわけだから。

●ソート（コード上でw）

　意味あるかな？　ある…と思う。

　「既にできてるものを作る」のがロスになるんだから
　早い段階で、大きい数字で大きい値をまんべんなく作っておいてから
　小さい数字で隙間を埋めていく方が…。

　でも、端から端まで調べてるわけじゃないから、
　最悪計算量を考えると、小さい値をまずみっちり埋めてった方が…なのか。
　すると…昇順ソート!?

　　#　走らせてみればわかるだろ　＞私

●近似解表示

　「ベストスコア(最小誤差)」をリアルタイム表示。
　終了時に近似結果を書出し。

　まぁ、DPでやる以上は近似解表示しないとメリットないんだけど
　　・目標値以上で誤差最小
　　・目標値以下で誤差最小
　　・差分が最小
　実務上どれもありうるし、事前に設定させるとなるとなぁ…。
　以上・以下、両方表示？

●反転する

　最初の反転はまぁ、いいとして。

　途中でやるのどうやるんだろ？　…つか、可能？？
　いや、「残和」って概念がないから、そもそも意味ないのか。

　最初だけ反転。

●公約数問題

　…は対応した方がいいよね。メモリのこともあるしね。

●剰余類

　剰余類に分けて調べる(下記参照)のはどうなんだろ？
　計算量減るかな？　減るよね？　減るに違いない！(ぇ

　再帰の場合とは逆に、まず飛び飛びで積んで、
　あと細かく埋めてく感じになるのかな。

●整数化

　これは公約数判定とは別個に、早い段階で要るよね。

●０値除外

　これも早めに入れとこう。　
--------------------------
ver.0.80(再帰系現状最速)

●近似解表示

　表示も書出しも、実装は難しくないけど…

　速度上は負担になるよね、やっぱ　orz
　その時点での最小誤差を覚えて、その都度残和と比較して…
　オマケに、最適解が見つかった後も判定が残る。ぅぇっ

　　#　「判定スキップすれば…」みたいなこと言わないように。＞未来の私
　　#　「判定スキップする判定」がいるでしょ。

　　#　あ、「目標値以上で誤差最小」を判定するのって実装上も結構手間だな。

×結果管理の再検討

　DP系のver.6.20／ver.6.30の結果見ると
　もしかしてジャグ配列よりStringの方が速いんじゃないかという疑惑(ぇ
　そんなハズはないと思いつつも…う～ん。

　　　#追記：そんなハズはありませんでしたww

　いっそ静的に宣言しちゃえば、ってハナシもあるよね。

○残和に応じたスキップ先を事前に調べて配列に格納しておく

　エレファントって言われそうな悪寒　orz

　 # 皆さんお気に入りの動的計画法だって
　 # 【 原理的に 】[要素数が目標値の配列]使うんだけどな。

　でも速くなるハズ。

　×最小要素判定要らなくなるし。　#　←追記：寝言でした
　○スキップ判定要らなくなるし。←でも埋めるの忘れないように。

　　#　R0_01で実装。

○コード上でソートｗ

　ワークシート上でソートしてから格納って…orz
　クイックソートくらいさらっと書きたいよね。

　　#　R0_08で実装。引き写しだけど　orz

○判定してから潜る

　判定してから潜ると、再帰数：ループ数が揃わないんだっけ？？？
　コーディングの問題？？？

　もし不可避なら、「まとめ」ではやはり最後に実装やね。

　　#　R0_02で実装。

○公約数判定

　最初、要素数×要素数の２次元配列作るかなぁと思ってたけど
　公約数の数だけ列用意してカウントアップしてけばいいよね。
　たいていは「無い」んだし。

　でもまぁ、おおごとになるのは確かなので、「まとめ」ではやはり最後に実装。

　　#　R0_05で実装。

●整数化

　これは公約数判定とは別個に、早い段階で要るよね。

●０値除外

　これも早めに入れとこう。

○メモ化

　「残和xをn番目以降の要素で作る作り方」
　を覚えるのはメモリ的に無理っぽいし、無駄多そう。

　でも
　「残和xをn番目以降の要素で作れないこと」
　を覚えるのはやれそうだし、計算量減りそう。

　目標値×要素数の配列作るのはアレなので
　残和毎に
　「それ以降の要素を使って残和を作れる【 可能性のある 】最小のｎ」
　を覚えるとか。

　　#　R0_03で実装。

●残和の剰余で分岐（高機能版？）

　要素を2,5,10^nで割り切れるか否かで

　一群：{2,5で割り切れない要素(5の倍数でない奇数)}
　二群：{2で割り切れ、10で割り切れない要素(5の倍数でない偶数)}
　五群：{5で割り切れ、10で割り切れない要素}
十群：{10で割り切れ、100で割り切れない要素}
　百群：{100で割り切れ、1000で割り切れない要素}

　等にグループ分けしておき、目標値の端数を要素の端数で作ってく。

　一群で作り始めて
　「一群」で残和が2で割り切れたら「一群で作り続ける枝」と「二群で作る枝」に分岐
　「一群」で残和が5で割り切れたら「一群」「五群」に分岐
　「二群」で残和が5で割り切れたら「二軍」「五群」に分岐

　「お釣りが無いよう16584円払うとき、1円玉４つなかったら即終了」
　みたいなハナシ。

　…実装が　orz
　---------------------------
　いや、いっそ、再帰的に処理したらどうよ。

　Ａ．要素を{偶数}と{奇数}に分ける
　Ｂ．目標値(残和)が奇数なら{奇数}で作る　←いつか必ず一つは奇数使うわけだから。
　Ｃ．目標値(残和)が偶数なら{奇数}で作る枝と{偶数}で作る枝に分岐
　Ｄ．{偶数}で作る枝に分岐したら、残和と要素を２で割ってＡに

　【偶数は、残和が偶数のときだけ使う】

　直感的には計算量かなり減る気がするんだけど…減るかな？　減るよね？

　早速書いてみたいけど、腕が錆ついて、グギギギギィィィ
81：_Kyle(1291004) :

2012/07/31 (Tue) 01:08:36

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343664516.png あー、たとえば…

　・N-1番目までの要素は３の倍数
　・N番目(最終)の要素が４
　・目標値を３で割ると２余る

みたいな状況も作ればあるか。

そうすると、最初だけ申し訳程度に判定して
「要素が100刻みなのに目標値が端数」
みたいなケースだけハジけばいいのかな。
80：_Kyle(1291004) :

2012/07/30 (Mon) 22:25:38

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343659111.png ■雑多の数値データを元に…
http://park7.wakwak.com/~efc21/cgi-bin/exqalounge.cgi?print+201110/11100019.txt

１年近くも前のネタを、コードも読まずに騙るかね？　＞私

こいつは…
ぱっと見た感じ「部分和問題(subset sum problem)を連続的に解く」課題のように見えますし、
質問の【 字面上は 】それで要求仕様を充たしますが
最終的には
瓶詰問題(bin packing problem)とか
板取り問題(cutting stock problem)とか
に移行しそうな悪寒。

質問者御自身はたぶん意識してないでしょうけど、こういう課題の場合
ある目標値について誤差０であることが、全体としてベストであるとは限りませんからね。
「最初の目標値で妥協した方が、後々有利になる」みたいなことが起こりうるので。

たとえば、
　要素群{24,20,4,3}から、目標値{28,25}を、誤差±１で作る
みたいな場合

結果Ａ：{24,4}誤差0,{解なし}
結果Ｂ：{24,3}誤差1,{20,4}誤差1

どちらの結果が欲しいかと訊けばたぶんＢって言われるわけで、結局後出しで
「全体として【 より多くの目標値を誤差以内でクリア 】できるように…」
みたいに要求仕様が変更される可能性大。

=====================================================

で、仮に、質問の字面通り

　「部分和問題(subset sum problem)を連続的に解く」

課題だとして…。

=========================

　>対象群が全て偶数で目標数値が奇数だったら

コレは、

■ver.0.81：　最初だけじゃダメ？
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5545512

　>「突っ込み」「揚げ足取り」といえばもう一点、
　>誰でも思いつく…もとい、誰もが試したくなるケースがありますよね(^^;;;;
　>
　>それは次回。

と言っておきながらその「次回」が来なかったヤツですね^^;;;;;;

幻のver.1.00

　●未使用要素の最大公約数で未使用要素と残和を割る
　●未使用要素の最大公約数で残和が割り切れなければアウト

むろん、その都度最大公約数を求めるわけにはいきませんし
「反転」と同じく、最初の１回だけチェックしても意味ないので、

あらかじめ
「n番目以降の要素の最大公約数の配列」
「n番目以降の要素の最大公約数でn番目以降の要素を割った配列」
「n番目以降の要素の最大公約数で後方部分和を割った配列」
等々を準備しておくわけです。

　>対象群の個数、最小値と最大値、重複の有無（ユニーク数）

にもよりますが、公約数問題に対応しちゃえば、

一般的に

　・解が無いほど、要素が少ないor目標値が小さい　⇒　舐め尽くせる
　・舐め尽くせないほど、要素が多いand目標値が大きい　⇒　解がある

というケースがほとんどじゃないかと…。

　#「重複」は極端な場合には問題あるかも。
　#でも「内訳推定」課題を想定してるから、同額の要素が多い場合には
　#そもそも課題が発生しないのよね。
　#
　#「980円の商品が600種類ある」場合に
　#「合計額と単価から内訳推定しよう」なんて発想しないし。

=========================

そいから、
　・解の有無を調べる
　・一つだけ解を求める
　・近似解を求める
ような場合には誠に遺憾ながらw　動的計画法のが断然有利ですね。
つか、そのための動的計画法だし。

「まとめ」高機能版では、動的計画法であらかじめ解の有無and最近似解を求めてから
再帰なりループなりで複数の解を探索するプランです。

=========================

YUJI氏

　>>156　解なし
　>70 + 86 で156になります。

wwwww

…はぁ。私だったらキレてますね。
79：_Kyle(1291004) :

2012/07/30 (Mon) 04:32:04

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343590325.png ●解法

　A,B系　再帰,ループ

　　0.00　総当たり　※最初から「潜る前」判定で！

　　0.01　進捗表示
　　0.02　終了処理
　　0.03　ESC
　　0.04　終了／中断表示

　　0.10　残和零or負で戻る

　　0.11　Integerを使う理由はない
　　0.12　Variant型大量読み書きはマヌケ
　　0.13　もちろんBoolean型の方が速い
　　0.14　子Ｐの記述は簡潔な方が有利
　　0.15　最後に一気に書き出す
　　0.16? ※String試せ

　　0.20　約分・整数化
　　0.30　多方向分岐
　　0.40　どれ使っても足りんならアウト
　　0.50　ソート　※０値があればitmCnt削れ！
　　0.60　どれ使っても超えるならアウト
　　0.70　残和以下までスキップ　※回すな！残和→要素対応配列作れ！
　　0.80　反転
　　0.90　カウンタ・タイマ除去

　C系　数値割当総当たり

　　0.00　Long型割り当て
　　0.10　Boolean型割り当て

　D系　動的計画法

　　0.00　ナップザック問題をExcelで解く
　　0.10　『DPSforExcelVBA』
　　0.20　下書ver.6.40
　　0.30　下書ver.6.50

　E系　高速低機能版

　　0.00　A系0.80

　　0.01　カウンタ除去
　　0.02　進捗表示ナシ
　　0.03　終了処理ナシ(ぇ
　　0.04　End抜け
　　0.05　終了／中断判定ナシ

　　0.10　事前手動約分
　　0.11　事前手動ソート

　　0.20　DP判定

　　0.90　タイマー除去

　F系　最少再帰

　　0.00　下書0.8b?

　G系　高機能低速版　※売る？ｗ

　　0.00　A系0.90
　　0.01　コード上でソート
　　0.02　配列受け⇒配列渡し
　　0.03　DPで解の有無を事前判定
　　0.04　DPで近似解を探索
　　0.05　件数上限
　　0.06　重複使用対応
　　0.07　使用要素数制限
　　0.08　使用要素最少・最多探索
　　0.09　書出順設定
　　0.10　除外・必須要素設定

　M系　打鍵猿

　　0.00　馬鹿猿
　　0.01　お利口猿

　Q系　シンプル版

　　0.01　ループ
　　0.02　多方向
　　0.03　不足
　　0.04　スキップ

　S系　ソルバー

　　0.00　ソルバー
78：_Kyle(1291004) :

2012/07/30 (Mon) 04:21:57

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1343589717.png あ、いや、「まとめる」というハナシではなくて…
「まとめるとすれば…」のハナシ。

●動作仕様

　A列　　項目列
　B列　　結果表示
　C列　　要素
　D列～　解書出

　B1　目標値
　B2　解の個数(～個／～個以上)
　B3　初期処理時間
　B4　探索時間
　B5　書出時間
　B6　総所要時間
　B7　単位探索時間　※msec表示に
　B8　再帰／ループ数

●課題

　・要素は60の倍数に
　課題Ａ：qa5212312
　課題Ｂ：要素数 30，解 200程度
　課題Ｃ：要素数 百，解 16000程度
　課題Ｄ：要素数 千，解 大量
　課題Ｅ：要素数 万，解 若干数
77：_Kyle(1291004) :

2010/06/11 (Fri) 16:37:21

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276241842.png …仕事しろ！　＞わたし
76：_Kyle(1291004) :

2010/06/11 (Fri) 04:06:05

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276196765.gif …寝ろ！　＞　わたし
75：_Kyle(1291004) :

2010/06/11 (Fri) 02:09:18

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276194618.gif ようやく「.80問題」が解決(?)したので、
ようやく「潜る前判定」へ行けますw

===================

…ver番号が足りなくなる悪寒(汗
まとめるときは桁一つ下げよう(ぉ
74：_Kyle(1291004) :

2010/06/11 (Fri) 02:02:31

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276189351.gif ■ver.5.80
http://abyssinia2010.web.fc2.com/ssstmp/ver5_80.txt

「潜ってから判定」です。

●所要時間（内探索時間）

　課題Ａ
　　5.70　0.240秒(0.176)
　　5.80　0.142秒(0.084)

　課題Ｂ
　　5.70　29.436秒(24.780)
　　5.80　31.104秒(25.993)

　課題Ｃ
　　5.70　135.255秒(_78.523)
　　5.80　175.958秒(100.350)

●解一つあたりの探索時間

　課題Ａ
　　5.70　0.0010256秒
　　5.80　0.0006068秒

　課題Ｂ
　　5.70　0.0018629秒
　　5.80　0.0019685秒

　課題Ｃ
　　5.70　0.0082563秒
　　5.80　0.0107409秒　

●再帰回数

　課題Ａ
　　5.70　157,141回
　　5.80　_40,465回

　課題Ｂ
　　5.70　42,693,713回
　　5.80　34,648,141回

　課題Ｃ
　　5.70　151,844,359回
　　5.80　149,011,187回

=======================================

ver.0.80との比較

●所要時間（内探索時間）

　課題Ａ
　　0.80　0.129秒(0.069)
　　5.80　0.142秒(0.084)
　　110%(120%)

　課題Ｂ
　　0.80　16.736秒(11.587)
　　5.80　31.104秒(25.993)
　　190%(220%)

　課題Ｃ
　　0.80　108.727秒(40.377)
　　5.80　175.958秒(100.35)
　　160%(250%)

書出しだけでなく初期処理にも時間もかかってるから
本当は回してる部分の時間測って、
再帰数・ループ数で割らないと比較にならないけど…。

●再帰回数

　課題Ａ
　　0.80　20,233回
　　5.80　40,465回

　課題Ｂ
　　0.80　17,324,071回
　　5.80　34,648,141回

　課題Ｃ
　　0.80　_74,505,692回
　　5.80　149,011,187回

ちゃんと揃っとりますね。
73：_Kyle(1291004) :

2010/06/11 (Fri) 02:01:42

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276241499.gif ■ver.0.80
http://abyssinia2010.web.fc2.com/ssstmp/ver0_80.txt

あらためて。

再帰・ループに関わらず
「反転した方が遅くなることがある」
これはまぁ、仕方ないんです。
一回あたりの処理が重くなるんですから。

再帰・ループに関わらず
「反転処理は不可欠」
これもまぁ、仕方ないんです。
反転しないと人間に負けちゃうことがありますから。

ただね「遅くなり方」が不自然で、それで悩んでたんですよね。
課題Ｃはあまりに遅くなりすぎるし、
なんで探索時間だけでなく「書出し時間」に差が出るんだと。

…使用要素の数が違うんでした　o .............rz

==================================================

「大きいものから使う」というのは
結果として概ね「使用要素の少ない解から探す」ことになります。

一方

「残が大きい場合に反転する」というのは
結果として概ね「選択要素の少ない解から探す」ことになります。

ver.X.70以前の場合は「選択要素」＝「使用要素」ですが
ver.X.80では、反転状態によって
「選択要素」＝「使用要素」のときと
「選択要素」＝「非使用要素」のときがあります。

で、
「大きいものから選択する」and「反転する」というのは
結果として概ね
「選択要素の少ない＝非使用要素の少ない＝使用要素の多い解から探す」
ことになります。

というわけで
「すべての解を表示する」課題Ａ，Ｂはともかくとして
「先に見つけた解16382件を表示する」課題Ｃの場合は
使用要素の多い解から先に見つかるので、
書き出す部分について、要素が増える結果、
表示に時間がかかるというハナシでした。

　#　メモリ関係を疑ってたのよね。

==================================================

微妙に修正しましたが
バージョン番号は変更ナシ。

　・一回きりだし、IIf使ってもいいと思うのよね。
　・十分に速くなったので進捗表示を100件おきに。
　・REMを簡潔に。

「潜ってから判定」です。

●所要時間(内探索時間)

　課題Ａ
　　0.70　0.197秒(0.131)
　　0.80　0.129秒(0.069)

　課題Ｂ
　　0.70　17.498秒(13.862)
　　0.80　16.736秒(11.587)

　課題Ｃ
　　0.70　_93.980秒(37.553)
　　0.80　108.727秒(40.377)

●解一つあたりの探索時間

　課題Ａ
　　0.70　0.0008419秒
　　0.80　0.0005513秒

　課題Ｂ
　　0.70　0.0011074秒
　　0.80　0.0010592秒

　課題Ｃ
　　0.70　0.0057368秒
　　0.80　0.0066370秒　

●再帰回数

　課題Ａ
　　0.70　78,571回
　　0.80　20,233回

　課題Ｂ
　　0.70　21,346,857回
　　0.80　17,324,071回

　課題Ｃ
　　0.70　75,922,432回
　　0.80　74,505,692回
　※最初の1万6千件についてはあまり差がでないけど
　　もし仮に「すべての解を探索する」としたら
　　圧倒的な差が出る…ハズ。
72：_Kyle(1291004) :

2010/06/11 (Fri) 01:53:28

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276188808.png スミマセン　o　　　　　　.......rz

　#　すぐにアップするつもりのものが他にいくつかあって
　#　まとめて上げようとおもってたんですけど直前に変更入ってあたふたしてるうちに…

　【　言い訳するな！！　】

orz
71：end-u(1037781) :

2010/06/11 (Fri) 01:45:16

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276188317.jpg 添削希望 :D
そういうの好きです。
自分のコード弄られるのは全然気にならないほうですしｗ

でも肝心のページが

>404Error - Page not found

...拒否られてる...orz
70：_Kyle(1291004) :

2010/06/11 (Fri) 00:17:25

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276183045.gif ぇっと、添削とかそういうんじゃないです(^^;;;;
あくまで「try」っつーことで。

　●try3：　「一歩前へ」
　http://abyssinia2010.web.fc2.com/ssstmp/try3.txt

　　# Ifブロックの書き方がいかにも冗長 (ーー;)
　　# もっとスマートな書き方がきっとある…　orz

課題Ａ 44,302
課題Ｂ 25,038,952

ちなみにExcel2003で
　課題Ａ　0.057秒
記録してますw

「スキップ」すればもっと減りますね。

====================================

　#　今気付いたけど(ぇ
　#　「要素に０が含まれる場合」の動作がバージョン毎に違うな。

　#　0.40以前「ヒットするまでは0も選ぶけど、ヒット以降は無視」
　#　0.50以降「0は選ばない」

　#　0.40以前の中途半端な動作はなんかバグっぽい。
　#　まぁ、「正整数」って断ってあるんだけど…。　
69：_Kyle(1291004) :

2010/06/10 (Thu) 01:38:24

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276101505.gif 茶茶大感謝です。大変勉強になりました。　<(_ _)>

独りで書いてるとつい
「これが最速のハズ」「これが最善のハズ」「必然的にこうなる」
みたいに思い込んじゃうことが多いので
違う視点からの指摘やアドバイスは大変有難いです。

「混乱」しちゃったのは、
興味深いポイントが沢山あって追試や確認でバタバタしちゃったという次第で
それだけ中身の濃いレスだったということで(^^

　#　本当の「混乱の元」はver5_80の不審な挙動だったり　orz

----------------------------

■Loopのみ回数に言及しても

ぃゃ、50,896回という数字は正直おどろきで、目が覚める思いでした(^^

　#　…ジツは「潜る前判定」のハナシ、忘れかけてたんですよね(ぉぃ
　#　最初の段階で試したときはあんまり差が出なかったし…(ｿﾘｬｿｳﾀﾞ

lv の使い方も当初誤解してたんですが、気付いてみれば目からウロコでした。
（　でもわたし的には.bckで呼び元覚えとく方がわかりやすい　orz　）

----------------------------

■「使った要素の番号と個数を覚える」

bufAry倒す必要がなくて凄く便利なので、
なんとか生かせないかなぁとただいま思案中です。

----------------------------

■【判定してから潜る】

>上の階層に抜けるタイミングを、
>先にもってきてみただけだったんですが。

そです。

たとえば
「残ありで次階層へ」となってる部分を、いっそのこと
「残が最小要素以上で次階層へ」としちゃえば

　●try2：　「残が最小要素以上で次階層へ」
　http://abyssinia2010.web.fc2.com/ssstmp/try2.txt
　　#　結果は合ってるようだけど、ちょっと不安(ぉぃ

それだけで
　課題Ａ　44,469回
　課題Ｂ　25,083,260回
になりますよね。

同じ要領で、【いっそのこと全部】
上に抜けるタイミングを前倒しにしちゃえば…というハナシです。

でも、わたしがやるとこんがらがらがらwwww

「【もし】これを使うとアウト」と考えるより
「【いま】この状態はアウト」と考える方が判りやすいんですよね。

----------------------------

■>Loop回数を減らすより、Loop内判定をいかにシンプルにするか

そですねー。
再帰の方はステップ数だけでなく構文サイズも絡んでくるのでさらにシビアです。

電車の中で何か思いついて「やった！＼(^o^)／」と思っても
いざ実装してみたらかえって遅くなったり…。

やっぱコーディングって大事だ　orz
68：end-u(1037781) :

2010/06/09 (Wed) 23:11:16

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276092676.jpg ヨコから妙な茶々入れしたみたいで混乱の元を作ってしまいました。
再帰に合わせたLoopロジックの比較だったのに
Loopのみ回数に言及しても意味なかったですよね。
重ねてごめんなさい。m(_ _)m


それにしても、素晴らしいコーディングスキルですね。
羨ましいです。
「反転」は考えてなかったんで安易に
「使った要素の番号と個数を覚える」方式にしたんですが
浅はかですねー…反省。


【判定してから潜る】...と言われればそうなんでしょうか。
私もこんがらがってて深く理解できてません。
上の階層に抜けるタイミングを、先にもってきてみただけだったんですが。


Loop回数と所要時間についてはなかなか興味深い結果となってますね。
Loop回数を減らすより、Loop内判定をいかにシンプルにするかに注目したほうが良さそうです。


まだまだ進化しそうですね。
私も別アプローチで実験してみたいと思ってます。
またしばらく勉強させてください :D
67：_Kyle(1291004) :

2010/06/09 (Wed) 18:40:39

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276076626.gif 速度とかコーディングとか、もろもろ度外視でw

　●ver.0.8b：　暫定最少再帰
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_8b.txt

　●ver.5.8b：　暫定最少ループ
　http://abyssinia2010.web.fc2.com/ssstmp/ver5_8b.txt

=======================================

課題Ａ

　0.7b　0.186秒　17,130回
　0.8b　0.173秒　_5,979回　←１万切った！　＼(^o^)／

　5.7c　0.176秒　40,788回
　5.8b　0.177秒　18,541回　←２万切った！　＼(^o^)／

課題Ｂ

　0.7b　14.492秒　_4,851,070
　0.8b　15.919秒　_4,027,452

　5.7c　22.940秒　19,040,609
　5.8b　23.530秒　17,394,156

課題Ｃ

　0.7b　_83.941秒　_6,804,890
　0.8b　_95.331秒　_6,713,035

　5.7c　115.897秒　75,315,890
　5.8b　123.929秒　74,855,255

=======================================

時間的には軒並み遅くなっとります　orz
でも、いずれにしろ「反転」は要るのよね。

結果の管理方法考えなくちゃ。
66：_Kyle(1291004) :

2010/06/09 (Wed) 08:40:01

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276042735.png …がら。　orz

　●ver.5.7c：　「潜る前に判定」／追いついた？
　http://abyssinia2010.web.fc2.com/ssstmp/ver5_7c.txt

ループ回数は追いついた…けど無理矢理　orz

　●ver.5.7d：　「潜る前に判定」／階層を跳ばない
　http://abyssinia2010.web.fc2.com/ssstmp/ver5_7d.txt

こういう理解であってるかしらん？

「使った要素の番号と個数を覚える」
フラグ倒さなく良いので凄く便利ですね　＼(^o^)／
...でも反転するとき困る　orz

課題Ａ

　5_70 0.235秒　157,141回
　5_7b 0.178秒　_57,918回
　5_7c 0.176秒　_40,788回
　5_7d 0.168秒　_44,331回

課題Ｂ

　5_70 32.573秒　42,693,713回
　5_7b 21.912秒　23,891,679回
　5_7c 22.940秒　19,040,609回
　5_7d 19.113秒　22,165,080回

課題Ｃ

　5_70 150.580秒　151,844,359回
　5_7b 106.414秒　_82,120,276回
　5_7c 115.897秒　_75,315,890回
　5_7d _98.527秒　_81,509,281回
65：_Kyle(1291004) :

2010/06/09 (Wed) 02:38:34

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276018714.png 一体どこでbuf倒してるんだろうと思ったら…
使った要素の番号を上から詰めてるんですね。

で、lvの意味を根本的に取り違えてました　orz

これは……わたしには当分無理かも　(T_T)

寝よう。
64：_Kyle(1291004) :

2010/06/09 (Wed) 01:55:39

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276016137.gif ＞使用要素数もついでに格納し書き出し時に利用。

ナルホド！　これは判りますｗ　＼(^o^)／

…でも「反転」したとき困る　orz
63：_Kyle(1291004) :

2010/06/09 (Wed) 01:38:00

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276015078.png ぇっと、あらためまして、いらっしゃませ！　＼(^o^)／

■>ひょっとして、このロジックだとかえって遅くなるからあえて

ぃぇ、深い意図はないデスw

「再帰でやれることはループでもやれる」ということがわかったので
とりあえず再帰と同じカタチで行けるところまで行ってみようと…。

「まとめ」るときに、再帰とループ、並べて紹介しようというつもりもあったり。

「ループ回数」：「再帰回数」の記事内容は
「揃う」というより「揃えた」というニュアンスで書くべきでしたね。

　#　独り合点して勝手にガチャガチャいじって
　#　問題を長引かせるアレな質問者の典型　orz

=======================================

■>Sub try

例によって解読ちう　orz

…なんですが、ひょっとして【判定してから潜る】ですか？

　#　回答きちんと読まずに勝手に独り合点して(ry　orz

だとしたら

　●ver.0.00：　再帰で「総当り」
　http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5392769

でもｺｯｿﾘ触れてたんですが、
「このロジックだとかえって遅くなるからあえて」ではなくて
「このカタチの方が（わたし的に）コーディングしやすいから」です。　o ....rz

潜る前に判定すると絶対混乱しそうな気がしたので
とりあえず書きやすい形で判定だけ増やしていって
最終的に直せるようなら直そうと…。

全然違うハナシでしたらスミマセン。
時間出来次第きちんと読みますので…。

…違うハナシですね。
跳ばずに１階ずつ戻ってるのになんでこの数字が出るんだろ？？
おーばーてくのろじー？？

=======================================

で、「判定してから潜る」ハナシですが、

ver.0.00では

　>　倍呼ぶと言っても、どうせ次の最初でトラップするので
　>　実質的な負担はそれほど変わりません。

とか書いてますが、これもジツは真っ赤なウソで、
たしかにこの段階では、他にいろいろ余計なコストがかかってますから
大勢に影響はないんですが、現時点ではかなり効きますね。

　●ver.0.7b：　「潜る前に判定」
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_7b.txt

　●ver.5.7b：　「潜る前に判定」
　http://abyssinia2010.web.fc2.com/ssstmp/ver5_7b.txt

　#　やっぱり混乱した　orz

　#　sumAryの作り方間違えて、小一時間…(死
　#　フラグの倒し方間違えて、小一時間…(滅
　#　カウンタの置き方間違えて、小一時間…(欝

=======================================

　課題Ａ
　　5.70：　0.240秒(0.158秒？)　／　157,141回　
　　5.7b：　0.218秒(0.136秒)　／　57,918回

　　0.70：　0.197秒(0.131秒？)　／　78,571回
　　0.7b：　0.186秒(0.120秒)　／　17,130回

　課題Ｂ
　　5.70：　29.436秒(22,947秒？)　／　42,693,713回
　　5.7b：　22.409秒(15.920秒)　／　23,891,679回

　　0.70：　17.498秒(12.469秒？)　／　21,346,857回
　　0.7b：　14.492秒(9.463秒)　／　4,851,070回

　課題Ｃ
　　5.70：　135.255秒(72.198秒)　／　151,844,359回
　　5.7b：　105.671秒(42.614秒)　／　82,120,276回

　　0.70：　93.980秒(32.461秒)　／　75,922,432回
　　0.7b：　83.941秒(22.422秒)　／　6,804,890回

　※カッコ内は表示サブを呼ばない場合の正味探索時間です。

　　#　…思ってた以上に速い　orz

　　#　再帰系、Ｂは正味10秒切ってるし、Ｃは正味20秒ちょいって。
　　#　ループ系も、Ｂ正味15秒、Ｃ正味40秒かよ！

　　#　とりあえずは枝バージョンの扱いですが、いつかはそうしないと、ですねこりゃ。

で、それでも課題Ａは負けてますね。
50,896回!?　(＠_＠;)

一応、こちらも「反転」すれば
再帰で１万以下、ループで３万前後まで下がることは下がるんですが…。

鋭意解読します　orz

=======================================

■>追記）ぁ、違う数値使ってますよね...orz

あ、そでしたね。私もすっかり忘れてました。　orz

何しろ１千個ですから、記事内に書けませんし
逆に、これだけ要素があれば桁がずれるほどの差は出ないということで
具体的な数字出すのは端折ったんでした。

こちらで使っている数字を一応上げときます。

　http://abyssinia2010.web.fc2.com/ssstmp/tasks.txt

　#　なんという素人臭い…　orz

fc2ってExcelのブック置けないんですよね　(ーー;)
拡張子偽装は即アカ停止とか脅し文が書いてあるし…。

別にアップローダ探そうかしら。

あ、その前に【Excelのブックをアップする前に処理すべきこと】を勉強しないと…　orz
別に指名手配犯ぢゃないので、いろいろ判ってもマズくはないんですが、
時々会社電話番号部署名本名メアド全部わかるような上げ方してる人もいますしね(ーー;)
62：_Kyle(1291004) :

2010/06/08 (Tue) 21:26:09

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275999969.png すみません。

タスク過重でちょっとフリーズ気味です……わたしが。　orz

しばしおまちを。
61：end-u(1037781) :

2010/06/08 (Tue) 03:40:17

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275936017.jpg 違うなー…
１回のLoopで２階層判定してるから
逆に多い事になる..のかな。

失礼しましたm(_ _)m
やっぱり勘違い...
アタマ混乱してるのでもう寝ますorz
60：end-u(1037781) :

2010/06/08 (Tue) 03:07:11

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275934628.jpg 速度はともかくとして、Loop回数は減らせるんじゃないかと思うんですが、
ひょっとして、このロジックだとかえって遅くなるからあえて、だったりします？

Sub try()
　　Dim CHK As Long　　　'目標
　　Dim mx　As Long　　　'要素個数
　　Dim mn　As Long　　　'最小要素
　　Dim lv　As Long　　　'階層
　　Dim cnt As Long
　　Dim tmp As Long
　　Dim i　 As Long
　　Dim j　 As Long
　　Dim vWrk() As Long　 '要素配列
　　Dim vSum() As Long　 '[後方和]配列
　　Dim buf()　As Long　 '一時配列
　　Dim rst()　As Long　 '残記憶
　　Dim idx()　As Long　 'index記憶
　　Dim bufs(1 To 20000) '結果配列
　　Dim v, z
　　Dim c As Long

　　With ActiveSheet
　　　　With .Range("B1", .Range("B1").End(xlDown))
　　　　　　.Sort Key1:=.Item(1), _
　　　　　　　　　Order1:=xlDescending, _
　　　　　　　　　Header:=xlNo, _
　　　　　　　　　OrderCustom:=1, _
　　　　　　　　　MatchCase:=False, _
　　　　　　　　　Orientation:=xlTopToBottom, _
　　　　　　　　　SortMethod:=xlStroke
　　　　　　v = Application.Transpose(.Cells)
　　　　End With
　　　　CHK = .Range("A1").Value
　　End With

　　mx = UBound(v)
　　ReDim vWrk(1 To mx)
　　ReDim vSum(1 To mx)
　　ReDim buf(0 To mx)
　　ReDim rst(0 To mx)
　　ReDim idx(0 To mx)
　　
　　tmp = 0
　　For i = mx To 1 Step -1
　　　　vWrk(i) = v(i)
　　　　tmp = tmp + vWrk(i)
　　　　vSum(i) = tmp
　　Next

　　cnt = 0
　　lv = 1
　　i = 1
　　rst(0) = CHK
　　mn = vWrk(mx)

　　Do
　　　　c = c + 1
　　　　'残りすべてを使っても足りないor最小要素に満たない場合
　　　　If rst(lv - 1) > vSum(i) Or rst(lv - 1) < mn Then
　　　　　　lv = lv - 1
　　　　　　i = idx(lv) + 1
　　　　Else
　　　　　　idx(lv) = i
　　　　　　buf(lv) = vWrk(i)
　　　　　　rst(lv) = rst(lv - 1) - vWrk(i)
　　　　　　'Hit
　　　　　　If rst(lv) = 0 Then
　　　　　　　　cnt = cnt + 1
　　　　　　　　'使用要素数もついでに格納し書き出し時に利用。
　　　　　　　　buf(0) = lv
　　　　　　　　bufs(cnt) = buf
　　　　　　End If
　　　　　　'最大Indexで折り返し
　　　　　　If i = mx Then
　　　　　　　　lv = lv - 1
　　　　　　　　i = idx(lv) + 1
　　　　　　Else
　　　　　　　　'残ありで次階層へ
　　　　　　　　If rst(lv) > 0 Then
　　　　　　　　　　lv = lv + 1
　　　　　　　　End If
　　　　　　　　i = i + 1
　　　　　　End If
　　　　
　　　　End If
　　Loop Until lv = 0

　　If cnt > 0 Then
　　　　ReDim z(1 To mx, 1 To cnt) As Long
　　　　For i = 1 To cnt
　　　　　　For j = 1 To bufs(i)(0)
　　　　　　　　z(j, i) = bufs(i)(j)
　　　　　　Next
　　　　Next
　　　　With ActiveSheet
　　　　　　'.Range("C1", .UsedRange.Item(.UsedRange.Count)).ClearContents
　　　　　　.Range("C1").Resize(mx, cnt).Value = z
　　　　End With
　　End If
　　Erase vWrk, vSum, buf, idx, rst, z
　　Debug.Print c

End Sub

ループ回数
課題Ａ　　　 50,896
課題Ｂ　 34,411,119
課題Ｃ　153,302,260※

Ｃは増えますね？
頭コンガラガッテ検証不足かもしれません。
勘違いしてたらごめんなさいm(_ _)m

追記）ぁ、違う数値使ってますよね...orz
59：_Kyle(1291004) :

2010/06/07 (Mon) 21:16:13

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275912973.gif ぇっと【いまさら】なんですが
[ver5_20以降のループ回数]　と　[ver0_30以降の再帰回数]
を比較するとこんな感じになります。

●X_20,X_30

　課題Ａ
　　ループ：　2,147,448,187
　　再　帰：　1,073,724,094
　課題Ｂ
　　ループ：　979,089,639
　　再　帰：　489,544,820
　課題Ｃ
　　ループ：　16,152,620,894
　　再　帰：　_8,076,310,793

●X_40

　課題Ａ
　　ループ：　671,987
　　再　帰：　335,994
　課題Ｂ
　　ループ：　979,089,599
　　再　帰：　489,544,800
　課題Ｃ
　　ループ：　16,152,620,894
　　再　帰：　_8,076,310,793

●X_50

　課題Ａ
　　ループ：　186,265
　　再　帰：　_93,133
　課題Ｂ
　　ループ：　122,353,701
　　再　帰：　_61,176,851
　課題Ｃ
　　ループ：　1,779,991,187
　　再　帰：　__889,995,846

●X_60

　課題Ａ
　　ループ：　164,503
　　再　帰：　_82,252
　課題Ｂ
　　ループ：　54,779,015
　　再　帰：　27,389,508
　課題Ｃ
　　ループ：　225,856,675
　　再　帰：　112,928,590

●X_70

　課題Ａ
　　ループ：　157,141
　　再　帰：　_78,571
　課題Ｂ
　　ループ：　42,693,713
　　再　帰：　21,346,857
　課題Ｃ
　　ループ：　151,844,359
　　再　帰：　_75,922,432

==========================================

なにも全部並べることはなかったんですが(^^;;;;
気付きました？　つか、知ってました？

ループ回数は、キレイに再帰回数の倍になってますね。
正確に言うと、
　[ループ回数]　＝　[再帰回数×２]－１
です。

まぁ、
コーディングが違うだけでアルゴリズムは同じなので
当たり前っちゃ当たり前なんですが…。
つか、キレイに揃わないようではマズいですw

　※課題Ｃの場合にキッカリにならないのは
　　eFlg／endFlgが立ったときの抜け処理の違いです。
　　再帰ではテッペンまで戻って抜けますが
　　ループでは途中からいきなり抜けます。

で、
なんでループ回数が再帰回数の倍になるかというと
　【　戻り道をカウントしてるからです　】

再帰の場合は、Exit SubやEnd Subで【自動的に】戻るので、新規呼び出しは不要です。
ループの場合は、ループ中の処理によって明示的に戻る必要があります。

==========================================

ちなみに、二方向分岐のver.X.00～ver.X.10の場合

●X_00

　課題Ａ
　　ループ：　3,221,225,470
　　再　帰：　2,147,483,648

●X_10

　課題Ａ
　　ループ：　3,221,172,280
　　再　帰：　2,147,448,187
　課題Ｂ
　　ループ：　1,468,634,458
　　再　帰：　__979,089,639

こちらは２倍ではなく、1.5倍になっていますね。

これは、二方向分岐の場合
「呼び元が要素を使わなかった場合はtAryのフラグを倒す必要がない」ので
「自分を呼んだ階」ではなく「最後に要素を使った階」に戻るようにしているからです。
58：_Kyle(1291004) :

2010/06/07 (Mon) 20:07:20

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275908840.gif こちらも一応低機能版を用意しました。

■ver.5.72
http://abyssinia2010.web.fc2.com/ssstmp/ver5_72.txt

■所要時間

●課題Ａ

k0SSS_5_70　0.240秒
k0SSS_5_72　0.125秒

●課題Ｂ

k0SSS_5_70　29.436秒
k0SSS_5_72　27.690秒

●課題Ｃ

k0SSS_5_70　135.255秒
k0SSS_5_72　134.374秒

============================

■制限事項

　・A1セルに目標値、B1セル以下に要素があることを仮定
　・要素が【事前に降順ソート】されていることを仮定
　・Excel2007での運用を仮定
　・要素に0が含まれないことを仮定
　・事前に書き出し範囲をクリアしない
　・ESCで書き出ししない
　・進捗を表示しない
　・すべての解を見つけたか否かを表示しない
　・解がない場合を想定しない

結果は一応数字を入れるようにしました。
「使うものに1を表示する」というのはさすがに嫌がらせっぽいのでw

　　【　でも、ソルバーはそうだよね　】

やっぱり嫌がらせかっ！
57：_Kyle(1291004) :

2010/06/07 (Mon) 19:51:34

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275919978.gif 再帰ではなくループの場合は、もちろん単一プロシージャで書けます。
再帰と違って主処理の呼び出しコストがかからないので、所要時間も変わりません。

　※
　再帰でk0SSS_Hとかk0SSS_Cとか分けてるのは
　呼びコストがかかる　⇒　子Ｐを分ける　⇒　【子Ｐの呼びコスト】が下がる　⇒　速い
　というハナシです。

　「呼びコストがかかるなら、再帰は分けない方がトクじゃん」
　とか間抜けなこと言わないように。念のため。

　※
　単一プロシージャなので、変数全部プロシージャレベルで宣言しても動きますが
　プロシージャレベル変数は読み書き時間の点で不利なので、少し遅くなります。
　所要時間を比較する際にアンフェアな気がしたので、宣言場所はそのままにしています。

■ver.5.71
http://abyssinia2010.web.fc2.com/ssstmp/ver5_71.txt

所要時間

●課題Ａ

k0SSS_5_70　0.240秒
k0SSS_5_71　0.248秒

●課題Ｂ

k0SSS_5_70　29.436秒
k0SSS_5_71　29.480秒

●課題Ｃ

k0SSS_5_70　135.255秒
k0SSS_5_71　137.163秒

ただし、取り回しの都合で当面はver.5.70を採用。
56：_Kyle(1291004) :

2010/06/07 (Mon) 19:12:17

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275905537.gif [残和]以下の要素までスキップ！

■ver.5.70
http://abyssinia2010.web.fc2.com/ssstmp/ver5_70.txt

●課題Ａ

　所要時間　0.240秒　⇒　0.240秒
　ループ回数　164,503回　⇒　157,141回

　cf.k0SSS_0_70　0.197秒（120%）／78,571回

●課題Ｂ

　所要時間　32.846秒　⇒　29.436秒　30秒切った！＼(^o^)／
　ループ回数　54,779,015回　⇒　42,693,713回

　cf.k0SSS_0_70　17.498秒（170%）／21,346,857回

●課題Ｃ

　所要時間　172.547秒　⇒　135.255秒
　ループ回数　225,856,675回　⇒　151,844,359

　cf.k0SSS_0_70　93.980秒(140%)／75,922,432回

=====================================

再びループとの速度比が小さくなってきましたね。

探索時間が短くなった結果、
所要時間に占める書出時間の割が大きくなったためです。
55：_Kyle(1291004) :

2010/06/07 (Mon) 18:44:29

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275903869.gif 寝てる間にちゃんとテスト終わってました＼(^o^)／

こういうときマクロって便利ですね(違？

だからEndとか使っちゃダメなのよ、ホント。
54：_Kyle(1291004) :

2010/06/06 (Sun) 19:32:08

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275903391.gif 残りのどれを使っても超えるならアウト！

■ver.5.60
http://abyssinia2010.web.fc2.com/ssstmp/ver5_60.txt

●課題Ａ

　所要時間　0.249秒　⇒　0.240秒
　ループ回数　186,265回　⇒　164,503回

　cf.k0SSS_0_60　0.1885秒（130%）／82,252回

●課題Ｂ

　所要時間　67.674秒　⇒　32.846秒　微妙に30秒切らない　(ーー;)
　ループ回数　122,353,701回　⇒　54,779,015回　１億回切った！　＼(^o^)／

　cf.k0SSS_0_60　21秒（160%）／27,389,508回

●課題Ｃ

　所要時間　920.569秒≒15分　⇒　172.547秒　３分切った！　＼(^o^)／
　ループ回数　1,779,991,187回　⇒　225,856,675回

　cf.k0SSS_0_60　107秒(160%)／112,928,590回
53：_Kyle(1291004) :

2010/06/06 (Sun) 19:07:07

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275903004.gif 大きいものから使う。

■ver.5.50
http://abyssinia2010.web.fc2.com/ssstmp/ver5_50.txt

●課題Ａ

　所要時間　0.456秒　⇒　0.249秒
　ループ回数　671,987回　⇒　186,265回

　cf.k0SSS_0_50　0.1719秒（140%）／93,133回

●課題Ｂ

　所要時間　474.189秒　⇒　67.674秒　びみょうに1分切らない　(ーー;)
　ループ回数　979,089,599回　⇒　122,353,701回

　cf.k0SSS_0_50　33秒（200%）／61,176,851回

●課題Ｃ

　所要時間　7823.485秒≒130分　⇒　920.569秒≒15分
　ループ回数　16,152,620,894回　⇒　1,779,991,187回

　cf.k0SSS_0_50　399秒(230%)／889,995,846回
52：_Kyle(1291004) :

2010/06/06 (Sun) 19:05:55

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275902501.gif 残りすべてを使っても足りないならアウト！

■ver.5.40
http://abyssinia2010.web.fc2.com/ssstmp/ver5_40.txt

●課題Ａ

　所要時間　1079.094秒　⇒　0.456秒　　＼(^o^)／　１秒切ったw
　ループ回数　2,147,448,187回　⇒　671,987回　＼(^o^)／　100万回切ったw

　cf.k0SSS_0_40　0.266秒（170%）／335,994回
　※時間は誤差みたいなもんですが。

●課題Ｂ

　所要時間　533.359秒　⇒　474.189秒　あれ？　予想以上に減った。不安(ーー;)
　ループ回数　979,089,639回　⇒　979,089,599回　これはまぁこんなもん。　

　cf.k0SSS_0_40　186秒（250%）／489,544,800回

●課題Ｃ

　所要時間　7621.338秒≒127分　⇒　7823.485秒≒130分
　ループ回数　16,152,620,894回　⇒　16,152,620,894回

　cf.k0SSS_0_40　2974秒≒50分／8,076,310,793回
51：_Kyle(1291004) :

2010/06/06 (Sun) 17:45:41

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275919146.gif やっと終わった　orz　←終わってませんw　←終わりました

テストしてる間に文庫本２冊読みきっちゃったよw
ティプトリーやっぱいいなぁ。

======================================

■ver.5.30
http://abyssinia2010.web.fc2.com/ssstmp/ver5_30.txt

●課題Ａ

　所要時間　1655.016秒≒27分　⇒　1079.094秒　＼(^o^)／　20分切った！
　ループ回数　2,147,448,187回　⇒　2,147,448,187回　もちろん変化ナシ

　cf.k0SSS_0_30　470秒（230%）／1,073,724,094回

●課題Ｂ

　所要時間　1155.382秒≒19分　⇒　533.359秒　＼(^o^)／　9分切った！
　ループ回数　979,089,639回　⇒　979,089,639回　もちろん変化ナシ

　cf.k0SSS_0_30　185秒（290%）／489,544,820回

●課題Ｃ

　所要時間　7621.338≒127分　微妙に２時間切らなかった　(ーー;)
　ループ回数　16,152,620,894回　ぇっと、160億回？

　cf.k0SSS_0_30　3009秒(250%)／8,076,310,793回

======================================

再帰と較べると、速度比的にかなり差が開いてしまいましたね。

個別に見るとこんな感じです↓

・ver.5.21／0.21
　Integer→Longは最初からそうしてたので変化なし

・ver.5.22／0.22
　Variant→Longは効いた。正味所要時間３割減　＼(^o^)／

・ver.5.23／0.23
　全体の処理量に占めるtAry変更処理の割が少ないので、
　Boolean型への変更は再帰ほどの効果はナシ。でも正味所要時間１割減　＼(^o^)／

・ver.5.34／0.24
　再帰と違い、プロシージャ呼び出し負担がかかってないので、
　ヒット処理切り出しは速度面での効果はナシ

・ver.5.25／0.25
　一気書き出しはもちろん効果大。＼(^o^)／
　ただし、全体時間に占める割は再帰より小さいので速度比は拡大　orz

・ver.5.26／0.26
　進捗表示は速度面では影響なし（あって２秒）

・ver.5.27／0.27
　もともとEndではなくExit Doで抜けるので、
　終了処理自体は速度面での影響はなし。

・ver.5.28／0.28
　再帰回数　＜　ループ回数　なので
　eFlg判定の負担が大きい　orz

・ver.5.29／0.29
　もともと一括書き込み

・ver.5.30／0.30
　速度面で影響なし
50：_Kyle(1291004) :

2010/06/06 (Sun) 11:17:53

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275811380.png eIdxの初期設定が消えてました　orz

直しました。

■ver.5.20
http://abyssinia2010.web.fc2.com/ssstmp/ver5_20.txt
49：_Kyle(1291004) :

2010/06/06 (Sun) 09:39:55

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275918825.gif 　【　ver.6.40 や ver.6.50 って速すぎじゃね？　】
　
　【　同じ(?)「動的計画法」なのにやたらと速いのは
　　　もしかして、なにか「間違えてるから」じゃないの？　】

という疑惑wwww

「動的計画法」スコアまとめ（いずれも秒／件　timeGetTimeで再計測）

　●ver.6.10：　イルカよりは確かそうな(?)人が書いた「動的計画法」
　　課題Ａ　1.575
　　課題Ｂ　10.689
　　課題Ｃ　×
　　qa5212312　14.588

　●ver.6.20：　チェコかどっかの大学(?)のサイトにあった「Dynamic Programming」
　　課題Ａ　0.218
　　課題Ｂ　0.056
　　課題Ｃ　×
　　qa5212312　9.398

　●ver.6.40：　早起きのイルカが書いた「動的計画法に似たなにか」
　　課題Ａ　0.071
　　課題Ｂ　0.456
　　課題Ｃ　2850.512
　　qa5212312　1.998

　●ver.6.50：　寝不足のイルカが書いた「動的計画法っぽいもの」
　　課題Ａ　0.148
　　課題Ｂ　0.817
　　課題Ｃ　1393.825
　　qa5212312　1.194

　cf.k0SSS_0_70：　だk(ry

　　課題Ａ　0.0008419秒
　　課題Ｂ　0.0011074秒
　　課題Ｃ　0.0057368秒　
　　qa5212312　0.00064754秒

まぁ【　速けりゃ間違えててもいいんじゃね？　】
とわたしなんかは思っちゃうわけですが…。

とりあえず解は出るようだし。
とりあえず出た解は合ってるようだし。

たとえば同じ「総当り」でも、速いのから遅いのまでいろいろあるわけだしね。

========================

で、【いまだにちゃんと読んでないんですが】
差が出る要因として考えられるのは…

たとえば
　課題　{9,8,7,6,5,4,3,2,1}　⇒　40
というときに

●使えないものを作ってる

たとえば
「4番目まで使って13を作る方法　{-,-,7,6}13」
なんて情報があっても使い道はないわけです。
「4番目までで13」ならどうしたって足りないわけですから。
「残りすべての…」というやつです。

●無駄なことを覚えてる

たとえば、第5要素まで進んだ段階で
「2番目まで使って17を作れる　⇒　{9,8}17」
「3番目まで使って17を作れる　⇒　{9,8,-}17」
「4番目まで使って17を作れる　⇒　{9,8,-,-}17」
という情報をそれぞれ全部覚えておく必要はありませんよね。

第N要素まで進んだ段階で必要なのは、
「N-1番目まで使ってYを作れる　⇒　{a,b,…,l,m}Y」
だけです。

「1番目まで使って作れる数」
「2番目まで使って作れる数」
「3番目まで使って作れる数」
・
・
・
「N-1番目まで使って作れる数」
と全部覚えてるからメモリが足りない。

　#　…というより、ver6.10は
　#　「各段階-各数字ごとの最適解の作り方を覚えてる」
　#　というニュアンスなのかな？
　#　「3番目まで使って19は作れない。一番近いのは{9,8,-}17」みたいな…。

　#　最終段階での最適解には意味があるかもしれないけど
　#　途中の最適解がわかってもうれしくないよね　(ーー;)
　#　最適解＋最適解⇒最適解とは限らんわけだから、
　#　使えるのは「キッカリの解」だけ。

●エレファントな覚え方をしている

ver.6.20は元コードの時点では2^Xの整数に組合せを割り当てていました。
ver.6.20では、X桁のStringに0/1を入れて組合せを管理しています。

しかし、「9,8,6で23を作れる」ことがわかったとして、
23を作る場合の組合せ　{9,8,-,6}23　を丸ごと全部覚えておく必要はありませんよね。

「最終要素XでYを作れる　⇒　{～,X}Y」
ことだけ覚えておけば、

「最終要素6で23を作れる　⇒　{～,6}23」
「最終要素8で17を作れる　⇒　{～,8}17」
「最終要素9で9を作れる　⇒　{～,9}9」
　6⇒(23-6=17)8⇒(17-8=9)9　と芋づる式に思い出せます。

●あと、【本来の】「部分和問題」は…

「解の有無を判定する決定問題」であるだけでなく
「要素を正整数に絞らない」のが普通のようです。

要素に負数がある場合は、
単純に「残りすべての和」と比較して刈ることはできません。
（正数と負数に分けて「正数の合計＋負数の合計」で考える手はあるけど）
48：_Kyle(1291004) :

2010/06/06 (Sun) 09:05:16

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275783647.gif テスト待ちのコードがどんどん溜まっていく…orz

=======================

↓こうした方が「どーてきけーかくほー」っぽいかも？

■ver.6.50　
http://abyssinia2010.web.fc2.com/ssstmp/ver6_50.txt

　　課題Ａ　0.148秒
　　課題Ｂ　0.817秒
　　課題Ｃ　1393.825秒
　　qa5212312　1.194秒

　cf.1　k0SSS_6_40

　　課題Ａ　0.071秒
　　課題Ｂ　0.456秒
　　課題Ｃ　2850.512秒
　　qa5212312　1.998秒

　cf.2　k0SSS_0_70

　　課題Ａ　0.0008419秒
　　課題Ｂ　0.0011074秒
　　課題Ｃ　0.0057368秒　
　　qa5212312　0.00064754秒

　#だかr(ry

=============

一口に「ボトムアップ」といっても「動的計画法」ってのは

　【　「できたもの」じゃなくて「つくったもの」をおぼえる　】

というハナシじゃないかというハナシ…よく知らないけど(ぉぃ

k0SSS_6_40　⇒　「まず積んでみて、できたものが新しいなら覚える」
k0SSS_6_50　⇒　「作れてない物を調べてみて、作れたなら覚える」

まぁ、同じこと…だと思うんだけどね。

でも、解の密度によってけっこう差が出るね。
　・薄い場合は6_40が有利
　・濃い場合は6_50が有利

=============

…という以前に、あってんのかなコレ？(ぉぃ

無制限で0からtgtSumまで調べるわけにもいかんしな…(ーー;)

こういう「端っこの処理」、苦手なんだよね。昔っから。
47：_Kyle(1291004) :

2010/06/06 (Sun) 08:12:36

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275895999.png 　　　　　　　　　　　　　　　　　　www　⇒

なんつーエレファントなバージョン管理(^^;;;;;;;

======================================

■ver.5.20
http://abyssinia2010.web.fc2.com/ssstmp/ver5_20.txt

どんどんうろんになってゆく　orz

======================================

●課題Ａ

　所要時間　1943.043≒33分　⇒　1655.016秒≒27分　＼(^o^)／　30分切った！
　ループ回数　3,221,172,280回　⇒　2,147,448,187回

　cf.k0SSS_0_20　約20分／1,073,724,094回

●課題Ｂ

　所要時間　1284.240秒≒21分　⇒　1155.382秒≒19分　＼(^o^)／　20分切った！
　ループ回数　1,468,634,458回　⇒　979,089,639回　＼(^o^)／　10億切った！

　cf.k0SSS_0_20　約13分／489,544,820回
46：_Kyle(1291004) :

2010/06/06 (Sun) 03:35:02

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275896195.gif ■ver.5.10
http://abyssinia2010.web.fc2.com/ssstmp/ver5_10.txt

【　コードって、書いた人のアタマの構造反映するよね　】

o　　...rz

でも動いてる！！　＼(^o^)／

==============================

●課題Ａ

　所要時間　1931.175秒≒33分　⇒　1943.043≒33分　
　ループ回数　3,221,225,470回　⇒　3,221,172,280回

　cf. k0SSS_0_10：約24分／2,147,448,187回

「子Ｐの構文的サイズが速度に直接影響しない」のがうれしいですね。

再帰だと
------------------------
　If xxxx Then yyyy
と
　If xxxx Then
　　yyyy
　End If
のどちらが速いか
------------------------
なんて不毛なこと考えないといけないので疲れますw

==============================

●課題Ｂ

　所要時間　1284.240秒≒21分
　ループ回数　1,468,634,458回

　cf.k0SSS_0_10：約16分／979,089,639回

これくらいの速度比（130～140％くらい？）で推移できるなら
十分実用レベルになりそうですね。

呼び出し負担考えずに凝ったことできる分
最終的にはかなりの速度が出るかも!?
45：_Kyle(1291004) :

2010/06/05 (Sat) 23:38:43

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275895661.gif また「総当り」から始めるのか!?　＞　わたし

　　#　5番台なのは「補数」ぢゃないです。「習作」ということで(^^;;;;

「できそうだ」「できるらしい」というのは知ってたんですが
実際真面目に読んでみたのは初めてで(ぇ、正直かなり目からウロコだったので、
土曜ということもありちょっとだけ「向上を志向」してみました（笑

===============================

■ver.5.00
http://abyssinia2010.web.fc2.com/ssstmp/ver5_00.txt

動いた！！　＼(^o^)／

でもやっぱり胡乱　orz

課題Ａ
　
　ヒット判定　1,073,741,824 = 2^30　回
　所要時間　1931.175秒 ≒ 33分
　ループ回数　3,221,225,470 = 2^30*3 -2　回

cf　K0SSS_0_00

　ヒット判定　2^30-1　＝　1,073,741,823　通り　
　所要時間　約20分／2,147,483,648 = 2^31回

===============================

そっか、再帰に較べて戻り道の判定が負担になるのね。なりゅほど。
44：_Kyle(1291004) :

2010/06/05 (Sat) 10:00:25

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275915836.png 「k0SSS_0_70が最速って、『課題Ａ【0.08秒】への途』はどうなったのさ？」

というツッコミが聴こえた気がしたので…。

ぇっと、わたしの環境だと、Excel2007で「課題Ａ0.08秒」は…

　【　出ません　】(ぉぃ

書き出しコストだけで間に合わない感じです。

その代わり、Excel2003では、k0SSS_0_80で
timeGetTime関数による「78ミリ秒」を記録しています。
もちろん、列方向書き出し、書き出し時間込み、進捗表示アリです。

最終的にもう一度、一通り測り直して整理するつもりですが、
とりあえずまとめるとこんな感じ。

k0SSS0_30　⇒　k0SSS0_80

●総所要時間

　課題Ａ　470秒　⇒　0.180秒　(1/2600)
　※Excel2003では0.078秒を記録（1/6025）
　課題Ｂ　185秒　⇒　19.854秒　(1/9)
　課題Ｃ　3009秒　⇒　107.574秒　(1/28)

●再帰回数

　課題Ａ　1,073,724,094回　⇒　20,233回　(1/53067)
　課題Ｂ　　489,544,820回　⇒　17,324,071回　(1/28)
　課題Ｃ　8,076,310,793回　⇒　74,505,692回　(1/108)

再帰回数の減り具合に対して、所要時間の減り具合が小さいのは
ver.0.30以降
「各バージョンとも一定の書き出しコストがかかってる」
からです。
「固定費」というやつです。

これ読んでる人がもしいるとしたらw、おそらくわたしと同じ文系事務屋さんでしょうから、
シュラッター=シュラッター図みたいなのを連想してもらえればわかりやすいかも。

※覚書

まとめるときには、
総所要時間を「探索時間＋書出時間＝所要時間」に分けて掲示すること　orz
43：_Kyle(1291004) :

2010/06/05 (Sat) 09:48:30

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275915497.gif 一方

「何も毎回チェックしてマメに反転しなくても、最初だけ反転すればいいんぢゃね？」

という考え方もありそうです。

　●ver.0.81
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_81.txt

たしかに、たいていの場合はコレで足ります。

---------------
※

足りる足りない以前に、課題Ｃはコレでもk0SSS_0_70より遅くなります。
（子Ｐは触らないけどdspAryを作るときの判定が負担）

k0SSS_0_81のスコア（括弧内はk0SSS_0_80）

●総所要時間

　課題Ａ　0.197秒　⇒　0.179秒（0.180秒）
　課題Ｂ　17.498秒　⇒　17.715秒（19.854秒）←「反転」しないので変化ナシ
　課題Ｃ　93.980秒　⇒　99.325秒（107.574秒）

●再帰回数

　課題Ａ　78,571回　⇒　29,947回（20,233回）
　課題Ｂ　21,346,857回　⇒　21,346,857回（17,324,071回）←「反転」しないので変化ナシ
　課題Ｃ　75,922,432回　⇒　75,697,162回（74,505,692回）

---------------

さて。

「反転するにしてもk0SSS_0_81じゃだめなの？」ってハナシですが、
たとえば、

●課題Ｃ改々

　・課題Ｃの目標値を　40,000,000　⇒　57,500,000　に変更
　・【　新たに100,000,000を要素に付け加える　】

というようなケースだと
初期処理の時点では要素の総和が大きいので反転基準を充たしませんが
100,000,000をハジいた時点で課題Ｃ改と同じことになります。

乱数で生成したようななだらかな分布の場合には、最初だけ反転すれば良いけれど
偏りや特異値があると、処理の中途で「極端なケース」が生じる可能性があります。

========

というわけで
「一般的な状況」においてはk0SSS_0_70の方が速いと思われますが
遅くなったといっても(ソルバーなんかに較べれば）k0SSS_0_80も十分に速いですし、
汎用性重視…というより
「こういうケースだと人間より遅くなるっつのwwwww　ﾌﾟｹﾞﾗ」
的な突っ込み／揚げ足取り対策wとしてk0SSS_0_80を採用ということに。

「突っ込み」「揚げ足取り」といえばもう一点、
誰でも思いつく…もとい、誰もが試したくなるケースがありますよね(^^;;;;

それは次回。
42：_Kyle(1291004) :

2010/06/05 (Sat) 09:44:13

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1344720422.gif ■ver.0.80
http://abyssinia2010.web.fc2.com/ssstmp/ver0_80.txt

なんかかなり胡乱なことになってますが…(^^;;;;;

たとえば

　　--------------------------------
　　●課題Ｆ
　　10個の正整数　[要素]　{113,96,87,126,92,106,103,99,85,117}
　　の中から、重複を許さず、順序を考慮せず選んで、それらの和が、
　　[目標値]　925　と等しくなる組合せ　[解]　を【　すべて　】求める。
　　--------------------------------

というような課題の場合、
人間が見れば「解が　{113,96,87,126,92,106,103,85,117} 　ただ一つである」ことが
ひと目…はちょっと無理ですがｗ、手計算でわかります。

しかし、k0SSS_0_70にはわからないので生真面目に探しちゃいます。

※いちおー念のために。

　課題Ｆについて、要素の総和は1024です。
　　・総和が1024の要素群から、和が 925 になるように要素を選ぶ
　　・総和が1024の要素群から、和が 1024-925 = 99 になるように要素を選ぶ
　どちらも同じことですよね。

で、わかるようにしてやろうというハナシです。

　【　要素の総和に対して目標値が大きい場合は
　　　課題を「反転」して「使わないもの」を探した方が賢い……ハズ　】

========

●実装上のポイント

・各段階ごとの反転基準を事前に用意する
・「残りすべてを使っても」判定は廃止。反転した時点で残和は後方和の半分より小さくなります。
・「反転した途端に残和が0になる」ことがあるので最初に判定する　←かつて間違えました　orz
・ヒット処理の際、反転状態に応じて後方を埋める　←かつて忘れました　o ...rz
・スキップした部分も忘れずに埋める　←5.80でハマりました　(T_T)

　#　ところで、番号の若い方を「前」と見る感覚はあってるのかしらん？
　#　もしかして[後方和]じゃなくて[前方和]とすべき？
　#　先に処理するものが「前」なのか、これから処理するものが「前」なのか…

　#　「参照先」と「参照元」もけっこう曖昧だったりするのよね、わたし(ぇ

========

というハナシなんですが……

●総所要時間

　課題Ａ　0.197秒　⇒　0.180秒
　課題Ｂ　17.498秒　⇒　19.854秒
　課題Ｃ　93.980秒　⇒　107.574秒

●解一つあたりの探索時間

　課題Ａ　0.0008419秒　⇒　0.0007692秒
　課題Ｂ　0.0011074秒　⇒　0.0012565秒
　課題Ｃ　0.0057368秒　⇒　0.0065666秒　

●再帰回数

　課題Ａ　78,571回　⇒　20,233回
　課題Ｂ　21,346,857回　⇒　17,324,071回
　課題Ｃ　75,922,432回　⇒　74,505,692回

再帰回数こそ減っていますが、所要時間の方はむしろ増えちゃってます。
子Ｐがかなり重くなった結果、損益分岐点を越えてしまった感じですね。
（課題Ｃの場合、子Ｐの引数を一つ増やすだけでも数秒遅くなります）

加えて、「残和が大きければ反転」というのは
「残りすべてを使っても足りないならアウト」と効果がかぶるんですよね。

実際、課題Ｆでは、「99」よりも大きい要素、
たとえば「113」を「使わない」と決めた時点で「残りすべて…」フラグが立ちます。

しかし、まったく意味が無いかというとそうでもなくて、たとえば、

●課題Ｃ改
　課題Ｃの目標値を　40,000,000　⇒　57,500,000　に変更

というケースでは

　k0SSS_0_70：154.488秒（内、探索時間85.897秒）
　k0SSS_0_80：113.891秒（内、探索時間43.482秒）

とけっこう差が出ます。

まぁ、そういう極端なケースは運用でカバーしろって立場もありそうですが…。
41：_Kyle(1291004) :

2010/06/05 (Sat) 00:16:55

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275892634.gif ■ver.0.70
http://abyssinia2010.web.fc2.com/ssstmp/ver0_70.txt

ぇっと、タイトル通りです。

「minItmの判定は要らなくなったんじゃないか」
と思われるかもしれませんが、
　●ver.0.71　minItm判定ナシ
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_71.txt
minItm判定は「一発で大量の枝を刈れる」点が大きいので残しています。

「二度に分けて回さなくてもループ中に判定すればいいじゃないか」
と思われるかもしれませんが、
　●ver.0.72　ループ中に判定
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_72.txt
「残和以下になっても引き続いて判定することになる」ので事前に回しています。

==========================================

■その他の変更点

・やっぱり一気に書き出すようにしたw
・書き出し時に解をいったんbufAryに格納するようにした。
・書き出し時にScreenUpdatingを切るようにした。

==========================================

■スコア

【　一般的な状況下では　】　一応コレが最速です、わたし的には。

●総所要時間（書き出し時間含む）

　課題Ａ　0.188秒　⇒　0.197　誤差
　課題Ｂ　21.328秒　⇒　17.498　＼(^o^)／　20秒切った！
　課題Ｃ　106.812秒　⇒　93.980　＼(^o^)／　100秒切った！

●解一つあたりの探索時間（書き出し時間含む）

　課題Ａ　0.0008055秒　⇒　0.0008419秒
　課題Ｂ　0.0013498秒　⇒　0.0011074秒
　課題Ｃ　0.0065201秒　⇒　0.0057368秒　

　※qa5212312　0.00064754秒　（16382件／10.608秒）

●再帰回数

　課題Ａ　82,252回　⇒　78,571回
　課題Ｂ　27,389,508回　⇒　21,346,857回
　課題Ｃ　112,928,590回　⇒　75,922,432回　＼(^o^)／　１億回切った！

==========================================

■低機能版

ときどき【機能落として】
「こっちの方が速い／軽い／簡単／短い」
とか言う人がいるので、念のために。

　●ver.0.79　低機能版
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_79.txt

　・A1セルに目標値、B1セル以下に要素があることを仮定
　・要素が【事前に降順ソート】されていることを仮定
　・Excel2007での運用を仮定
　・要素に0が含まれないことを仮定
　・要素の値ではなく1を表示
　・Endで終わる
　・事前に書き出し範囲をクリアしない
　・ESCで書き出ししない
　・進捗を表示しない
　・すべての解を見つけたか否かを表示しない
　・解がない場合を想定しない

低機能ですが速いデス。

●総所要時間（書き出し時間含む）

　課題Ａ　 0.088秒
　課題Ｂ　14.497秒
　課題Ｃ　83.882秒

●解一つあたりの探索時間（書き出し時間含む）

　課題Ａ　0.0003761秒
　課題Ｂ　0.0009175秒
　課題Ｃ　0.0051204秒

　※qa5212312　0.000469173秒　（16382件／7.686秒）

==========================================

次回以降【　一般的でない状況　】に対応します。
40：_Kyle(1291004) :

2010/06/04 (Fri) 07:24:12

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275603844.gif ■ver.0.60
http://abyssinia2010.web.fc2.com/ssstmp/ver0_60.txt

たとえば

--------------------------------
●課題Ｅ
10個の正整数　[要素]　{14,26,85,46,72,66,43,28,44,23}
の中から、重複を許さず、順序を考慮せず選んで、それらの和が、
[目標値]　10 と等しくなる組合せ　[解]　を【　すべて　】求める。
--------------------------------

というような課題の場合、
人間が見れば「解がない」ことが一目でわかりますが
k0SSS_0_50は「解がない」ことわからないので生真面目に探しちゃいます。

で、わかるようにしてやろうというハナシです。

k0SSS_0_50の段階で要素を降順にソートしているので
最終の要素が最小の要素ということになりますが
要素にゼロが含まれていた場合のことを考慮して一応順番に見ています。

k0SSS_0_50の「[残和]が負になったらアウト！」判定と差し替えになっています。
rmnSum < 0　がTrueならば　rmnSum < minItm　もTrueです。

--------------------------------

●総所要時間

　課題Ａ　0.1719秒　⇒　0.1885秒
　課題Ｂ　33秒　⇒　21秒　＼(^o^)／　30秒切った！
　課題Ｃ　399秒　⇒　107秒　＼(^o^)／　2分切った！

●解一つあたりの探索時間

　課題Ａ　0.0007345秒　⇒　0.000805455秒
　課題Ｂ　0.002088秒　⇒　0.001349796秒
　課題Ｃ　0.02434秒　⇒　0.006520054秒　＼(^o^)／　1/100秒切った！

もはや指数表示にすべき？w

●再帰回数

　課題Ａ　93,133回　⇒　82,252回
　課題Ｂ　61,176,851回　⇒　27,389,508回
　課題Ｃ　889,995,846回　⇒　112,928,590回

============================================
k0SSS_0_50でorgAryをEraseするの忘れてました　orz

k0SSS_0_20～k0SSS_0_30で
「要素使い切ったらアウト！」判定要らなかったんじゃないかと思ったら…要りませんでした　orz
39：_Kyle(1291004) :

2010/06/04 (Fri) 07:22:15

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275604470.gif 別に、
　「動的計画法はダメだ！」
とかダイソレタことを言うつもりはありません。

単に、
　「動的計画法は、皆さんが期待しているようなものぢゃないかもしれない」
というハナシです。

------------------

「いわゆる部分和問題」を解決する上で、動的計画法は

【　要素の数が極めて多く、かつ、解の数が極めて少なく、かつ、解をどれか一つ見つければよい　】

という場合には、有効な手法です、たぶん。

●要素の数が（PCの能力に比して）比較的少ない場合

再帰処理で簡単に調べ尽くすことができますし
きちんと枝を刈れば、再帰処理の方が平均的には速いと思われます。

●解の数が（組み合わせの総数に比して）比較的多い場合

（確率的な問題として）少なくとも一つの解は再帰処理で簡単に見つかります。
きちんとコーディングすれば、再帰処理の方が平均的には速いと思われます。

●すべて、あるいはできるだけ多くの解を見つける必要がある場合

動的計画法では【　原理的に　】複数の解を見つけることはできません、たぶん。
再帰処理であれば【　原理的には　】物理的に書き出せるだけの解をすべて発見することができます。

------------------

一口に「ナップサック問題」と言っても
部分和問題は、瓶詰(Bin_packing_problem)や箱詰(割付問題)と違って
ある程度の規模の課題であれば、たいていの場合、かなり多数の最適解があります。

したがって、少なくとも実務上の課題においては

【　動的計画法が再帰処理よりも有利になる場面というのはほとんどない　】

…のではないか？　というのがわたしの認識です。

=============================================

★４　オマケ（でも最速）

ウィキペディア見ながら
http://ja.wikipedia.org/wiki/%e5%8b%95%e7%9a%84%e8%a8%88%e7%94%bb%e6%b3%95
【すくらっちから】【いめーじで】【てきとーに】書いてみたコード。
たぶんこーゆーことぢゃないかと思うのよね、よく知らないけど(ぉぃ

【　そりゃ動的計画法ぢゃねー！　】とか言われそうな悪寒ww

■ver.6.40
http://abyssinia2010.web.fc2.com/ssstmp/ver6_40.txt

　　　　課題Ａ　0.04688秒　（0.04688秒／1件）　←最速！　＼(^o^)／
　　　　課題Ｂ　0.4375秒　（0.4375秒／1件）
　　　　課題Ｃ　2819秒　（2819秒／1件）　←メモリ足りた！　＼(^o^)／
　　　　qa5212312　2.125秒　（2.125秒／1件）　←最速！　＼(^o^)／

けっこう速いw

　　cf.　k0SSS_0_50

　　　　課題Ａ　0.0007345秒　（0.1719秒／234件）
　　　　課題Ｂ　0.002088秒　（33秒／15801件）
　　　　課題Ｃ　0.02434秒　（399秒／16382件）
　　　　qa5212312　0.0007936秒　（13秒／16382件）

　#　だからなz(ry
38：_Kyle(1291004) :

2010/06/04 (Fri) 07:05:29

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275602731.gif ★３　ためしに…

Stringの代わりにジャグ配列使ってみた。
　※基本的に引き写しで中身読んでません(ぉ　

■ver.6.30
http://abyssinia2010.web.fc2.com/ssstmp/ver6_30.txt

　　　　課題Ａ　0.5313秒　（0.5313秒／1件）
　　　　課題Ｂ　0.09375秒　（0.09375秒／1件）
　　　　課題Ｃ　[メモリが不足しています。]
　　　　qa5212312　33.3125秒　（33.3125秒／0件）

ジャグ配列遅い　orz　…つか、String速い!?

　　cf.　k0SSS_0_50

　　　　課題Ａ　0.0007345秒　（0.1719秒／234件）
　　　　課題Ｂ　0.002088秒　（33秒／15801件）
　　　　課題Ｃ　0.02434秒　（399秒／16382件）
　　　　qa5212312　0.0007936秒　（13秒／16382件）

　#　だからなぜk(ry
37：_Kyle(1291004) :

2010/06/04 (Fri) 06:36:02

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275602549.gif ★２　次に…

●左に書いてある数字から（その数字は一回しか使えません）選び、足した値が
http://bekkoame.okwave.jp/qa5212312.html
で、
どっかの「専門家」が英字サイト這いずり回って拾ってきたREXXコードを
わたしがやっつけでVBAに移植(?)した『DPSforExcelVBA』

　※元サイト消えてます。手元にも元コード残ってません。
　※基本的に引き写しで中身読んでません(ぉ

　#　つかなんで英字サイトでREXXコードなんだろ？
　#　Cかなんかのコードがそこらへんの日本語サイトに転がってるだろうに…
　#　まぁ、Cだったらわたし読めないけどw

■ver.6.20
http://abyssinia2010.web.fc2.com/ssstmp/ver6_20.txt

　　解を【一つ】発見するまでの所要時間

　　　　課題Ａ　0.1719秒　（0.1719秒／1件）
　　　　課題Ｂ　0.04688秒　（0.04688秒／1件）
　　　　課題Ｃ　[文字列領域が不足しています。]　←初めて見たw
　　　　qa5212312　9.5781秒　（9.5781秒／1件）

Stringとか使って、ばかっぽいコーディングしてる割には意外と速い？

　　cf.　k0SSS_0_50

　　　　課題Ａ　0.0007345秒　（0.1719秒／234件）
　　　　課題Ｂ　0.002088秒　（33秒／15801件）
　　　　課題Ｃ　0.02434秒　（399秒／16382件）
　　　　qa5212312　0.0007936秒　（13秒／16382件）

　#　だからなぜ較b(ry
36：_Kyle(1291004) :

2010/06/04 (Fri) 06:26:35

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275601712.gif みなさんお待ちかね(?)の「動的計画法」デス。

【　動的計画法(Dynamic Programming)　】
と書くとなんかスゴそうに見えますよね。

「再帰処理」も
【　分割統治法(Divide and conquer algorithm)　】
と書いたらスゴくなるかしら？　www

さて。

一口に「動的計画法」と言っても実装上はいろいろ選択肢があるわけで…

=============================================

★１　まずは…

●ナップザック問題をExcelで解く
http://www.geocities.co.jp/SiliconValley-Oakland/8139/
にある
●動的計画法　＞　動的計画法により目標値に最も近い物をひとつだけ求める
http://www.geocities.co.jp/SiliconValley-Oakland/8139/dynamic.html

　　解を【一つ】発見するまでの所要時間

　　　　課題Ａ　1.6094秒　（1.6094秒／1件）
　　　　課題Ｂ　12.1094秒　（12.1094秒／1件）
　　　　課題Ｃ　[メモリが不足しています。]
　　　　qa5212312　14.5781秒　（14.5781秒／1件）

まぁ、こんなもんです。期待してた(?)人、ごめんねw

　　cf.　k0SSS_0_50（解一つあたりの平均所要時間）

　　　　課題Ａ　0.0007345秒　（0.1719秒／234件）
　　　　課題Ｂ　0.002088秒　（33秒／15801件）
　　　　課題Ｃ　0.02434秒　（399秒／16382件）
　　　　qa5212312　0.0007936秒　（13秒／16382件）

　#　だからなぜ較べr(ry

ちなみに、動作仕様をこちらに合わせた版はこちら
　※基本的に引き写しで中身読んでません(ぇ　

■ver.6.10
http://abyssinia2010.web.fc2.com/ssstmp/ver6_10.txt

　　解を【一つ】発見するまでの所要時間

　　　　課題Ａ　1.5938秒　（1.5938秒／1件）
　　　　課題Ｂ　11.0156秒　（11.0156秒／1件）
　　　　課題Ｃ　[メモリが不足しています。]
　　　　qa5212312　14.8594秒　（14.8594秒／1件）

動的配列で宣言したら遅くなるかと思ったけど大勢に影響ない感じやね。
Integer ⇒　Long　で相殺された感じ？
35：_Kyle(1291004) :

2010/06/02 (Wed) 20:24:38

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275890404.gif ■ver.0.50
http://abyssinia2010.web.fc2.com/ssstmp/ver0_50.txt

数理的に証明するのはめんどくさそうな気がしますが
日常的な感覚として
　【　小さい要素は潰しが効くから、後に取っといた方が賢い　】
というのは素朴に思いつきますよね。

大きい要素を優先的に使って、
小さい要素で調整するようにした方が効率がいいんじゃないかというハナシ。

再帰の度に大きいものを探していたら日が暮れますから事前にソートします。
本当はコード上でソートしたいんですが
クイックソートとかサラっと書けるレベルではないので、とりあえず今後の課題と言うことで…(汗

　#　クイックソートのコードなんてそこらへんにいくらでも転がってるし
　#　実は自分で書いたものもあるんだけど…動作に自信が持てない　orz

--------------------------------

●総所要時間

　課題Ａ　0.2656秒　⇒　0.1719秒
　課題Ｂ　186秒　⇒　33秒　　　　　1分切った　＼(^o^)／
　課題Ｃ　2974秒　⇒　399秒　　　　7分切った　＼(^o^)／　

●解一つあたりの探索時間

　課題Ａ　0.001135秒　⇒　0.0007345秒
　課題Ｂ　0.01179秒　⇒　0.002088秒
　課題Ｃ　0.18秒　⇒　0.02434秒

●再帰回数

　課題Ａ　335,994回　⇒　93,133回
　課題Ｂ　489,544,800回　⇒　61,176,851回
　課題Ｃ　8,076,310,793回　⇒　889,995,846回

--------------------------------

劇的？　
34：_Kyle(1291004) :

2010/06/02 (Wed) 20:19:22

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275477562.gif 一部に熱烈な愛好家(?)がいるソルバー。

■ver.7.00　ソルバー
http://abyssinia2010.web.fc2.com/ssstmp/ver7_00.txt

　　解を【一つ】発見するまでの所要時間

　　　　課題Ａ　169秒　（169秒／1件）
　　　　課題Ｂ　1037秒　（1037秒／1件）
　　　　課題Ｃ　[変化させるセルが多すぎます。]
　　　　qa5212312　∞秒　（3600秒／0件）

参考　k0SSS_0_40

　　解一つあたりの平均所要時間

　　　　課題Ａ　0.001135秒　（0.2656秒／234件）
　　　　課題Ｂ　0.01179秒　（186秒／15801件）　
　　　　課題Ｃ　0.18秒　（2974秒／16382件)
　　　　qa5212312　0.0038秒　（63秒／16382件)

　#　だから、なぜ較べる？　www
　#　…なぜか較べる人がいるからです。　(ーー;)

===================================

・事前に[SOLVER]を[参照設定]する必要があります。
・その前に[Solver.xla]が開いている必要があります。
・その前に[ソルバー]がインストールされている必要があります。

===================================

ソルバーには【うんざりするほど】オプションがあるので、
もっと速く解が出る設定があるかも。

あと、Excel2007よりも、Excel2003の方が速いみたい。

===================================

いや、ソルバーも、状況によっては悪くないんですけどね。

　・要素の数がごく少ない場合
　・解をどれか一つ見つければよい場合
　・解が見つからなくてもかまわない場合（ダメモトとか興味本位とか）
　・コード書くのが面倒な場合
　・時間が山ほどある場合
　・「共役傾斜法」とか「準ニュートン法」とか言ってみたい場合
　・ごり押しで質問者をだまくらかしたい場合

こういう場合には有効な手法です。

短所

　・要素の数が多いとアウト
　・解を一つしか見つけることはできない
　・解があっても見つけられないことがある
　・死ぬほど遅い

===================================

「ソルバーは役に立たない」とかいうハナシではありません。

ソルバーは

　「少数のパラメータの変動にともなって、価値が連続的に変化する課題」

を解くには非常に有効かつ有用な機能です。

しかし、部分和問題のように

　「多数のパラメータが二値で切り替わり、かつ、価値が不連続に変化する課題」

を解くには不向き…というより、そもそもそんなことするための機能ぢゃありません。

「ExcelをWord代わりに使う人」見るとイラッときますよね。
「ボルト回すのにペンチを使う人」見るとイラっときますよね。
「カッターナイフで魚捌く人」見ると「ぅげっ」と思いますよね。

そういうハナシです。
33：_Kyle(1291004) :

2010/06/01 (Tue) 23:02:46

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275914508.gif ■ver.0.40
http://abyssinia2010.web.fc2.com/ssstmp/ver0_40.txt

たとえば

--------------
●課題Ｄ
10個の正整数　[要素]　{8,1,9,4,3,4,8,8,5,6}
の中から、重複を許さず、順序を考慮せず選んで、それらの和が、
[目標値]　1000 と等しくなる組合せ　[解]　をすべて求める。
--------------

というような課題の場合、
人間が見れば「解がない」ことが一目でわかりますが
k0SSS_0_30にはわからないので生真面目に探しちゃいます。

で、わかるようにしてやろうというハナシです。

--------------------------------

●総所要時間

　課題Ａ　470秒　⇒　0.2656 秒　wwww
　課題Ｂ　185秒　⇒　186秒
　課題Ｃ　3009秒　⇒　2974秒

●解一つあたりの探索時間

　課題Ａ　2.00秒　⇒　0.001135秒
　課題Ｂ　0.01171秒　⇒　0.01179秒
　課題Ｃ　0.18秒　⇒　0.18秒

●再帰回数

　課題Ａ　1,073,724,094　回　⇒　335,994　回
　課題Ｂ　　489,544,820　回　⇒　489,544,800　回
　課題Ｃ　8,076,310,793　回　⇒　8,076,310,793　回

--------------------------------

課題Ａ、いきなり１秒切ってしまいましたね。
思わず芝が生えてしまいましたが、真面目な数字です。

一方、課題Ｂ，Ｃの方は変化がありません。

課題Ｂは、要素の総和に対して目標値がかなり小さいので
「残りすべてを使っても足りない」という状況がほとんど発生しません。

課題Ｃは無数にある解のうちごく一部しか表示しませんが
「番号の若い要素を中心にした解」だけで１万６千以上あるので
結果として、表示される部分については違いが出ません。

--------------------------------

実装上のポイントは、
「残り全部の和」が幾らになるか、毎回計算していては日が暮れるので
【　ある要素以降の和が幾らになるのか、事前に計算して覚えておく　】
ことです。

--------------------------------

また、「要素を使い切ったらアウト！」判定が消えています。

要素を使いきった場合（　itmIdx > itmCnt　の場合）
sumAry(itmCnt+1)　はゼロですから
rmnSum　が正の場合　rmnSum > sumAry(itmIdx)　はTrueです。
つまり、判定　itmIdx > itmCnt　は　判定　rmnSum > sumAry(itmIdx)　に包含されます。

「要素を使い切った　⇒　残りの要素はない　⇒　残りの要素すべて使っても足りない」

　※追記　
　「要素を使い切ったらアウト！」判定は
　ver.0.20になった段階で不要でした　orz
32：_Kyle(1291004) :

2010/06/01 (Tue) 22:58:12

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275400693.gif 「コーディング編」が一段落ついて、ようやく「アルゴリズム編」です。
普通は逆な気もしますが…(汗

で、実際のところ、つか、例によって
「アルゴリズム」なんて言うほどたいしたハナシぢゃありません。

==========================================

課題Ａのスコアは現時点で470秒前後です。
これを0.08秒で処理するには6000倍のスピードで処理……できるわけがありません。
そこで【　処理の方を1/6000に　】減らそうというハナシ。

==========================================

基本的な考え方としては
　【　見込みのない枝は舐めない　】
これだけです。

言い換えると
　【　見込みのない枝がわかるようにする　】
ということです。

ただし、注意しないといけないのは
　【　再帰回数と単位処理時間は基本的にトレードオフになる　】
点です。当たり前ですが。

まめに枝を刈れば再帰回数は減らせますが
まめに枝を刈れば子Ｐは重くなります。
再帰回数が半分になっても、１度の再帰にかかる時間が倍になったら同じ事ですよね。

というわけで
　【　最初にわかることはあらかじめ計算しておく　】
のが実装上のポイントになります。

==========================================

スコアまとめ

現時点(ver.0.30)のスコアは以下の通りです。

●総所要時間

　課題Ａ　470秒
　課題Ｂ　185秒
　課題Ｃ　3009秒

●再帰回数

　課題Ａ　1,073,724,094　回
　課題Ｂ　　489,544,820　回
　課題Ｃ　8,076,310,793　回

●解一つあたりの探索時間

　課題Ａ　2.00秒
　課題Ｂ　0.01秒
　課題Ｃ　0.18秒　
31：_Kyle(1291004) :

2010/06/01 (Tue) 22:45:35

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275914291.gif 本編(?)に戻る前にいんたるーど。

　#　…いんたるーどの割に手間かかったけど。

『無限の猿定理』ってやつです。
http://ja.wikipedia.org/wiki/%e7%84%a1%e9%99%90%e3%81%ae%e7%8c%bf%e5%ae%9a%e7%90%86

「ランダムにいろいろ試したらそのうち当たるかも？」というハナシ。

==============================================

■ver.8.00　かなりお馬鹿なお猿
http://abyssinia2010.web.fc2.com/ssstmp/ver8_00.txt

やってることの割にやけに長いですが
動作仕様を『本編』に合わせたらこんなんなっちゃいました。
「難しいことしなくても…」とか言われますね、きっと。

【解一つあたり】の平均探索時間

課題Ａ　1018秒（5092秒／5件）　
課題Ｂ　∞秒（3600秒／0件)　１時間回して一つも当たらなかった。
課題Ｃ　∞秒（3600秒／0件)　これも。

参考１　k0SSS_3_00

課題Ａ　2.00秒（470秒／234件）
課題Ｂ　0.01秒（185秒／15801件)
課題Ｃ　0.18秒（3009秒／16382件)

　#　較べてどうすんだよ？

qa5212312のように
組合せの総数に比して解の割合が多いケースでは
普通に想像するよりかは当たります。

参考２　qa5212312
k0SSS_8_00　172.2秒(1722秒／10件)
k0SSS_3_00　0.004秒（63秒／16382件)

　#　いや、だから較べちゃダメだってww
　#　…てか、k0SSS_3_00はこの時点でこのスコアですよ、御大。

==============================================

で、一口に「打鍵猿」と言っても実装上の選択肢はいろいろあるわけで
たとえばこういう選び方をすればけっこう速くなります。

■ver.8.10　少しお利口なお猿
http://abyssinia2010.web.fc2.com/ssstmp/ver8_10.txt

　【　毎回全部ランダムに選びなおすんじゃなくて
　　　変えるものをランダムに選んで差分だけ計算すれば
　　　単位時間当たりに試せる組合せが増えるよね　】

というハナシ。

課題Ａ　1.82秒（182秒／100件）　ただし100件中92件が重複。正味8件。
課題Ｂ　∞秒（3600秒／0件)　これは無理
課題Ｃ　∞秒（3600秒／0件)　これもw
qa5212312　0.074秒（74秒／1000件)　ただし1000件中798件が重複。正味202件。

　#　…てか、打鍵猿でこのスコアですよ、御大。

==============================================

なお、いずれも重複判定していないので同じ解が複数回表示されます。

また、後半になればなるほど重複が増えて効率が悪化するので
単位所要時間に解の総数を掛ければ全部見つかるというわけではありません。

短所

　・当然ながら平均的には再帰よりかなり遅い
　・解がない場合に、解がないということが判らない
　・たとえすべての解をみつけたとしても、それで全部だということが判らない
　・同じ解を何度も見つける
　・ばかっぽい
30：_Kyle(1291004) :

2010/05/29 (Sat) 23:32:56

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275143576.png ホントのホントのホントは……

わたし、実際こういうレベルなんで、
「コード」も「騙り」も突っ込みどころ満載だと思います(^^;;;;;;;;;;;;;;;;

おひま～なときにでも、もしお気が向いたら突っ込んでくださると…

　　朝昼晩拝みます　<(_ _)>

というハナシでした　　o ....rz
29：_Kyle(1291004) :

2010/05/29 (Sat) 23:31:04

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275143464.gif ホントのホントは……

突っ込まれそうな部分についての言い訳、というか予防線だったりw

「LongよりIntegerの方が使用するメモリが少ないのだ！」
「Longの方が速いんです。」

「Variant型使えばループ回さなくても要素取れるよ！」
「Longの方が速いんです。」

「難しいことをしなくても、使った値をそのまま配列に入れれば良いのだ！」
「Booleanの方が速いんです。」

「なんでヒット処理をわざわざ別プロシージャにするわけ？ｗｗｗ」
「分けた方が速いんです。」

「Variant型で書き出すよりLong型で書き出す方が速いのだ！」
「変わりません。」

「StatusBarなんか使うと遅くなるし無駄です！」
「全体で最大２秒です。無駄じゃないです。」

「フラグ立てて戻らなくてもEndを使えばその場で終了します！」
「それだと他から呼べません。」

「親Ｐでエラートラップした方が軽いです！」
「それだと続行できません。」

「On Error GoTo 0 したらキャンセル以外のエラーが見えちゃいますよ」
「想定外のエラーはちゃんと見えないと困ります。」

というハナシ。

まぁ、ココで予防線張っても意味ないんですがw
28：_Kyle(1291004) :

2010/05/29 (Sat) 23:27:03

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275143311.gif 本当は…

　　【　ン十億回まわしてやっとこの程度の差なの？　】

って見方もできるというハナシ。

ン十億回まわしてこの程度の差しかでないんですから
１回あたりで考えれば無視できるほどの違いでしかありません。

速度気にする必要のない場面や、高々数十、数百回程度まわすような処理で、
【　目を吊り上げて最適化をギリギリ言い立てたところで意味ないよね　】
というハナシでもあります。

「●●は遅いのだ！」「○○の方が速いのだ！」
と、バカボンのパパ口調で言う前に
「速くないと困る部分、要素、場面なのか考えましょう」
というハナシ。

わたし、基本的に
『日本語変数』も『Variant型』も『暗黙の型変換』も『既定のプロパティ』も
好きなんですよね(ぇ

なにしろ

　【　コーディングに要する時間が短縮されますから　】

わたしが普段書いているコードってのは、
基本的に「売り物」じゃなくて「使う物」で
【今日】必要なコードを【今】書いてるわけですから、
コーディング時間ってのは動作速度以上に大事なんですよね。

たとえば、単発１回こっきりのデータ整形課題において
　Ａ：「２時間かけて書いた、５秒で処理できるコード」
　Ｂ：「１０分で書いた、処理に２０分かかるコード」
どちらが【速い】かは明らかですよね。

「○○するクセをつける」みたいなこと言う人もいますよね。
「他の言語に行ったときに困る」みたいなこと言う人も。

　【　みんながみんな　「いつかはC」　みたいなこと思ってるわけぢゃないよw　】

つか、「素人」プログラマではなく「初心者」プログラマなんだったら
VBAを入り口に選んでる時点で色々マチガえてますww
27：_Kyle(1291004) :

2010/05/29 (Sat) 23:23:36

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275143016.gif いや、
「このようにコーディングすべし！」という「まとめ」ではなくて
「コーディングはアルゴリズムと同じくらい重要」という「まとめ」

ver.0.20　⇒　ver.0.30　で
「アルゴリズム」はまったく変わっていません。
再帰呼び出しの回数も変わっていません。

　課題Ａ　1,073,724,094 回　⇒　1,073,724,094 回
　課題Ｂ　489,544,820 回　⇒　489,544,820 回

しかし、所要時間の方は

　課題Ａ　1087.67 秒　⇒　469.60 秒
　課題Ｂ　760.53125　⇒　184.53 sec.

とかなり短くなっています。

まぁ
「ver.0.20はわざと遅く書いてただろ！」とか
「普通ver.0.20みたいな書き方は最初からしない！」とか
言われたら一言もありませんが、とりあえず

　【　どれほど凄い（あるいは凄そうな）アルゴリズムでも、実装できなければ絵に書いた餅　】

　【　エレファントなアプローチでも、コーディング次第では意外と使える…こともある　】

　【　「所要時間」と「計算量」は、必ずしも比例しない　】

ということで。
26：_Kyle(1291004) :

2010/05/29 (Sat) 20:00:48

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275130848.gif ■ver.0.30
http://abyssinia2010.web.fc2.com/ssstmp/ver0_30.txt

課題Ａ　472秒　⇒　470秒
課題Ｂ　188秒　⇒　185秒
課題Ｃ　49分　⇒　51分

※所要時間の違いは基本的に誤差です。

・事前にA2セルをクリアするようにしました。
　不正終了したときに数字が残っちゃうので。

・「すべての解をみつけたのか否か」わかるようにしました。

あとREMいじったり、処理順変えたり。
25：_Kyle(1291004) :

2010/05/29 (Sat) 18:50:49

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275142575.gif データ型をユーザ定義して変数をまとめてみる

■ver.0.292
http://abyssinia2010.web.fc2.com/ssstmp/ver0_292.txt

普段あまりやらないんですが
モジュールレベル変数をずらりと並べると【怒られる】ので(ーー;)

課題Ａ　472秒　⇒　542秒
課題Ｂ　188秒　⇒　203秒
課題Ｃ　49分　⇒　54分

ん～…やっぱり【　却下　】w

=============================

【速度やスタックの問題をとりあえず度外視すれば】
rtnAry,rtnCnt,tmpAry,endFlgの４つについては引数にしてもいいと思うんですけど、
itmAry,itmCnt,rtnLmtみたいなのを引数にするのはどうも【気持ち悪い】んですよね。

rtnAry,rtnCnt,tmpAry,endFlgは処理が進むに従って動きますから
「この[状況]を処理せよ」って意味で引数にして渡すのは判るんです。
稟議書や出欠表を回覧してそれぞれに判押させたり記入させたりする感じですよね。

一方、
itmAry,itmCnt,rtnLmtは最初に設定してから動くことはありません。
Staticではありませんが（日常的な意味で）【静的な】値です。
電話帳や住所録みたいなものを回覧しますか？

そういう「普遍的で」「不変な」情報を
共有するのではなくリレーするのって
迂遠でエレファントな感じがするのはわたしだけかしらん？

電話帳や住所録の類いは
「必要になったときいつでもすぐ手に取れるところ」
においておくべきでは？

もちろん、値渡しではなく参照渡しの場合は
『電話帳』や『住所録』そのものではなく
いわば『閲覧許可資料一覧』を受け渡すわけですが

職員一人一人について『閲覧許可資料一覧』を作成・管理して
「事前に与えられた『閲覧許可資料一覧』に記載されていなければ、電話帳も住所録も閲覧不可」
「電話帳を閲覧したい者は、事前に『閲覧許可資料一覧』の改訂を上司に申し出よ」
「上司の『閲覧許可資料一覧』に『電話帳』が含まれていない場合は、更にその上司を通して許可を得よ」

って不便じゃないですか？

-------------------------------------

もちろん、大人数で作業する場合に
重要な資料を誰でも手にとれるところにほっといたら
「勝手に処分されたり」
「勝手に書き換えられたり」
「いつ処分されるか判らなかったり」
「処分して良いものか否か判らなくなったり」
というトラブルが発生するのはわかります。
実際よっくわかります(^^;;;;;;;;;

でも…

　　　　　【　独りで作業してるんですが　】

高々数個プロシージャが並ぶ程度のコードを独りでちまちま書いてるのに

「疑う人は、一度チームを組んで試してみるといいでしょう。確実に氏ねます(;_;)」

とか言われてもね(笑
24：_Kyle(1291004) :

2010/05/29 (Sat) 18:01:08

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275123668.gif モジュールレベル変数を参照渡しにしてみる。

■ver.0.291
http://abyssinia2010.web.fc2.com/ssstmp/ver0_291.txt

「モジュールレベル変数は親の葬式でもなければ使ってはならぬ！」
なんてことを家訓にしてる人もいるようなので…。

課題Ａ　472秒　⇒　553秒
課題Ｂ　188秒　⇒　246秒
課題Ｃ　49分　⇒　66分

ん～、こんだけ引数並べると呼び出し負担もかなりかかってるはずだから
比較としてフェアじゃない（？）ですよね。

そこで…
23：_Kyle(1291004) :

2010/05/29 (Sat) 16:37:30

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1275118650.gif 1000件ずつ書き込むようにする

■ver.0.29
http://abyssinia2010.web.fc2.com/ssstmp/ver0_29.txt

課題Ａ　472秒　⇒　472秒
課題Ｂ　188秒　⇒　188秒
課題Ｃ　49分　⇒　49分

　※やけにキレイに揃いましたが、ちゃんと測ってます。

「解を一件一件ちまちま書き出すのはマヌケだけど
　だからといって1万6千件一気に書き出すのはちょっとやりすぎだよね」
というハナシ。

課題Ｃみたいな規模の課題だと、dspAryがちょっとしたサイズになるため
【　動画やDVD見ながら動作させるとマズい　】かもしれないので(笑)

いや、冗談。
わたしの駄目な環境だと課題Ｃの「1000行×1万6千列」はけっこうイッパイイッパイです　orz

======================================

k0SSS_Dが復活した　orz

「もじゅーる化」とかそんな高尚(?)なハナシではなくて
なんかね、一つのプロシージャが40行超えると、
【PCではなくてわたしの】メモリがあふれちゃうのよね…ww

======================================

　#　なお、課題Ｃは「イルカが想定している最大規模の課題」とお考えください。
　#　「要素数Ｎ万」だの「解を行方向に100万件書き出す」だのといった課題は
　#　実務レベルでのニーズがちょっと考えにくいので…。
22：_Kyle(1291004) :

2010/05/28 (Fri) 02:28:20

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1276037294.gif [ESC]キーでendFlgを立てる。

■ver.0.28
http://abyssinia2010.web.fc2.com/ssstmp/ver0_28.txt

課題Ａ　438秒　⇒　472秒
課題Ｂ　171秒　⇒　188秒
課題Ｃ　45分　⇒　49分　

かなり遅くなった　orz　
でもやむを得ない。コレは必須。

-------------------

0.24以前のバージョンの場合、途中でBreakしても
それまでに見つけた解はその都度書き出してるので、当然表示されます。

しかし、0.25～0.27では、途中でBreakすると、
それまでに見つけた解は電子の泡になっちゃいます。
（ホントはBreakした後でも読めなくはないけど）

そこで、ESCキーでendFlgを立てて
途中でBreakした場合でも、それまでに見つけた解を書き出すようにしました。

-------------------

「中止？」に対して

　・[はい]　⇒　「中止します」　⇒　その時点までの解を書き出す
　・[いいえ]　⇒　「中止しません」　⇒　Stopして[中断]
　・[キャンセル]　⇒　「押し間違えた」　⇒　そのまま続行

という仕様デス。判りにくくてスミマセン。

-------------------

以下念のために。

・k0SSS_Cを切り出してるのは
　ver.0.23⇒0.24と同じく呼び出し負担軽減のためです。

　●ver.0.281
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_281.txt

　　課題Ａ　438秒　⇒　508秒
　　課題Ｂ　171秒　⇒　193秒
　　課題Ｃ　45分　⇒　52分

・親Ｐでトラップする方が速度面では有利ですが
　「続行」したときに「最初からやり直し」になります。

・「続行できない仕様にする」という選択肢もありますが
　「サンプルコードなのに中断できない仕様ってどうよ？」という判断と
　「フォーカスはずれて表示がマズくなったときに復帰する」機能も兼ねてるので。
　　　#　…つか、中断できないとわたしが困るｗ

・ヒットＰでのトラップを省くと、ヒット処理中に割り込まれた場合に
　二重処理が発生して結果がマズいことになる可能性があります。

・「割り込み以外のエラーは見せる」仕様…つかポリシーです。

-------------------

　#　ところで、そもそもトラップの仕方はこれであってるのかしら？(ぇ
　#　基本「トラブったら呼んでください」なスタンスなので
　#　ジツはエラートラップ書いた経験があまりなかったり　（ぉぃ

　#　でも、たいていの「エラー処理」って、単に、
　#　「エラー見せずに終わらせるだけ」か「不正な状態抱えたまま走り続けるだけ」の
　#　「臭いものにフタ処理」だよね　(ーー;)

　#　「エラー吐いて止まるコード」よりも
　#　「エラーも吐かずに止まるコード」や「不正な結果を吐くコード」の方が良い
　#　ってのはどういう感覚なんだろね？

　#　数式でもそうだよね。
　#　「どんなトラブルだろうと、とりあえず長さゼロの文字列を返す」ことの
　#　どこが一体「エラー処理」なのかわたしには皆目(ーー;)

============================

…というわけで、課題の性質上当然に「途中でBreakする運用」を念頭においているので
　・解が一つでも見つかっているのか、全く見つかっていないのか
　・解が無数にあるケースか否か
を判断するために、運用上【　進捗表示は必須　】なんです。
誰がどんな目線でなんと言おうと。
21：_Kyle(1291004) :

2010/05/27 (Thu) 20:55:46

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274961346.gif 終了フラグ用意して、いろいろちゃんと終わる

■ver.0.27
http://abyssinia2010.web.fc2.com/ssstmp/ver0_27.txt

課題Ａ　431秒　⇒　438秒
課題Ｂ　166秒　⇒ 171秒
課題Ｃ　45分　⇒　45分

遅くなった　orz

でもまぁ、End使うと【怒られる】のでしょうがないです(ぇ

…いや、冗談（^^;;;;;

End使うと、実際潰しが効かないので。
終了処理それぞれ必要になるし、他から呼べないし。

●ちゃんと戻ってから終わるならk0SSS_D要らないので廃止。

●ワークシートさわるのは親Ｐだけになったので
　optCelとitmCelをプロシージャレベルに変更。
　【　ご安心ください　】

●終了処理でモジュールレベルの配列をErase。
　【　ご安心ください　】　

●ScreenUpdating切ってないのにTRUEにしてるのは
　StatusbarをFALSEにしても時々残っちゃう対策。

　　#　なお、課題Ａ・課題Ｂいずれの場合も、
　　#　Excel2007で解く場合は列あふれはしないのでendFlgは立ちません。

　　#　また、速度上負担になっているのは
　　#　「endFlgに従って戻る処理」ではなく「endFlgが立ってるか判定する処理」です。
　　#　なにしろ、ン十億回*要素数とか、そういう単位で判定するので。

============================

実際のところ、
わたしはメモリのやりくりで苦労した世代じゃありませんし
業務内容からいっても、メモリが問題になるような処理は例外的なので
普段EraseとかNothingとかあまりしません(ぇ
　…それ以前に、[New]なんてめったにしないのでw

この課題にしたって、
基本的に【専用のブックで単体動作させる運用】を想定してるので
メモリなんてあまり気にしなくていい気もするんですけどね。

「プログラマとしての意識の問題」とか言われそうですけど、わたし意識低いのでw
メモリの無駄遣いが気になって仕方がないような「意識とレベルの高い人」は、
「舌打ちして【自分で】１行書き加えれば済む」ハナシですし。

　【　そんなにメモリが惜しいなら、Excel閉じちゃえばいいじゃない　】
　　　　　　　　　　　　　　　　　　　　（マリー=アントワネットの口調で）

でも、まぁ、「よそ行き用」コードってことで、一応。

　#　いっそのことitmCnt,rtnCnt,rtnLmt,endFlgも初期化しようかと思ったけど
　#　それはそれで神経症っぽく見られそうなので自重

　#　毎日デフラグかけたり、毎月クリーンインストールしたり
　#　メモリクリーナ常駐させたりするようなタイプの人、苦手だなぁ、わたしは。　
20：_Kyle(1291004) :

2010/05/27 (Thu) 19:34:58

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274956679.gif StatusBarに進捗を表示する

■ver.0.26
http://abyssinia2010.web.fc2.com/ssstmp/ver0_26.txt

課題Ａ　427秒　⇒　431秒
課題Ｂ　167秒　⇒　166秒
課題Ｃ　44分　⇒　45分

【　所要時間の違いは誤差の範囲デス　】

「固まったように見える」対策でStatusBarに進捗を表示するようにしました。
速度は変わらずですが【　体感速度５割マシ　】です……少なくともわたし的には。

「無駄な処理」「遅くなる」とか言って嫌う人もいるようですが
探索する解の個数は、最大でも16382組です。
更新は10件おきですから、更新回数は1639回。

判定も含めて、StatusBarを1639回更新するのに必要な時間は
わたしの環境で【 ２秒 】です。

動いてるのか動いてないのか、進んでるのか進んでないのか
状況が判らないまま何分もぢっと待つより
たとえ全体で【 ２秒 】遅くなっても進捗がわかったほうがうれしいなぁ
…と思うのはわたしだけですかね？

規模とか状況とか考慮せず、教条主義的・原理主義的に
【　コレはダメ、アレもダメ　】とか脊髄で判断する人、嫌いだなぁ、わたしは。

　#　ところで、Excel2007では、StatusBarの更新が物凄く遅くなってる？
　#　2003⇔2007で20倍くらい差が出るんだけど…　(ーー;)
　#　2003なら、1万6千回まるまる回しても1秒かかんないのに…。

　=============================
　ver.0.25で
　「解が無かったときに書き出し処理をスキップ」するの忘れてました。
　まとめるときに直します。
19：_Kyle(1291004) :

2010/05/27 (Thu) 06:37:30

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274909850.gif ver.0.20　⇒　ver0.24　で
課題Ａの方は順調に速くなっていますが、
課題Ｂの方はいまいち効果が小さいですよね。

　課題Ａ　約1200秒　⇒　434秒
　課題Ｂ　約780秒　⇒　432秒

ジツは、課題Ｂの場合、所要時間の大部分が書き出しに要する時間です。
探索処理が速くなっても、書き出す解の量は変わらないから全体として速くならないという…。

そこで…

==========================

結果を配列に格納しておいて最後に書き出す。

■ver.0.25
http://abyssinia2010.web.fc2.com/ssstmp/ver0_25.txt

課題Ａ　434秒　⇒　427秒
課題Ｂ　432秒　⇒　167秒　３分切った！　＼(^o^)／　www
課題Ｃ　59分　⇒　44分

当たり前っちゃ当たり前なんですが。

==================================================

でも、一口に「一気に書き出す」と言っても
選択肢はいろいろとあるわけで…。

●ver.0.251：　Long型に直接書いて貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_251.txt

　課題Ａ　437　434　438
　課題Ｂ　163　165　164

●ver.0.252：　Variant型に直接書いて貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_252.txt

　課題Ａ　423　426　419
　課題Ｂ　163　162　162

　#　ん？　Variantのが速い？　(ーー;)

●ver.0.253：　Boolean型に書いといてLong型に書換⇒貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_253.txt

　課題Ａ　425　423　428
　課題Ｂ　166　165　164

●ver.0.254：　Boolean型に書いといてVariant型に書換⇒貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_254.txt

　課題Ａ　434　431　433
　課題Ｂ　173　172　171　

●ver.0.255：　ジャグ配列にそのまま投げといてLong型に書換⇒貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_255.txt

　課題Ａ　436　424　428
　課題Ｂ　167　168　167

●ver.0.256：　ジャグ配列にそのまま投げといてVariant型に書換⇒貼り付け
　http://abyssinia2010.web.fc2.com/ssstmp/ver0_256.txt

　課題Ａ　423　427　425　
　課題Ｂ　166　167　167

というわけで、ちょっと胡乱な結果もありますが、
いずれにせよ大勢に影響ない感じですし
取り回しの良さと「見た目」を重視してver.0.256を採用。

==========================

…つか、Long型で貼るのはホントはマズかったのよね。

「課題」では「正整数」って断ってあるけど、
「要素に0が混じってる」場合に紛れちゃうし
後で使用要素数を調べるときに0が入ってると取り回し悪いし
そもそも「使ったものを書き出す」のが動作としては自然だしね。

速度的にはこれでとりあえず一段落。

==========================
　
ver.0.10以降のバージョンで
「列あふれエンドで解の個数を書き出す」処理を忘れてました　orz
まとめるときに直します。

==========================

　#　朝起きたとき、全部ちゃんと終わってるかドキドキしたww
18：_Kyle(1291004) :

2010/05/26 (Wed) 18:26:33

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274894318.gif 「イルカさん、何やってんの？」

「ぇっと
　【Excelでrecursive callするときに、
　　どんなcodeをどれくらいnestするとstackがoverflowするのか】
　ちょっと実験してるとこです。」

「……。あ、そう。がんばってね。」

　#　早口で言うのがコツです(ぇ

------------------------------------

で、

■test2
http://abyssinia2010.web.fc2.com/ssstmp/test2.txt

…という結果です。

今回は順当な(?)結果で安心しましたw
「当たり前の結果」とも言いますが…ww

　・子Ｐ内のプロシージャレベル変数が使ってるメモリはもちろんのこと
　　コード自体の【構文的サイズ】も、
　　【その部分が実行されるか否か／呼び出しの前か後かに関わらず】
　　スタック領域の消費に影響する

　・REM文や空行、インデント、変数名の長さなど、
　　子Ｐの【見た目の】サイズはスタック領域の消費に影響しない

　要は、アクティブなプロシージャは、コンパイル(?)されたカタチで
　まるっとスタックを占領するってことですね。

　ついでに

　・（スタック領域的には）参照渡しよりもモジュールレベル変数の方が有利

　・（スタック領域的にも）無意味な値渡しはマヌケ

　もちろん、だからといって、
　「参照渡しではなくモジュールレベル変数を使うベシ」とか、
　そういうハナシではありません、念のため。

　そもそも、普通はスタックあふれたりしませんしw
17：_Kyle(1291004) :

2010/05/26 (Wed) 18:14:35

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274865468.png 　>「列番号を格納する変数は、明示的にIntegerで宣言すべきな【のだ】」
　>なんてことをバカボンのパパ口調で言われて、
　>それを真に受けて書いたコードがExcel2007になって一斉にマズいことになってる悪寒。

ぇっと、列番号をIntegerに入れても
Excel2007でマズいことになったりはしませんね、全然　orz

「Byte型で十分」みたいな言説とごっちゃになってました(ぇ

--------------------------------

　※スレッドタイトル変更しましたww
16：_Kyle(1291004) :

2010/05/25 (Tue) 22:35:08

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274797622.png ヒット時の書き出し処理を外に出す

■ver.0.24
http://abyssinia2010.web.fc2.com/ssstmp/ver0_24.txt

課題Ａ　468秒　⇒　434秒
課題Ｂ　447秒　⇒　432秒
課題Ｃ　65分　⇒　59分　

課題Ｃ、１時間切った！　＼(^o^)／　www

なにしろ、ン十億回とかそういう単位で呼ぶので、
子Ｐをロード(?)する時間も馬鹿にならないというハナシ。

　　#　あと、きちんと検証してませんし、うろ覚えですが、子Ｐの（構文的な）サイズも、
　　#　スタック領域の消費に影響するような記憶というか経験則というか気配というか…。

もっとも、k0SSS_Hを呼ぶこと自体もコストになるので
スケールによっては無論トレードオフになります。
なんでもかんでも切り出せば速くなるというわけではありません。

　・親Ｐ　⇒　１回きり
　・子Ｐ　⇒　ン十億回
　・ヒット処理　⇒　1万6千回

というあたりを勘案して判断しないとね。

１万６千回【しか】実行されないコードを
ン十億回もロード(?)するのは無駄ということです。

…という以前に
ワークシートを触る部分と触らない部分を分けといた方が
あとあと潰しが効くってのも大きいです。
「もじゅーる化」ってやつですね（違？

----------------

寝ます
15：_Kyle(1291004) :

2010/05/25 (Tue) 19:16:51

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274865198.png ぇっと
　・ver.0.10
　・ver.0.20
　・ver.0.21
　・ver.0.22
　・ver.0.23
に記載した課題Ｂのタイムですが…【　真っ赤な嘘　】でした　orz

実は、Excel2007でテストできる環境・時間が限られているため
課題Ｂについては、Excel2007のない環境で動作テストしたり仮タイム出したりできるよう

【　各列ではなく各行に解を書き出すテスト用の別コード　】

で計測してたんですが(ぉぃ

【　列方向の書き出しって、行方向の書き出しより深刻に遅い　】

んですね。

http://abyssinia2010.web.fc2.com/ssstmp/test1.txt

全然知らなかった。　orz

…ってもしかして常識？

　#　常識、なんだろうなぁ…なにせ10倍超だもの…。
　#　一般論として「Excelの行列は非対称」ってのは基本ではあるけど
　#　まさか値入れるだけでこれほど差が出るとは…。

　#　おまけに、列方向の書き出し時間って
　#　UsedRange(?)の状態によっても変動する模様(ーー;)

　#　きっと、ReDim Preserve　の逆みたいな感じで
　#　内部処理的に、UsedRangeの行方向拡張は簡単だけど列方向拡張は手間かかるとか
　#　そんなハナシなんだろうなぁ。

　#　つか「列方向に書き出すか／行方向に書き出すか」なんてことは
　#　普通は要求仕様の段階で決まってるものだから
　#　「どちらが速いか」なんて考えたこともなかった　orz

　#　Excel2003以前なら、列方向って所詮256列までだから、目に見える問題って出ないしね。
　#　実務でもオフでも、いまだにメイン環境Excel2003時々2000ところにより2002な感じなので
　#　回答以外でExcel2007本格的に運用したことないのよね、実は。　orz

そんなわけで、課題ＢについてExcel2007でコードを実行しても
（もちろん環境にもよりますが）記載してた数字は出ないです。　orz

【違うコードで計測した数字】を、さも実測したような顔して挙げちゃいかんよなぁ。
倫理的に、人として、イルカとして。　＞　わたし

「あくまで仮コードの仮タイムのつもりで
　HPにまとめる段階できちんと再計測するつもりだった」
とか全然言い訳にならんよなぁ。　＞　わたし

「本コードも別コードも、実質的に同じ動作をするコードだと思い込んでいて
　Transposeかける分、別コードの方が遅くなることはあっても速くなることはないと思ってた」
とか全然言い訳にならんよなぁ。　＞　わたし

「どうせver.0.25で『一発書き出し』に変更するから
　当面の書き出し方は重要じゃないと思ってた」
とか全然言い訳にならんよなぁ。　＞　わたし

「どうせテスト環境も公開してないし、
　重要なのはver間の速度比であって、絶対数値は重要じゃないと思ってた」
とか全然言い訳にならんよなぁ。　＞　わたし

ホントスミマセン。海より深く反省します。 <(_ _)>

　　　　　　　　　　　　　....rz
　　o
------------------------------------

で、Excel2007での課題Ｂ実測タイムです。

　・ver.0.10　921.34375
　・ver.0.20　725.234375
　・ver.0.21　718.0117188
　・ver.0.22　562.171875
　・ver.0.23　446.109375

※なお、課題Ｃのタイムはもともと実測値です。
（要素数1000なので、横に並べても列あふれするので）
14：_Kyle(1291004) :

2010/05/25 (Tue) 07:01:31

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274784445.png Boolean型で結果を管理する

■ver.0.23
http://abyssinia2010.web.fc2.com/ssstmp/ver0_23.txt

課題Ａ　595秒　⇒　468秒
課題Ｂ×388秒　⇒　183秒　○563秒　⇒　447秒
課題Ｃ　89分　⇒　65分

…これも当たり前のハナシデス。

======================

結局寝れなかった　orz

…というより、中途半端な時間に寝ると朝つらいから途中で寝るの諦めたw

今夜は野球終わり次第寝るので、現れないかも。

========================================

■嘘つきイルカ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5412133
13：_Kyle(1291004) :

2010/05/25 (Tue) 05:11:12

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274800575.png itmAryをLong型にする

■ver.0.22
http://abyssinia2010.web.fc2.com/ssstmp/ver0_22.txt

課題Ａ　1017秒　⇒　595秒
課題Ｂ×445秒　⇒　388秒　○719秒　⇒　563秒
課題Ｃ　143分　⇒　89分

課題Ａ、10分切った！　＼(^o^)／

まぁ、当たり前のハナシなんですが、「こんなに違う」という意味で。

------------------

子Ｐと違い、親Pの処理は１度きりなので
親Ｐは少々冗長だろうが迂遠だろうが大勢に影響はない、というハナシでもあったり。

たとえば
要素をいったんVariant型でとってから、コード上でLong型に入れ替えれば
【理論上は気持ち速くなるかもしれませんが】
ソコで急いでもしょうがないですよね。

親Ｐは１回きり。
子Ｐはン十億回。

数式にしろマクロにしろ
「○○は速い／軽い」「●●は遅い／重い」
みたいな一般論を教条主義的・原理主義的に振りかざす人がいますけど
クリティカルな部分・要素・場面とそうでない部分・要素・場面があると思うんですよね。

「配列数式は重いからダメだ！」と言いつつCOUNTIFフィルする人とか
単発１回キリのデータ整形課題で速度や可読性や保守性に文句つける人とか
一体何が言いたいのやら…(ーー;)

========================================

■嘘つきイルカ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5412133
12：_Kyle(1291004) :

2010/05/25 (Tue) 03:36:37

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274816218.png Integer型をLong型に直す

■ver.0.21
http://abyssinia2010.web.fc2.com/ssstmp/ver0_21.txt

課題Ａ　1111秒　⇒　1017秒
課題Ｂ×457秒　⇒　445秒　○726秒　⇒　719秒
課題Ｃ　非対応　⇒　143分

「なんでIntegerよりもLongの方が速いのか」　
なんてことは、恥ずかしいのでいまさら触れませんが、

「Long型よりもInteger型の方が使用するメモリが少ない【のだ】」
なんてことをバカボンのパパ口調で言われるとイラっときますね、正直。

------------------------------

ようやく課題Ｃ対応になりました。　＼(^o^)／

でも死ぬほど遅いwww

死ぬほど遅いですが、しかし、
【　解を16382組見つけるのに143分　】
ですから、
【　解一つあたりの探索時間は0.5秒　】
です、念のため。　＞　ソルバー派のみなさま

========================================

■嘘つきイルカ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5412133
11：_Kyle(1291004) :

2010/05/25 (Tue) 03:32:57

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274725977.gif 「同じアルゴリズムでも、コーディングを見直すだけでだいぶ違う」
というハナシ。
「アルゴリズムの良し悪しが、コーディングの良し悪しでひっくり返ることもある」
というハナシでもあります。

わたしは元来コーディングについて語れるような立場の人間ではないのですが、
Integerとか使う人も時々いるので【　わたしにすら判る　】レベルで(^^;;;

なんか『コーディングの初歩』みたくなってますが
実験とか検証とかも兼ねてますのでご了承ください。

基本的には速度面での改善ですが、仕様面での改良もちらほら。

なお、もともとHP用に用意した原稿をもとにしてるので
ちょっと目線に角度がついていますが(?)
もちろんend-uさん向けではアリマセン、念のため。

で、もう一度速度テストしてから上げようと思うので、一つずつ分けます(ぇ
10：_Kyle(1291004) :

2010/05/23 (Sun) 23:14:44

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274965764.png ■ver.0.20
http://abyssinia2010.web.fc2.com/ssstmp/ver0_20.txt

マヌケ…というほどでもないんですが

　子Ｐは、【　呼ぶだけで時間喰う　】し
　ネストが深くなるほどスタック領域を消費するから
　「自身を使うか否か」で「狭く深く」分岐するよりも、
　「次に使うのは何か」で「広く浅く」分岐した方が賢いよね

…というハナシです。

また、今後いろいろいぢっていく上で、その方が取り回しが良いというのもあります。

課題Ａ　：　24分　⇒　20分　
課題Ｂ　：×11分　⇒　8分　○16分　⇒　13分

========================================

■嘘つきイルカ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5412133
9：_Kyle(1291004) :

2010/05/23 (Sun) 19:36:55

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274783693.png ■ver.0.10
http://abyssinia2010.web.fc2.com/ssstmp/ver0_10.txt

部分和問題を再帰処理で解く【　最も原始的な　】カタチです。

k0SSS_0_00（総当り）は「とりあえず全部決めてから判定」するわけですが
再帰処理の場合、各時点での[残和]が判るわけですから
「残和が負になっても選び続ける」ってのはさすがにアタマ悪すぎますよね。

　【　残和が０になったらヒット！　】
　【　残和が負になったらアウト！　】

たったこれだけのことです、基本的には。

---------------------------------

■課題Ａ

ジツは k0SSS_0_00（総当り） よりも遅くなります(ぇ

　k0SSS_0_00　：　約20分
　k0SSS_0_10　：　約24分

課題Ａを解く際に、子Ｐを呼ぶ回数
　k0SSS_0_00：　2,147,483,648　回
　k0SSS_0_10：　2,147,448,187　回

つまり、総当りとほとんど変わらない量を舐めているということです。

課題Ａのように【 要素のほとんどを使う 】課題では、
呼び出し回数が総当りに近くなるため
子Pの処理が重い分、所要時間が逆転してしまうことがあります。
　※この問題は上位バージョンで解決ズミ。

---------------------------------

■課題Ｂ

こちらは効果覿面ですね。
宇宙の寿命が尽きる前にちゃんと終わります。【　×11分　○16分　】
課題Ａ解くよりも早いですw

k0SSS_0_10が子Ｐを呼ぶ回数
　課題Ａ：　2,147,448,187　回　
　課題Ｂ：　　979,089,639　回

なので当たり前っちゃ当たり前ですが…。
　
課題Ｂのように【 要素のほとんどを使わない 】課題では、
「残和が負になった時点であきらめる」だけで
ほとんどの枝をバッサリ刈れるというハナシ。

========================================

■嘘つきイルカ
http://abyssinia.bbs.fc2.com/?act=reply&tid=2850777#5412133
8：_Kyle(1291004) :

2010/05/23 (Sun) 16:54:51

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274602008.png ばぐふぃくすとも言うw

■ver.9.01
http://abyssinia2010.web.fc2.com/ssstmp/ver9_01.txt

見直したつもりだったんだけどなぁ…　orz

たいしたミスじゃない(?)のでｺｯｿﾘ直しちゃおうかとも思ったけど
…この際だからついでに騙ろう(ぇ

---------------------------------

●総当たり法　＞　目標値と一致する物をすべて求める
http://www.geocities.co.jp/SiliconValley-Oakland/8139/soatari.html

の元コードでは
　N　　　：要素個数（≒　itmCnt）
　wa(N)　：要素配列（≒　itmAry）
をそれぞれモジュールレベルで宣言しているので
要素数を変更するたびにVBE開いてコード書き換える必要があります。

最初見たときは正直
　「　なんつーユーザフレンドリな…(ーー;)　」
と思ったのですが
どうも【　速度を稼ぐため　】にわざとそうしてあったようです。

　・動的配列よりも静的配列の方が読み書きが速い

のはまぁ、普通に考えてそういうもんだろうと思いますが

　・プロシージャレベルで宣言した静的配列よりも
　　モジュールレベルで宣言した静的配列の方が読み書きが速い

のはちょっと盲点でした(ぇ　…もしかして常識？

---------------------------------

そんなわけで、要素を格納する配列は
【モジュールレベルで静的配列として】宣言する必要があるのですが…

よく考えれば

　【　多めに宣言して、余った分は使わなきゃいいよね　】

どうせ30超えたらアウトなわけですし、
Long型高々30弱でメモリがどうこう言う時代じゃありませんし。

そんなわけで、ver.9.0　は、

　【　itmAryを、要素数に関わらず常に　1 To 30　で宣言して、itmCnt分使う　】

という仕様にしました。

要素数が10のときでも20のときでも、そのままで動作します。

---------------------------------

…なので、要素読み込むときに30まで回す必要なかった　orz

あと、DimになってたのをPrivateに直しました。気分の問題でw
7：_Kyle(1291004) :

2010/05/23 (Sun) 14:38:57

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274964512.gif ■ver.9.10
http://abyssinia2010.web.fc2.com/ssstmp/ver9_10.txt

「こんな方法もありますよ」な総当りコード。
ちょっと胡乱な感じもしますが、ある意味「基本」かも!?

k0SSS_9_00は
　「N桁の２進数を、N個の要素から選ぶ組合せとみなして、数値型変数で管理する」

というアプローチでしたが

k0SSS_9_10は【　逆　】に

　【　組合せを管理する要素数ＮのBoolean型配列を、N桁の２進数とみなしてインクリメントする　】

というアプローチです。

数値を組合せとみなすのではなく、組合せを数値とみなすというハナシ。
これならは簡単に要素数を増やせますよね。

しかも意外と(?)速いですｗ　課題Ａを13分。現時点で最速。
6：_Kyle(1291004) :

2010/05/23 (Sun) 13:00:41

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274964450.gif ■ver.9.00
http://abyssinia2010.web.fc2.com/ssstmp/ver9_00.txt

いきなりバージョン9.0
…ではなく、補数というやつで、バージョンマイナス1.0w

●ナップザック問題をExcelで解く
http://www.geocities.co.jp/SiliconValley-Oakland/8139/
にある
●総当たり法　＞　目標値と一致する物をすべて求める
http://www.geocities.co.jp/SiliconValley-Oakland/8139/soatari.html

を、動作仕様をこちらに合わせて書き直しただけのオマケコードです。

======================================

一口に「総当り」と言っても、どのように実装するかでけっこう違うというハナシ。

「総当り」をコーディングする際、一番アリガチな手法はやはり、このコードのように

　【　N桁の２進数を、N個の要素から選ぶ組合せとみなして、数値型変数で管理する　】

というやつですが、この手法は

　「ExcelVBAでは2^100といった大きな桁の数値を扱うのが困難」

という、PCの性能以前の【　言語上の制約で　】要素数を増やし難いという問題があります。

上記サイトのコードの場合、ビット比較とか結構高度(?)なことやってますが
要素数が30を超えると（当然ながら）Long型変数があふれてしまいます。

ときどき

　>総当り法はデータ数が30件程度と書かれていますが、
　>最近のPCの性能なら100件でも対応可能かも？

みたいな紹介する人がいますが……コード嫁！

　　#つか、いくらPCの性能が上がったと言っても
　　#2^(100-30)倍になったと考えるのは無茶だろｗ

======================================

また、実際のところ、このアプローチは「総当りとしても」あまり速くありません。
なにしろ【　その都度最初から足し上げる　】ことになるので。

課題Ａを解くのに、オリジナルコードの場合、78分かかりました。
　#k0SSS_9_00だと75分。…気持ちだけ速くなってますｗ

同じ「総当り」でも、k0SSS_0_00であれば20分弱ですから
数値割当方式だと、再帰の4倍時間がかかるということになります。

課題Ｂはもちろんオーバーフローします。PC買い換えてもダメですw
5：_Kyle(1291004) :

2010/05/23 (Sun) 02:27:14

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274593990.gif ■ver.0.00
http://abyssinia2010.web.fc2.com/ssstmp/ver0_00.txt

再帰でやるなら、なにも【わざわざ】総当りする必要はないんですが、一応キホンなのでw

　【　自身を使うか否かで分岐して、底まで行き着いたら判定して上がる　】

それだけ。

潜ってから「超えたか否か」を判定するのではなく
潜る前に「最後の要素か否か」を判定するようにすれば
呼び出し回数は半分になるリクツですが
あとあと判定を付け加える際に
このカタチの方が（わたし的に）コーディングしやすいので。

倍呼ぶと言っても、どうせ次の最初でトラップするので
実質的な負担はそれほど変わりません。

----------------------------------------

■課題Ａの場合

わたしのかなり駄目な環境だと20分ほど要しますが、一応終わります。

　2^31　＝　2,147,483,648　回　
子Ｐを呼んで、
　2^30-1　＝　1,073,741,823　通り　
をキッチリ調べます。

コレを最終的に0.08秒でやれるようにしようというハナシデス。

■課題Ｂの場合

　2^101　≒　2.535*10^30　＝　2,535,000,000,000,000,000,000,000,000,000　回　
子Ｐを呼んで、
　2^100-1　≒　1.268*10^30　＝　1,268,000,000,000,000,000,000,000,000,000　通り
をキッチリ調べ……ようとするので、実際にやると宇宙の寿命が尽きます、比喩でなく。

　#単純計算だと…40,000,000,000,000,000【年】くらい？

----------------------------------------

逆に言えば、調べる組合せの数は幾何級数的に変化するので
【　要素の個数が少なければ、コレで十分足ります　】

要素数が20個の場合、わたしのかなり駄目な環境でも【　1秒　】で舐め尽くします。
4：_Kyle(1291004) :

2010/05/22 (Sat) 23:44:04

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274775591.gif 数式

　=INT(RAND()*90000)+10000

で生成した　1000個　の正整数　[要素]　の中から、
重複を許さず、順序を考慮せず選んで、それらの和が、

[目標値]

　40000000

と等しくなる組合せ　[解]　を【　16382組　】求める。

========================

・求める解の個数は、設定列を除いたExcel2007の最大列数にあわせました。

・最も重い課題。運にもよりますが、ソルバーではたぶん無理。

・現時点の手元最速コードだと、指定の数だけ解を見つけるのに、書き出し時間含めて8分強。
　解一つあたりの平均探索時間は0.033秒
3：_Kyle(1291004) :

2010/05/22 (Sat) 23:22:29

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274775462.gif 100個の正整数

[要素]

　{
　63380,23430,59550,74120,90280,56900,32090,51020,97130,97740,
　75930,32380,32070,84090,67360,76750,85940,24770,97790,63630,
　70600,45180,76440,27560,70170,52480,44760,13740,50440,18370,
　27820,65040,47040,34570,52720,95930,99250,42900,57780,21950,
　98710,27400,62240,27220,50070,79450,80350,87890,64860,87670,
　77740,20400,62880,87970,34090,60640,93970,32900,44500,83560,
　89560,12320,41260,27710,21440,44680,15310,73220,67360,61180,
　38840,33770,13140,52140,30130,34670,54630,43360,94250,92450,
　77600,44900,80410,29180,63720,68470,78870,73460,88210,46530,
　50950,88740,59230,75210,34070,45210,58920,41690,97760,83070
　}


の中から、重複を許さず、順序を考慮せず選んで、それらの和が、

[目標値]

　209000

と等しくなる組合せ　[解]　を【　すべて　】求める。

========================

・解は15801組。Excel2007の最大列数にあわせました。

・標準の課題。ソルバーでも見つけられなくはないようです。

・現時点の手元最速コードだと、全部見つけるのに、書き出し時間含めて40sec.ぐらい。
　解一つあたりの平均探索時間は0.0025秒
2：_Kyle(1291004) :

2010/05/22 (Sat) 23:12:39

https://bbs9.fc2.com//bbs/img/_525600/525512/full/525512_1274775321.gif 30個の正整数

[要素]

　{
　560,1570,8550,8830,6460,780,2420,9490,3650,4960,
　9050,6770,6810,6570,1820,2240,4830,2060,1380,3480,
　4880,3590,7300,4230,1160,1190,1340,1140,4220,2070
　}

の中から、重複を許さず、順序を考慮せず選んで、それらの和が、

[目標値]

　110000

と等しくなる組合せ　[解]　を【　すべて　】求める。

========================

・解は234組。Excel2003以前の最大列数にあわせました。

・いっちゃん軽い課題。１つ見つけるだけならソルバーでも足ります。

・要素数が30個なのは、整数割当方式の総当りコードと比較可能にするため。

・現時点の手元最速コードだと、全部見つけるのに、書き出し時間含めて0.08sec.
　解一つあたりの平均探索時間は0.00034秒
  • 名前： E-mail(省略可)：
  • 画像：
Copyright © 1999- FC2, inc All Rights Reserved.