////////////////////////////////////////////////////////////////////
/*

    KAB-studio.h


    (C)KAB-studio 1999 - 2004 ALL RIGHTS RESERVED.
        http://www.kab-studio.biz/
        info@mail.kab-studio.biz

    送信日： 2004/07/19(Mon) No.266
    配信数： 2090
    発行元： まぐまぐ ( URL: http://www.mag2.com/  ID: 0000012198 )
*/
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
/*                ２００４年７月１９日（月）の更新                */
http://www.kab-studio.biz/index.html

・ほとはー８の１追加！
　三人合体ホットハーブに「８の１１ 添い寝レベル」を追加！
[ 三人合体ホットハーブ ]
http://www.kab-studio.biz/Comic/HotHerb/index.html


////////////////////////////////////////////////////////////////////
/*                        ちょお普通な日記                        */
http://www.kab-studio.biz/nikki2/index.html

2004/07/11 (Sun)
　AKIRA をリアルタイムで見て５時寝。表紙のデザインとかダビングとか
色々うだうだ。表紙のデザイン、あまり変わらなかった。その他色々こまご
ま修正。

2004/07/12 (Mon)
　ライフガードで水浸し。バグ＆仕様変更が増えまくる。１００人斬り。
ＧＩＲＬＳブラボーは湯気邪魔すぎ。部屋の片付けですっきりと。録画中の
不備。

2004/07/13 (Tue)
　バグ潰しで死ねる。へろへろ。今年前半のヒット数について。やっぱプロ
グラミング系が強い……。

2004/07/14 (Wed)
　バグ＆仕様変更をがーっと潰す。３連休取れそう。帰りにヨドバシで超硬
１０枚組３８００円購入。３連休の予定。らくえんやりたい。そして文字と
イラストの検索。

2004/07/15 (Thu)
　精神的に疲れた。バグが……仕様変更が増えていく……。来たら増えてる
し。等級アップ！　お給料増える？　ギャラクシーエンジェルは烏丸さんが
いい感じ。そして超硬。アマゾンで……。

2004/07/16 (Fri)
　３連休のためにバグ＆仕様変更を２桁潰す。よくやってるよ自分。カレー
にはチーズパン。３連休の予定。サーバーメンテナンスとからくえんとか
スーツとか。そして超硬とアマゾン。

2004/07/17 (Sat)
　午前中はうだうだと。午後はほとはー描き。描き上がってから横浜へ。
らくえん他購入。らくえん、面白いです。それを１１月までがーっと。
トリコロドラマＣＤ良かったです。


////////////////////////////////////////////////////////////////////
/*                         風雅、舞い                             */
http://www.kab-studio.biz/Novel/Fuga/index.html

■　第十章　剣と魔法　−１５−

　ため息をひとつついてから、
「全然便利じゃないから」
　嫌みというよりは、あきらめ。
「たとえば今の硬質化。別にどんなものにでも変化できるわけじゃない」
「そうなの？」
「あの硬い状態と、今の柔らかい状態、どちらかだけ。今より柔らかい状態
とか、全然違う物質には変えられない」
　体をかがめて、背負ってきたバッグを取る。
「それに、これ」
　バッグから取り出した大量の包み。それは全て、薬だった。
「先生が許可した時間は２４時間。そこまで伸ばせたのもこの薬のおかげ。
これを、４時間おきに飲まなきゃいけない」
　……。
「ごめん」
　……。
　プライバシーに触れた。減点１。謝罪。加点１。プラスマイナス、ゼロ。
　舞の本当にすまなそうな顔は、計算した上でのものとは見えない。
　もう一度、ため息をついて、
「やっぱり、変」
「え？」
「で、他に訊きたいことは？」
　と言いつつ、リシュネはまわりを見渡す。
「あ、そうそう、リシュネ、どうしてここがわかったの？　お母さんから訊
いた？」
　知っていそうな気もするが、知らないような気もする。何より、雅樹は教
えてない、と言っていた気がする。
「そう、今日はそのことを言いに来たの。電話もないし……」
　縁側をのぞき込む。外は土煙が少し舞っていて、風呂上がりにはいたくな
い。
「……何やってるの？　訊いてる人なんていないと思うけど」
「……椅子、ない？」
                                                              (続く)

////////////////////////////////////////////////////////////////////
/*                       #pragma twice                            */
http://www.kab-studio.biz/Programing/PragmaTwice/index.html

　Version 13.30
計算量と時間

「さて、今回はアルゴリズムを考えるうえで重要な【計算量】、そして処理
に掛かる時間の計算方法について考えます」
『それってやっぱり重要なんだね……』
「まず、アルゴリズムの【計算量】について」
『それって、検索するとどこででも出てくるね』
「アルゴリズムの処理にどれくらい時間が掛かるかの目安だからね。計算量
の書き方は」

O(？)

「みたいになります」
『……なんか数学っぽくて難しい……』
「アルゴリズムは数学の世界だからね。僕の方針としては、プログラムに必
要なことだけ勉強すればいいって考えているから、数学的なことは置いてお
きます」
『その方が助かるかも』
「 O は【オーダー】と読みます。問題は？のところ。基本的に、？の所に
は〈要素数の何乗〉が入ります」
『要素数、って配列の中身の数だよね。それの何乗……』
「具体例で説明していこうか。まず要素数を N とします。つまり 
int iAry[N] みたいな場合」
『うん』
「では例として Version 13.07 ( No.243 ) のバブルソートについて考えま
す。バブルソートは、右からふたつずつ比較して、右の方が小さかったら入
れ替える、というのを繰り返すというものでした」
『そうすると自然と左の方に小さいのが行ってるんだよね』
「まず１周目の比較について。１周目は N - 1 回比較します」
『あれ？　 N じゃないの？』
「ふたつずつ比較するんだから、 1 少なくなるでしょ。実際に試してみた
ときの例を追ってみて」
『あ、要素数５で４回しか比較してない……あー、〈間の数〉だけ比較す
るんだね』
「う、うん、そういうこと……かな。さて、２周目は、一番左に一番小さな
数が来てるからこれは比較しないので、 N - 1 - 1 = N - 2 回比較します」
『１回少なくなるんだね』
「それを繰り返すと、比較回数は」

( N - 1 ) + ( N - 2 ) + ... + ( 2 ) + ( 1 ) 

「となります。これを数学の公式で書くと」

N * ( N - 1 ) / 2

「になります」
『数学の公式……』
「まぁこれは当てはめちゃえばいいだけだから難しいこと考えないで。重要
なのはここからだから」
『重要？』
「すごく重要。と、その前に」
『その前に？』
「〈 A の x 乗〉を〈 Z ^ x 〉と書くとします」
『 2 の 4 乗なら 2 ^ 4 ってことね』
「そういうこと。で、さっきの式を計算すると」

( ( 1/2 ) * N ^ 2 ) - ( ( 1/2 ) * N )

「となります」
『ただカッコ開いただけだね』
「さて。ここで N を 1 から順に増やしてみます」

( ( 1/2 ) * 1   ) - ( ( 1/2 ) * 1 )
( ( 1/2 ) * 2   ) - ( ( 1/2 ) * 2 )
( ( 1/2 ) * 4   ) - ( ( 1/2 ) * 3 )
( ( 1/2 ) * 8   ) - ( ( 1/2 ) * 4 )
( ( 1/2 ) * 16  ) - ( ( 1/2 ) * 5 )
( ( 1/2 ) * 32  ) - ( ( 1/2 ) * 6 )
( ( 1/2 ) * 64  ) - ( ( 1/2 ) * 7 )
( ( 1/2 ) * 128 ) - ( ( 1/2 ) * 8 )

『 N ^ 2 のところがすごく増えてくね。二乗だから当然だけど』
「そう、そこが重要！！」
『え、なに？』
「 N がある程度大きな数の場合、 N ^ 2 の影響力が大きすぎて、これにか
けている 1/2 や、右側の - ( ( 1/2 ) * N ) がほとんど意味がなくなって
しまうんです」
『確かに二乗の前には微々たるものよね』
「そこで、この？の所には、意味がない部分を取り除いて」

O( N ^ 2 )

「と記述します」
『おー、他のをばっさり削っちゃうんだ』
「この考え方がとても重要なんです。アルゴリズムに限らず、プログラムは
for などのループで〈何乗〉の計算が簡単に発生します」
『２重ループで２乗、３重ループで３乗ね』
「この〈何乗〉というのは要素数が増えるとすごく計算量が増えます。だか
ら、個別の計算とかよりも、この〈何乗〉っていう点は常に気を付けておい
て」
『〈何乗〉の計算になったらすごく重くなる、ってこと？』
「そういうこと。プログラムの中で for や while を入れる時には、こう
いったことを常に頭の片隅に入れておいて」
『はーい、って言ってもそれって結構難しいよね……』
「優れたプログラマーの資質のひとつに〈危険察知能力〉があるかも」
『危険察知能力、ねぇ……』
「さて、このオーダーの話は机上の話です」
『机上の空論？』
「とまでは言わないけど、実際問題として、 N が１なのと１００万とじゃ
全然違うでしょ」
『それは違いすぎ……』
「でも現実ではそういったことも考えなきゃいけないから。実際にプログラ
ムを組む上で注意しなきゃいけないのは、オーダーの他には次の３つ」

・要素数
・処理に掛かる時間的コスト
・データ容量

「ひとつひとつ見ていこうか」

・要素数

『これが今言ってた１か１００万か、ね』
「そういうこと。アルゴリズムの多くは要素数がそのままループ数になるか
ら、要素数がいくつか、っていうのを考える必要があるかな」
『でもそれって決まってるものかな』
「その辺の切り分けが重要。まず、要素数の中にはプログラム上固定のもの
があります」
『固定？』
「たとえば〈月の数〉とか」
『あー、それなら１２固定だね』
「固定でないにしても、プログラム上、上限値が決まっている場合は多いか
ら、それなら時間がわかるよね」
『決まってない場合っていうのは？』
「一番多いのが、ユーザーが入力できたり、環境に依存したりする場合。
一番ありがちなのが、ファイル数。あるフォルダに入っているファイルをす
べて処理する、とか」
『ユーザーがいっぱいファイル入れたらすごいことに……ってこと？』
「そういうこと。ユーザーによってデータ数が可変になる場合、ユーザーは
上限とか全然気にしないから、そういう可能性があるかどうか常に気を付け
ておく必要があります」
『気を付けてどうするの？』
「方法はいくつかあるかな。ある一定以上の数なら処理前に警告する、上限
を設けて超えていたらエラーにする、途中でキャンセルできるようにする、
とか」
『キャンセルが一番楽そう』
「これは次の章で紹介する【マルチスレッド】を使うことになるから、その
ときに説明します」
『はーい』
「では次」

・処理に掛かる時間的コスト

「ズバリ言えば、メモリアクセスよりファイルアクセスの方が重い、ってこ
と」
『当然じゃない』
「そうなんだけど……たとえば O( N ^ 2 ) と O( N ^ 3 ) でも、もし
O( N ^ 2 ) がファイルアクセス、 O( N ^ 3 ) がメモリアクセスなら」
『計算量が少ない方が時間かかっちゃう、ってわけね』
「そういうこと。特にファイルをメモリ代わりに使ったりするとかなり重く
なるから」
『ファイルをメモリ代わり？』
「具体的に言うと【データベース】へのアクセス」
『データベース……きいたことあるしなんとなくわかるけどよくわかんな
い』
「データベースの説明はもう少し先になるかな。 C++ からのアクセスは面
倒だし……まぁ、思わぬことでファイルアクセスがあったりすると重くなる
から、どこでそういう処理をしているか気を付けてってこと」
『はーい』
「では最後」

・データ容量

「これは今の話と関係していて、たとえばファイルアクセスを減らすため
に、最初にファイルから全部メモリの構造体に入れてそれを処理する、と
いう方法があります」
『そうすればファイルアクセスなくなるもんね』
「ところが、その際のデータ容量がすごく大きいと、結局はファイルアクセ
スが発生して重くなっていまいます」
『え”、そうなの？』
「メモリに入りきらないデータはハードディスクに書き込まれるから」
『それがファイルアクセスになる……って、でもメモリって他のアプリとか
も関係してくるんでしょ？』
「そのとき動かしているアプリの数や占有されているメモリのサイズ、マシ
ンに積まれているメモリの容量、そういったものが関係してくるからプログ
ラムの側ではカバーしきれない部分もあります」
『そういう時にはどうするの？』
「そういうときのために〈最低メモリ容量〉とか書いてあるでしょ」
『あ、そういえばそうだね』
「まぁそれも目安にしかならないけどね。さて、こういった現実的な問題が
あるわけですが、できればすべてのループ、すべての処理でこういった点に
ついては考慮しておいてください」
『考慮するだけでいいの？　したら、なんか対処しなきゃいけないんじゃな
いの？』
「もちろんそうなんだけど、実は〈考慮しない〉っていうことが多いんだよ
ね……プログラムを作っているときって」
『……そういうもの？』
「まず動くものできなきゃしょうがないでしょ」
『あー』
「それに、関数から関数を呼び出すような場合、厳密には〈呼び出している
関数がどれだけ時間掛かるか〉っていうのを把握してなきゃいけないけど」
『それって大変だよね。関数が増えたら特に』
「だから現実的には難しいけど、それでも常に気にはしておいてください」
『はーい』

/*
    Preview Next Story!
*/
「次回でアルゴリズム編は最後です」
『３部構成みたいな感じだったから、思ったより早いかも』
「まぁもっと本格的にやったら１年掛かるだろうけど」
『うわ』
「ま、その辺ははしょるってことで」
『というわけで次回』
＜ Version 13.31 アルゴリズムのまとめ ＞
『につづく！』
「……まとめ、っていう割にはちょっとまとまってないかも」
『ダメじゃん』


////////////////////////////////////////////////////////////////////
/*                ２００４年７月２６日（月）の更新                */
http://www.kab-studio.biz/index.html

・ほとはーに１話追加予定
三人合体ホットハーブに一話追加予定。


////////////////////////////////////////////////////////////////////
/*                          ご注意！！                            */

・このメールを返信しないでください。
・ご意見・ご希望・ご感想は[チョー普通な日記]よりお送りください。
http://www.kab-studio.biz/nikki2/
・購読登録を解除したいときにはこのページで行なってください。
http://www.mag2.com/m/0000012198.htm
・解除は自分で行なってください。
・バックナンバーはこれらのページにあります。
http://backno.mag2.com/reader/Back?id=0000012198
http://www.kab-studio.biz/Freeware/index.html#MailMagazine


////////////////////////////////////////////////////////////////////
/*
    KAB-studio.h
      Weekly Mail Magazine.
      Written by Kaburaya Seiden.
      http://www.kab-studio.biz/Info/MailMagazine/

    (C)KAB-studio 1999 - 2004 ALL RIGHTS RESERVED.
        http://www.kab-studio.biz/
        info@mail.kab-studio.biz
*/
////////////////////////////////////////////////////////////////////

