著者アーカイブ 杉浦

著者:杉浦

コード中のif節を減らす

これの記事はシンプルなif節を減らすことについての記事です。
例えば、次のようなプログラムがあるとします。条件ABCの真偽に応じて01を返すプログラムです。

if A
    if B
        if C
            return 1;
        else
            return 0;
        end
    else
        if C
            return 0;
        else
            return 1;
        end
    end
else
    if B
        if C
            return 1;
        else
            return 0;
        end
    else
        if C
            return 1;
        else
            return 0;
        end
    end
end

このプログラムは一見読みにくく、また余分な動作があります。if節を減らすことで速度と可読性の向上が見込めます。単純な真偽を表に表します。ABCが条件、Rが返り値です。1は値の1の他に真の意味も持ちます。0は値の0の他に偽の意味も持ちます。

例えば~AB~C=1、AB~C=1です。~は否定の意味です。ここからB~C=1と短縮でき、以下の様にプログラムを変えることができます。

if B
    if C
        if A
            return 0;
        else
            return 0;
        end
    else
        return 1;
    end
else
    if C
        if A
            return 1;
        else
            return 0;
        end
    else
        if A
            return 1;
        else
            return 0;
        end
    end
end

判定が減った分、文量も処理量も減りました。
そんなこんなで真偽を最適化した場合、次のような式ができます。
1 = ~A~BC + B~C + A~C
この式に従った場合、以下の様にプログラムを変えることができます。

if C
    if ~A
        if ~B
            return 1;
        end
    end
else
    if A
        return 1;
    end
    if B
        return 1;
    end
end
return 0;

最初の書き方が愚直すぎるのもありますが随分と簡略化できました。
真理値の短縮には多くのアプリ、ライブラリもあるのでコードを簡略化したい際にはググって使うのが良いと思います。

著者:杉浦

ハッシュ探索

　人間が本棚から特定本を探す時、どのような行動をとるでしょうか。
　慣れ親しんだ自宅の本棚ならここに入れてある、と一瞬で目当ての本の場所がわかると思います。図書館の様な場所なら辞書内を探す様にタイトルを追って大体の場所を行ったり来たりして探していくと思います。前者と後者の違いは題名と保管場所に密接な関係があるかないかの違いです。前者ならば題名を思い出した時に保管場所も共に思い出しているでしょう。後者ならば題名からこのあたりにあるだろうと推測を付けているでしょう。データ名がコンピュータがデータを保存している場所を示した場合、コンピュータも自宅の本棚から本を見つける様に一瞬で目当てのデータを探せるでしょう。ハッシュ探索は大体そのような方法です。
　コンピュータのデータ格納場所は番地、値で表せます。データ名もまた、値で表せます。データの格納番地をデータ名とした場合、データ名の場所にアクセスしにいけばそれで一発でデータを読み出せます。大体このような考えがハッシュ探索です。実際には、格納場所はもっと狭く、格納番地を読み出すためのコストもバカにならないので、データそのままでなく何らかの別のものをキー（格納番地）として扱います。それでも多くの場合で他のデータ構造より高速に特定のデータを読み出せます。
　多くの言語にはマップというデータ構造が備えられておりハッシュ探索に対応しています。先ほどのデータ名や格納番地足るキーと共にデータ値を登録していくデータ構造です。
追記：人間の頭が一瞬で目当てのデータを見つけられる主な仕組みはハッシュ探索の仕組みというより、頻繁に使われるデータや最近使用されたデータを上位（記憶の上層）に保管している仕組みです。

著者:杉浦

浮動小数点数

　浮動小数点数は01のみで少数のような細かい数からn^mの様な巨大な数までを表現する方法です。浮動小数点は図の様に、仮数部^(符号ビット*指数部)で表されます。赤が仮数部、青が符号ビット、緑が指数部です。図はIEEE 754 形式の単精度でPC上でよく使われています。

　それなりの精度の仮数部と仮数部を拡縮する符号ビットと指数部によって広い範囲の値を表現できます。また、仮数部をhoge乗するという点からわかるように一定の相対誤差を保ちます（相対誤差：x%の誤差というように表せる誤差。大きな数ほど誤差が大きく、小さな数ほど誤差が小さい。）。この誤差は値の表現を省略する誤差であり、丸め誤差と呼ばれます。常に誤差があるというのが特徴で、丸め誤差が積み重なるような計算（値を表現してから加算することを繰り返すなど）をするプログラムを書くと大きな誤差が生まれて惨事になりやすいです。