JavaScriptでわかる!組込みプログラミングの神髄

第3回 処理をまとめて,細かく実行するには?

この記事を読むのに必要な時間:およそ 4 分

はじめに

この特集もいよいよ最終回となりました。今回は,⁠まとめて処理」「細かく処理」にするテクニックを2つ紹介します。とくに最後のものは「リングバッファ」と呼ばれ,組み込みシステムではよく使われるものです。

では,さっそく見ていきましょう。

時間がかかる処理の例

前回まで取り上げてきたサンプルプログラムは「ある時間待つ」というものでした。たとえばメトロノームは,拍子のタイミングを待ったり,キーリピートのタイミングを待ったりという処理でした。

今回扱うのは「時間がかかる処理」です。キー入力を待っている間に,できるだけ進めておきたいような処理です。たとえば電子辞書などでは,文字を入力している途中でも検索結果が表示される,インクリメンタルサーチ機能があります。また,かな漢字変換でも,変換キーを押す前に辞書を先読みして,応答を早くしています。

時間がかかる処理のサンプルとして,素因数分解を取り上げてみました。素因数分解というのは,たとえば「12 =2 * 2 * 3」というように自然数を素数の積に分けるものです。SSL通信のような公開鍵暗号にも,素因数分解の性質が利用されています。

リスト1 fipn.html

<HTMLM><HEAD><TITLE>factorization in prime numbers</TITLE>
<SCRIPT type="text/javascript"><!--

var        inputnumber = 0;
var        current = 0;
var        divider = 0;

function        int_t0()
{
        for (var i=0; i<100; i++) {
                if (divider == 0)
                        return;
                if (divider > current) {
                        document.getElementById("output").innerHTML += ";";
                        divider = 0;
                        return;
                }
                if ((current % divider)) {
                        divider++;
                        continue;
                }
                current /= divider;
                s = document.getElementById("output").innerHTML;
                if (s != "")
                        s += " * ";
                s += divider;
                document.getElementById("output").innerHTML = s;
        }
}

function        press(val)
{
        if (val < 0)
                inputnumber = 0;
        else
                inputnumber = inputnumber * 10 + val;
        document.getElementById("input").innerHTML = inputnumber + " = ";
        document.getElementById("output").innerHTML = "";
        current = inputnumber;
        divider = 2;
}

function        init()
{
        setInterval(int_t0, 100);
}

// --></SCRIPT>
</HEAD><BODY onload="init()">
<H1>factorization in prime numbers</H1>

<P><SPAN id="input">
<SCRIPT type="text/javascript"><!--
document.write(inputnumber);
// --></SCRIPT>
</SPAN><SPAN id="output"></SPAN></P>

<P><BIG><BIG>
<SCRIPT type="text/javascript"><!--
for (var i=0; i<10; i++)
        document.write('<SPAN onmousedown="press(' + i + ')">[' + i + ']</SPAN>');
// --></SCRIPT>
<SPAN onmousedown="press(-1)">[C]</SPAN>
</BIG></BIG></P>


</BODY></HTML>

テンキー部分をクリックすると,数字が入力されます。同時に計算が行われ,進行状況が表示されます。計算途中でさらに数字を入力すると,最初から計算をしなおします。

プログラムは,100ミリ秒ごとのタイマー割り込みで100回の計算を行い,リターンしています。つまり,1秒に1000回計算を行うことになります。組込みシステムの場合はタスクを利用して行うことが多いのですが,OSがない環境で優先度を扱う場合は,このように処理を分割しなければならないこともあります。

処理を分割するやり方ですが,関数からリターンしても,次に関数が呼ばれたときに続きの計算ができるように,計算の進行をグローバル変数に保存しています。関数からいったんリターンしないといけないので,再帰処理などはグローバル変数をスタックとして使い,関数そのものを再帰呼び出ししないように直す必要があります。

計算途中で数字が入力されたときは,グローバル変数をリセットして,次のタイマー割り込みのときに最初から計算されるようにします。もしタイマー割り込みではなく,タスクでこれを行っている場合は,グローバル変数に「設定が変更されたフラグ」を用意し,計算の途中でときどきこれをチェックして,必要ならば計算をやり直すようにします。

ソートアルゴリズムの比較デモ

ちょっと特殊な例ですが,ソートアルゴリズムをグラフィカルに表示するデモです。これは別のところで公開したものですが,JavaScriptだけでできています。

バブルソート,選択ソート,マージソート,クイックソートの4つについて,ソートのようすを棒グラフで表示しています。

同時進行させるには,それぞれのアルゴリズムを1ステップずつ進めないといけないのですが,1ステップで行う比較や交換の回数は,ソートアルゴリズムによって異なります。各アルゴリズムを1ステップずつ実行したのでは,公平な比較になりません。そこで,比較や交換のたびにカウンタを増やし,タイマー割り込みの都度,どのアルゴリズムも同じだけカウンタが進むように調整しています。

著者プロフィール

木元峰之(きもとみねゆき)

独立系ソフトハウスに8年間勤務,パッケージソフトの開発や記事執筆などを行う。現在はフリーのコンサルタント。SWESTなどのワークショップで分科会のコーディネータを務める。デジタル回路設計歴30年,プログラミング歴27年。

きもと特急電子設計
URL:http://business.pa-i.org/

コメント

コメントの記入