帰ってきた徒然苔: 4月 2018

2018年4月27日金曜日

メモリに収まらない数量のソートが必要ならマージソートと組み合わせよう

悶絶しそうなコードを先日見たのでネタにさせていただきます。
どのように悶絶しそうになったかを書くとその人にバレるので話を一般化したうえでさらに別の例で当人にはまったく気づかれない話題に仕立てます。

膨大な量をソートしなくてはならず、メモリ量の制約から一括して行えない場合は分割してソートすればいいですよ、というお話です。

といっても、話は非常に簡単です。手順はこうです。

第一段階

残っている(初回なら先頭からの)未ソートのデータをとりあえずメモリに収まる分だけの量をソートします。ソートアルゴリズムは何でもいいです。クイックソートのライブラリはC言語にすらありますので適宜利用してください。
この際に使用するソート用の比較条件は第二段階で使いまわします。
1でソートした内容を、それぞれ個別にファイルに吐きます。便宜的にこれらのファイルをζとします。
データが尽きたら第一段階を終了し、第二段階に進みます。
1に戻る。

第一段階おわり。

第二段階として、いっぱいできているはずのファイルζをマージソートしていきます。

一つもファイルζがない場合は第二段階を終了します。
2つずつファイルζを開いて(便宜的にそれぞれa,bとします)、先頭から第一段階の1.でソートに利用したしたのと同一の比較条件に合致したデータを別ﾌｧｲﾙ(便宜的にcとします)に吐いていきます。
aしか開けない(bがない、つまり最後の一つの)場合、aをそのままcにリネームし、第二段階を終了します。
a,bどちらかのファイルが終端になったら、まだ終端に達していないほうの残りのデータをすべてcにコピーしたうえで、a,bの両者を削除します。
1に戻る。

第二段階が一回おわると、cが第一段階で出来たファイルζの半分の個数できているはずです。
ここで出来たファイルcをファイルζとみなし、また第二段階先頭に戻り、処理します。
これを繰り返し、最後にファイルcが1つだけになったらソート完了です。

これは基本中の基本なのでこの程度は当然思いつくと思います。
この工夫を考え付く人なら、以下は必要ないでしょう。
しかしながら、経験上、ファイルを扱う際に以下に述べる程度の工夫をしない人も多数見受けられ、絶句することがあります。
多分言語側がすべてやってくれるんだと過度の期待をしているものと思いますが、そもそもなーんにも考えてない可能性もあります(そうとしか思えない人が多すぎる(そしてそういう人に限って声だけ大きい))。
簡単ですが効果ある手法をご紹介します。
言語によらず、せめてこのくらいは最低限行いたいところです。

一つ。ﾌｧｲﾙIOはシーケンシャルアクセスになるように設計しましょう。
ランダムアクセスのほうが早い外部記憶装置(HDDやSSDなど)は存在しないからです。
一般的にHDDだけでなくSSDでさえシーケンシャルアクセスのほうが圧倒的に早いです。
いくらアルゴリズムを見直しても、どうしてもファイルに対してランダムアクセスをしなくてはならない状況に陥ったら、十分な大きさのメモリマップトファイル(posixならmmap,Win32APIならCreateFileMapping,javaならFileChannel,csharpならMemoryMappedFile)の利用を検討してください。
とはいえ、結局マップしなければならない箇所がコロコロかわるなら、効果は限定的です。出来ればマップ元データの構造の再検討をお勧めします。

一つ。ファイルIOの発生は極力控えましょう。
一般的に、ハードディスクはシーケンシャルアクセスであっても、いくら早くても転送速度は250MB/s程度です。大量のHDDでRAID0を組んで(ストライピングして)涙ぐましい努力を重ねても1GB/sなんてとてもではないけど届きません。
一方、メモリは今時古臭いDDR3-1600なシングルチャネルであっても12.8GB/s、ふつうはデュアルチャネルな仕様のマザーボードが多いでしょうから25.6GB/sの速度です。
まあ、比較にならない速度です。
従って、まずは本当に外部記憶に頼る必要があるのか、採用しようとしているアルゴリズムをよく見直してください。
そのうえで、どうしても必要ならメモリが許す限り先読み用バッファと書き込み用バッファを十分な量確保したうえでｼｽﾃﾑコール発行回数を極力減らしてください。
数バイトずつread/write(posix), ReadFile/WriteFile(Win32API)するなんて愚の骨頂です。最近の言語はよくできていて、大抵はリードバッファ、ライトバッファ付きのストリーム操作手段が用意されているはずです。たとえばcsharpだったらFileStreamのコンストラクタでバッファ量を指定できますしjavaならBuffered[Reader|Writer]で同様のことができます。C/C++ならmalloc()/newで自力で管理する必要がありますので、どうせライブラリが充実している言語を使うなら、その恩恵を十二分に享受したほうがお得です。というよりも、意識して使ってください。

一つ。開いたファイルは閉じましょう。
ガベージコレクタがいずれは閉じてくれるからいいって?
ほんとに?
忘れてただけなんじゃないの?!

一つ。OSが管理する資源には最後には結局OSのAPIがcallされます。
ファイルだろうがTCP/IPによる通信だろうがスレッド生成だろうがプロセス生成だろうが同じことです。
結局どんな高級言語でもどんな資源をどのように扱うのかを、きちんと最終的にはOS側のAPIが呼ばれてどうなるか理解したうえで設計しないとロクなもんにならんから油断しちゃいけないです。
たとえば身近なところではスレッド。余程の事はない限り必ず使うでしょう。
でも何かを勘違いしている人は声が大きい。たとえばcshrapならマルチスレッド処理にはイマドキThreadよりTaskを必ずつかえとか。でもGUIスレッドで時間のかかる処理を行うと動作が固まるので重い処理を行うワーカースレッドを起動して、GUIではそのワーカースレッドの進捗を表示するという場合も多いと思います。この場合、メインスレッドとワーカースレッドの二つだけが必要です。LongRunningをつけてもつけなくても結局残りのスレッドプールはまるまる無駄な資源となりますし、結局スレッド間通信はTaskだろうがThreadだろうがやることは同じです。Taskは細かい処理をわーっと並べてwait(join)する用途には最適ですが、一つの長大な時間のかかる処理のためには無駄が多すぎます。
もちろん、書きやすいというメリット(Task.Run(()=>{});と書けるのはとても楽ですよね)もあるし、高々無駄なスレッドプールがいくつか生成される程度の無駄なら無視できる、ということを理解したうえであえて使うというならわかります。
しかし、無条件に利用するとなるとこれは考え物です。
以前、Taskによるasync/awaitはスレッド生成のコストがかからないとか意味不明な発言を読んだことがあります。
最初はスレッドプールを使いまわすという意味で言っているのかと思ったのですが、どうも本気でスレッドを起こさないと思っているようでした。もしそうなら、E*菌とかス*ラー電磁波とか並みいるオカルト諸先輩方もびっくりなさることとおもいます。
折角ある脳みそですから使ったほうがいいと思います。多分。

2018年4月23日月曜日

javascriptのWorkerに触ってみた

まさか自分ごときがjavascriptでマルチスレッド処理をやろうと思うなんて夢にも思わなかったので覚書。

Worker使用の条

Worker構築直前まで、Worker用のコードはただのﾃｷｽﾄだ
メイン/ワーカースレッドはpostMessageだけが通信手段だ
postMessageで通信する内容は連想配列、配列の配列など多彩に使える。但し自作クラスインスタンスはそのままでは使えない
言い換えればpostMessageで通信する内容はJSONオブジェクトなどで[デ]シリアライズできる範囲であればなんでもイケル
実際にやってみるとどうということはない

以上です。
以下タワゴトです。まず、HTML5にはWorkerという別スレッドで実行させる仕組みがすでにあるそうです。
実際やってみたらInternet Explorer11でもChrome65でも全く問題なく動作してちょっと感動しました。

で、Workerって何だと。
まあ、スレッドです。
但し、豪華にメインスレッドとワーカースレッド間の通信機能付きなんですこれが。
お互いpostMessage()しあうだけで通信ができちゃう。

誤解を招く言い方をすると、Win32APIで例えるならば、メインスレッドとワーカースレッド間の通信にﾒｰﾙスロットやパイプを使う感じ。mutexやsemaphoreやcritical sectionでもってロックしてそのスキにオブジェクトのインスタンス丸ごといただき!!とはいかない。

というのは、複雑なオブジェクト、たとえばクラスっぽく実装したオブジェクトをやり取りすると、メソッド的な定義が全部undefinedになって受け渡されるので、結局はシリアル化可能な状態にして送受信しなきゃダメヨ、という制限があるということです。
※javascriptにクラス(ECMAScript 6 のsyntaxsugarを除いて)なんかない！ => ありません。オブジェクト指向継承モデルはjavascriptにはありません。以下プロトタイプベースのナニカを指していると思って、その前提でお読みください。

別のたとえをすると、C++のクラスのインスタンスをfwrite()でそのままファイルに吐きました!fread()で持ってきました!!うごきません!!!みたいな。こういう言われ方をすると「動くわけねぇだろ」って言いたくなるでしょ?でも高級言語をもっぱらお使いの人たちは「動いて当然」とまず思い込むようです。いくらなんでもJSONやらXMLやらでシリアライズする処理なんか普段お手の物のはずなんですが、スレッド間通信はそうあってはならないらしい。

裏を返せばそれだけの話で、メインスレッド/ワーカースレッド間通信はプロセス間通信とかノード間通信でソケットなどでおしゃべりすることをイメージしたほうが早いです。

実際にC#で実装したコードをNetjsでjavascript化した総当たりトーナメント関数をjavascriptでもスレッド化して、長時間かかる処理の進捗状況と、終了した場合はその結果を受け取る、という処理を書くのに1時間もかかりませんでした。
全部MDN Web Docsさんのわかりやすいドキュメントのおかげです。

Bloggerではjavascriptを気軽にjsファイルとして外部化すると設置する別サーバが必要になるので、全部同一ソースで行う前提での例をご覧いただきます。

まず、すごい時間がかかる処理をやるだけのクラスがあるとします。FillFieldと名付けます。

で、ワーカースレッド用のスクリプトを書きます。
たとえば以下のように。

<script id="workerscript" language="text/worker">
    // 進捗報告用コールバック。cnt=現在完了済みの作業量
    function progresscallback(cnt) {
        postMessage({ type: 1, value: cnt });
        return true;
    }
    // 計算終了報告用コールバック。objは演算結果が入っているクラス
    function successendcallback(obj) {
        postMessage({ type: 2, value: obj.GetPatternList() });
    }
    onmessage = function (event) {
        // メインスレッドからメッセージを受信した際に呼ばれるイベントハンドラ。
        // ここでは何も考えずいきなり時間がかかる処理を開始している
        var workerFillFieldObject = new FillField(
            event.data[0],
            new CropData(event.data[1][0], event.data[1][1], event.data[1][2]),
            event.data[2],
            event.data[3],
            event.data[4],
            event.data[5],
            event.data[6],
            event.data[7]);
        var rate = workerFillFieldObject.CalculationAmount / 1000;
        if (rate > 10000) {
            rate = 10000;
        }
        // FillFieldクラスのコールバックにコールバック先を登録している
        workerFillFieldObject.SetCallBack(progresscallback, successendcallback, rate);
        // これがでたらめに時間がかかる処理本体
        workerFillFieldObject.MakeHumusPattern();
    }
</script>

このコード、多くをFillFieldをnewするだけに費やしていることを見ても、えらい楽勝でしょう?
実際にやっていることは、FillFieldから呼ばれるコールバック、進捗報告と作業完了報告のために呼ばれるものが2つ定義してあって、あとはFillFieldクラスをnewして目的のメソッド(MakeHumusPattern)を実行しているだけ。
コールバック関数ではメインスレッドにpostMessageを投げつけているだけです。
ご注意いただきたいのは<script id="workerscript" language="text/worker">としてありますが、languageの右辺値が出鱈目です。
言い換えると、ﾌﾞﾗｳｻﾞがlanguage=""の中身の解釈方法を知らない必要があります。ワーカースレッド以外で実行されてほしくないからです。
右辺値にjavascriptとか書いてはいけません。ﾌﾞﾗｳｻﾞはその解釈方法を知っているからです。別にscriptでなくてもなんでもよくて、中身のﾃｷｽﾄだけが必要なので、実際にはhiddenなdivでもかまいません。当然、最終的にはjavascriptとして実行されますので何でもいいといってもテキストの中身は和文でも英文でも中文でもだめでjavascriptでなければなりません。

onmessageにいきなりメソッドを代入していますが、メインスレッドからpostMessageされた際の処理なので、複数のメッセージをメインスレッドから飛ばしたいなら工夫してください。
たとえば、上記の例でもワーカースレッドからメインスレッドに対して2種類のメッセージを連想配列(キーはtypeとvalue)を使用して発行しています。当然伝えたいのはvalueの右辺値ですが、そのvalueが何を意味しているのかを簡単にわかるようにするためtypeに番号を振ってあります。
まあ、通常、メインスレッドからのメッセージは「開始せよ」「一時中断せよ」「再開せよ」「死んでしまえ」くらいですかね。この場合は「開始せよ」というメッセージ以外想定していないコードです。

では、次にメインスレッド側でのスレッド起動処理を書きます。
まず、外部ファイルを使わない前提なので同一ソースから全部ワーカースレッドを実行するための「ﾃｷｽﾄ」を拾ってきます。
先ほど定義した<script id="workerscript" language="text/worker">は、そのﾃｷｽﾄのうち、ワーカースレッドとして必要な定義を記述してありました(今のところﾌﾞﾗｳｻﾞにも解釈されない単なるﾃｷｽﾄです)。
そのほかに、そもそもFillFieldクラスの定義も必要です。それは<script id="class_define_script" language="javascript">としてメインスレッドでも使えるように定義してあるものとします。

メインスレッドで見えるようなクラス定義になっていても、ワーカースレッドさんは見えません。そのため、ワーカースレッド用にも同一のソースファイル(のﾃｷｽﾄ)が必要となります。そのため、二か所に記述するのは間抜けなので、すでにメインスレッド用に定義してあるスクリプトを文字列として取り出すためclass_define_scriptというidを振ってinnerHTMLでテキストを吸い出す作戦です。

workerScript = workerscriptの中身の文字列 + class_define_scriptの中身の文字列;
var blob=new Blob([workerScript], { type: "text/javascript" });
でまずBlobを作っちゃいます。読んだ通り元ネタは文字列をくっつけただけです。
そのblobのURLを作って、そのURLからWorkerを作ります。
worker = new Worker(window.URL.createObjectURL(blob));
これだけです。

これで無事Workerができたので、workerでFillFieldクラスをnewできるだけの情報をpostMessageします。
ちょっとややこしい例になっていますが、ただの配列や配列の配列などは問題なくpostMessageでやり取りできる例としてみてください。postMessageしている内容は配列ですが、配列の中に配列があったりします。これでもOKです。
これで先ほど定義したWorker側のonmessageが呼ばれ(FillFieldがnewされ)処理が開始されます。

function exec() {
  // 一つ目のソースのﾃｷｽﾄを取得
  var class_define_script = document.getElementById("class_define_script").innerHTML;
 
  // 上記ﾃｷｽﾄと２つ目のﾃｷｽﾄを足す
  var workerScript = class_define_script + document.getElementById("workerscript").innerHTML;
  // ﾃｷｽﾄからBlobを作り、URLを作り、Workerを構築
  worker = new Worker(window.URL.createObjectURL(new Blob([workerScript], { type: "text/javascript" })));
  // Worker側でFillFieldクラスがnewできるように情報を送る
  worker.postMessage([fields_num,
    [cd.crop_name, arr, cd.manual_bonus],
    expectedCropYield,
    100,
    USE_HUMUS_FLAG[1],
    USE_HUMUS_FLAG[2],
    USE_HUMUS_FLAG[3],
    USE_HUMUS_FLAG[4]]);
  // Workerからメッセージを受信するためのイベントハンドラを定義
  worker.onmessage = function (event) {
    if (event.data.type == 2) {
      // Workerが成功終了した場合に受信する
        makelisttext();
        document.getElementById("button_exec").disabled = "";
    }
    else {
      // Workerから進捗報告を受けた際に受信する
        document.getElementById("exec_resultarea").innerHTML = "現在" + event.data.value + "%";
    }
  }
}

次にメインスレッド側でワーカースレッドからメッセージを受け取るために、worker.onmessageハンドラにイベントリスナを登録します。
先のWorker用コードではFillFieldクラスには進捗報告コールバック機能があるので、そのコールバック関数にそのままメインスレッドへのpostMessageを呼び出すだけの関数を与えてありました(FillField.SetCallBack())。このリスナでそのメッセージを受信を行うことができるようになります。
引数はeventだけのシンプルなものです。
先ほども見たように、ワーカースレッドからはメインスレッドに対してpostMessageのeventとして連想配列を投げつけてきます。進捗状況通知ならtype=1,終わりならtype=2といったように。
その連想配列がこのeventの中身です。
連想配列のキー名"type"という名前にイベント番号、キー名"value"という名前に実際の値を突っ込んどけば何種類のメッセージだってswitch文だけで処理できるサンプルになるというわけです。ここでは2種類しかないのでifなんですけど。

この際も、メインスレッド側でクラスのインスタンスを生成してそれをワーカースレッドに渡さなかったように、処理結果もワーカースレッドのクラスのインスタンスをそのままメインスレッドに投げてもそのままそのインスタンスのオブジェクトは利用できません。
ただ、クラスのインスタンスだとするとメソッドを除けば単純コピーされているので、それを再利用すると可読性は落ちますが手っ取り早いかもしれません。
たとえば、List<T>オブジェクトがあったとして、List.CountやList.Addなどのメソッドはundefinedとして飛んできますが、List<T>内部でarrayで管理していた場合、実際にはそのarrayはしっかりコピーされて飛んできます。それを再利用するということです。
自前で管理クラスなどを作るより、はるかに楽だと思います。C#等の言語とは違い、クラスメンバにprivateもpublicもprotectedも、アクセス制限はなーんにもないのでアクセスし放題です。
まあ、しつこいようですが可読性はガックリ下がりますので、その辺はある程度覚悟(二度とメンテしないと決意したとか)が必要になるかもしれません。

文章にすると長くなるなあ。まとめる能力が欲しい。
お伝え出来たという歯ごたえがまったくありませんが、実際にやってみると簡単ですよ、ということで、一つよろしくお願いいたします。

なお、実際の上記の例の実行例はこちらの記事です。

ここまでお読みいただきありがとうございました。

Visual Studio 2017(それ以前も)のIDEからはビルドイベントにbash(を含む64bitなコマンド)は使えない

小一時間も悩んであまりにも当たり前なことに気づいてしまった瞬間、そのあまりの恥ずかしさに悶絶したのでここに記録する次第です。

※ここで言うビルドイベントとは、例の「ビルドイベント[前|後]のコマンドライン」を指しています。
※bashとはWindows Subsystem for Linux(旧Bash on Ubuntu on Windows)のbashを指しています。

結論から申し上げます。
bashだけでなく、64bit向けにビルドされたあらゆるコマンドが使えません。

当たり前ですよね。
Visual StudioのIDEに64bit版なんかないんですから。
bashは64bit版しかないんですから。

呼べるわけないですよね!!!

以上です。
以下タワゴトです。

とあるプログラムの前処理にbash経由でperlを使いたいと思いました。
それを行うバッチを書いて、手動で起動するとばっちりでしたので、ビルドイベント前のコマンドラインとして設定しました。
そしてビルドすると・・・

1> 'bash' は、内部コマンドまたは外部コマンド、
1> 操作可能なプログラムまたはバッチファイルとして認識されていません。

と、こういうエラーが吐出されました。

面食らった私は以下のように思いました。

は?
ないの??
ないわけないでしょ???
なんでみえないの????
タスクスケジューラとかでも使えてるのに?????(←何の関連もない)

そこで、フルパスでC:\Windows\System32\bash.exeとか指定したりしたのですがやっぱりエラー内容が変わりません。

そもそも、ここで気づけばよかったんですよね。
エラーメッセージは見えないとかないとか一言も言ってなくて、「認識されていません」ときちんと正しい日本語で教えてくれているのでした。
それを勝手に勘違いしてなぜbashが見えないのだ～～～と悶えた挙句、そういえばIDEって32bit版だったよな～、ということを思い出して(時間経過を無視すれば)あっさり終了。
実行環境とアーキテクチャが違うﾊﾞｲﾅﾘ持ってくんなバカ、と叱られていたのにそれに気づけない間抜けさが身に沁みます。

ちなみに、そのバッチ内で
echo %PROCESSOR_ARCHITECTURE%
とやると、キッチリx86と表示されました。当たり前ですが。
(64bit環境下だと環境変数PROCESSOR_ARCHITECTUREにはAMD64が入っています)

あまりの自分のふがいなさに、ちょっと鼻血が出そうになりました。

IDEの前処理欄を使用するといろいろ都合がよかったので、結局perlで書いたスクリプトはcsharpで書き直してしまいました。
当ブログの趣旨に沿った行動ができました。心からﾊｽﾞｶｼｲです。

2018年4月18日水曜日

Netjsに変換する際に起きた配列関連のトラブル2件とその対応

1. List<>とarray[]が混在しているとTypeScriptへの翻訳がうまくいかない

例えばC#で次の型があったとします。
List<List<byte[]>> arraylistlist = new List<List<byte[]>>();

で、ﾘｽﾄ0要素目->子ﾘｽﾄﾘｽﾄ0要素目->子配列0番目にアクセスしたいと思ったとします。
するとC#では次のように書けます。

byte val = arraylistlist[0][0][0];

ですが、この書き方ですと、NetjsのTypeScript翻訳結果は次の通りになり、うまくいきません。

var val : number = arraylistlist.get_Item(0).get_Item(0).get_Item(0);
理由は、number[]型にget_Itemというメソッドがないからです。

本来は次のように翻訳されるべきです。
var val : number = arraylistlist.get_Item(0).get_Item(0)[0];

TypeScriptは自動生成されるものなので生成後のTypeScriptを手動で修正するのは極力避けたいですよね。
この解決策は容易です。
単純にC#側のコードを2行に分けるだけです。
具体的には
byte[] bytearray = arraylistlist[0][0];
byte b = bytearray[0];
というふうに。
すると、次のように正しく翻訳されます。
var bytearray : number[] = arraylistlist.get_Item(0).get_Item(0);
var val : number = bytearray [0];

2. array.CopyToがない
たとえばC#で以下のようなコードを書いたとします。
byte[] bytearray = new byte[10];
bytearray.CopyTo( dst, 0 );
すると、次のようにTypeScriptに翻訳されます。
var bytearray : number[] = new Array<number>(10);
bytearray.CopyTo(dst, 0);

bytearray はTypeScriptでのnumber[]型なので、CopyToというメソッドを持っていません。 number[]はTypeScriptの基本型なのでNetjsそのものの改造が必要になると思うので、直接対応するには敷居が高そうです。
そこで、Array.CopyToをBuffer.BlockCopyとして書き直してやったうえでmscorlib.tsに次を追記してあげるとうまくいきます。

class Buffer extends NObject
{
  static BlockCopy(src: any[], srcOffset: number, dst: any[], dstOffset : number, count: number ): void
  {
    for (var i = 0; i < count; i++) {
      dst[ i + dstOffset ] = src[ i + srcOffset ] ;
    }
  }
}

まあそんな感じです。
個人的には次にNetjsを使用することはないと思いますが一応。

C#素人が陥ったﾊｽﾞｶｼｲ失敗

ひとつ前の記事でご紹介したjavascriptの生成元はC#なのですが、それを作成する際にかいた恥を２つご紹介します。
まあ、そりゃそうだよね、というものばかりです(以下の記事で使ったデータを出したプログラムは文末に付録としてご覧いただけます)。

１．インスタンスの生成時間が異常に遅い
例えば1単位当たり5個のint型で表せる大量のデータのリストが欲しくなったとします。
その場合、1単位を表すには以下のケースが考えられます。

case1:5つのデータを持つクラス

class TestObject1 {
  public int data1;
  public int data2;
  public int data3;
  public int data4;
  public int data5;
}

case2:int[5]を持つクラス

class TestObject2
{
  public int[] datas = new int[5];
}

case3:intの配列

1	`int[] datas =` `new` `int[ 5 ];`

case4:5つのデータを持つ構造体

struct TestStruct1
{
  public int data1;
  public int data2;
  public int data3;
  public int data4;
  public int data5;
}

上記のケースごとにSystem.Collections.Generic.Listを作成する時間を計測してみました。

追加要素数	5,000,000
追加要素	10回平均値 (単位:ミリ秒)
Case1: TestObject1	528
Case2: TestObject2	1,084
Case3: int[5]	694
Case4: TestStruct1	76
追加要素数	10,000,000
Case1	1,064
Case2	2,173
Case3	1,379
Case4	152
追加要素数	20,000,000
Case1	2,005
Case2	4,131
Case3	2,682
Case4	306

こんな単純なクラスなのに、これほど劇的な違いが生まれてしまいます。

ケース３のList<int[]>ですが、「ふーん、int[]のAddのほうがただのクラスより遲いんだねー、使うのやめとこ」と判断する前に、そもそもこの使い方は誤っています。

実際には5バイトのint[]をリストに追加しまくるのは無駄です。こうするべきです。

Case3A: int[] array = new int[ 5*追加要素数 ];

すると、インスタンス生成に係る回数は1回、必要な時間はほぼゼロ。

上限数が分かっていれば、速度だけで言えばこれ以外の選択肢はありません。

但し、デメリットもまた多いです。

まず、配列だけ見てもなにを表しているのかパッと見わかりません。データの取り扱い方法は工夫する必要が出てくるでしょう。

また、処理中に追加要素数が上限を超えたなら、当然arrayを自力で拡張する必要があります。

素直にCで組んだほうがいいと思います。

また、ケース2は最悪です。自インスタンス生成時間にメンバのint[5]のインスタンス生成時間が加わるため、見事に実行時間がケース1の倍になっています。

ケース４の構造体の早さは圧倒的です。おまけにデータ加工用のメンバ関数などのオブジェクト指向の恩恵も得られるので、わざわざC#を使うならこれを採用したいところです。

自分の場合は、今回はケース1からケース3Aに変更しました。その時の劇的な処理速度向上への驚きがこの記事を書いたきっかけです。おﾊｽﾞｶｼｲ。

2.Math.Ceilingを使ってもそこまで遲くない

私は古い世代なので、浮動小数演算を避けたくなってしまう癖があるのですが、念のため計測してみました。

演算回数	5,000,000
関数名	10回平均値 (単位:ミリ秒)
整数版CEIL	30
Math.Ceiling	35
演算回数	10,000,000
整数版CEIL	62
Math.Ceiling	71
演算回数	20,000,000
整数版CEIL	121
Math.Ceiling	143

確かに、ほんのわずかに速いものの、ほとんど変わりません。

但し、上記結果はReleaseビルドでの結果です。Debugビルドでの結果はｲﾝﾗｲﾝ化がされない等の影響からか整数版CEILは致命的に遲くなります。

演算回数(Debugビルド)	5,000,000
関数名	10回平均値 (単位:ミリ秒)
整数版CEIL	259
Math.Ceiling	54
演算回数(Debugビルド)	10,000,000
整数版CEIL	486
Math.Ceiling	108
演算回数(Debugビルド)	20,000,000
整数版CEIL	973
Math.Ceiling	219

素直にMathライブラリを使ったほうがいいですね。

見る人が見たら何言ってんだ、と言われるようなことばかりなのでしょうが、恥をさらす当ブログの趣旨によりここに記録する次第です。
普段使うことがないので、勉強になりました。

ふろく：上記図表の計測プログラム

class Program
  {
    static void Main( string[] args )
    {
      test test = new test();
      test.run( 5000000 );
      test.run( 10000000 );
      test.run( 20000000 );
      Console.WriteLine( "Hit ANY KEY" );
      Console.ReadKey();
    }
  }
 
  class test
  {
    class TestObject1 {
      public int data1;
      public int data2;
      public int data3;
      public int data4;
      public int data5;
    }
    class TestObject2
    {
      public int[] datas = new int[5];
    }
    struct TestStruct1
    {
      public int data1;
      public int data2;
      public int data3;
      public int data4;
      public int data5;
    }
 
    List<TestObject1> list1 = new List<TestObject1>();
    List<TestObject2> list2 = new List<TestObject2>();
    List<int[]> list3 = new List<int[]>();
    List<TestStruct1> list4 = new List<TestStruct1>();
    Stopwatch sw = new Stopwatch();
    void Elapse()
    {
      Console.WriteLine( $"　{sw.ElapsedMilliseconds}ミリ秒" );
    }
      void case1( int cnt )
    {
      for(int i=0;i< cnt; i++ ) {
        TestObject1 o = new TestObject1();
        o.data1 = i;
        o.data2 = i;
        o.data3 = i;
        o.data4 = i;
        o.data5 = i;
        list1.Add( o );
      }
    }
    void case2( int cnt )
    {
      for ( int i = 0; i < cnt; i++ ) {
        TestObject2 o = new TestObject2();
        o.datas[ 0 ] = i;
        o.datas[ 1 ] = i;
        o.datas[ 2 ] = i;
        o.datas[ 3 ] = i;
        o.datas[ 4 ] = i;
        list2.Add( o );
      }
    }
    void case3( int cnt )
    {
      for ( int i = 0; i < cnt; i++ ) {
        int[] datas = new int[ 5 ];
        datas[ 0 ] = i;
        datas[ 1 ] = i;
        datas[ 2 ] = i;
        datas[ 3 ] = i;
        datas[ 4 ] = i;
        list3.Add( datas );
      }
    }
    void case4( int cnt )
    {
      for ( int i = 0; i < cnt; i++ ) {
        TestStruct1 o;
        o.data1 = i;
        o.data2 = i;
        o.data3 = i;
        o.data4 = i;
        o.data5 = i;
        list4.Add( o );
      }
    }
    void case5( int cnt )
    {
      for ( int i = 0; i < cnt; i++ ) {
        TestStruct1 o;
        o.data1 = i;
        o.data2 = i;
        o.data3 = i;
        o.data4 = i;
        o.data5 = i;
        list4.Add( o );
      }
    }
    int CEIL( int val, int mul10 )
    {
      int ret = val * mul10;
      if ( ret % 10 != 0 ) {
        ret += 10;
      }
      return ret / 10;
    }
    void mathCase1(int cnt)
    {
      for ( int i = 0; i < cnt; i++ ) {
        TestStruct1 o;
        o.data1 = i;
        o.data2 = CEIL( i, 15 );
        o.data3 = CEIL( i, 16 );
        o.data4 = i * 2;
        o.data5 = CEIL( i , 22 );
      }
    }
    void mathCase2( int cnt )
    {
      for ( int i = 0; i < cnt; i++ ) {
        TestStruct1 o;
        o.data1 = i;
        o.data2 = (int)Math.Ceiling( i * 1.5 );
        o.data3 = (int)Math.Ceiling( i * 1.6 );
        o.data4 = i * 2;
        o.data5 = (int)Math.Ceiling( i * 2.2 );
      }
    }
    void interval()
    {
      int WAITSEC = 5;
 
      GC.Collect();
      Console.WriteLine( $"Wait for {WAITSEC}seconds..." );
      Thread.Sleep( WAITSEC * 1000 );
    }
    delegate void cases( int cnt);
    void job(string titile, int cnt, cases c, Object listobj)
    {
      int LOOPCNT = 10;
 
      Stopwatch stopwatch = new Stopwatch();
      MethodInfo mi = null;
      if ( listobj != null ) {
        Type t = listobj.GetType();
        mi = t.GetMethod( "Clear" );
        t.GetProperty( "Capacity" ).SetValue( listobj, cnt, null );
      }
      stopwatch.Start();
      for ( int i = 0; i < LOOPCNT; i++ ) {
        c( cnt );
        if ( listobj != null ) {
          mi.Invoke( listobj, null );
        }
      }
      stopwatch.Stop();
      Console.WriteLine( $"{titile}:{LOOPCNT}回平均値: {stopwatch.ElapsedMilliseconds/ LOOPCNT}ms" );
 
    }
    public void run(int loopcnt)
    {
      Console.WriteLine( $"追加要素数:{loopcnt}" );
      job( "Case1", loopcnt, case1, list1 );
      job( "Case2", loopcnt, case2, list2 );
      job( "Case3", loopcnt, case3, list3 );
      job( "Case4", loopcnt, case4, list4 );
 
      job( "整数版CEIL", loopcnt, mathCase1, null );
      job( "Math.Ceiling", loopcnt, mathCase2, null );
      interval();
    }
  }

登録: 投稿 (Atom)