サイゼントの技術ブログ – Just another WordPress site

2019年8月17日

O(オーダ)の概念と実務での使い道

今回の記事は、検索アルゴリズムやソートアルゴリズムの性能を評価する際に用いられる「O(オーダ)」の概念についてです。

「O」は情報処理技術者試験ではよく主題されるものの、業務系SE（特定の業務のシステム設計を得意とするSE）には無縁のものに思われがちです。
しかし、業務系SEでも「システム改修によりデータ量が○倍になるが、このバッチ処理は○分以内に終わらせないといけない」という形で性能面を考えた設計が必要になることがあります。
実際に本番と同じ環境・改修後のデータ量を用意してテストができれば良いのですが、それができない場合は本番環境の現状のデータ量・処理時間から改修後の処理時間を見積もる必要があります。
（この見積もりで求められる性能が出ない場合は、性能を向上させるための設計を考える必要が出てきます）
このような見積もりで、「O」という概念が必要になります。

下記に、代表的なアルゴリズムとそのオーダを記載します。

・線形検索

O(N)

・２分検索

O(logN)

・バブルソート、基本選択法、基本挿入法

O(N^2)

・クイックソート、マージソート、ヒープソート

O(NlogN)

ここで、Nはデータ量のことを指し、Oは処理時間のことを指します。
例えば、「O(N^3)」なら、処理時間はデータ量の増加の割合の３乗となります。
データ量が２倍になれば、処理時間は８倍(2^3)となります。

また、情報処理の分野では、logの底は2とされています。
そのため、「logN」とは、「2を何乗したらNになるのか」を指す値となります。
log2は1(2^1=2)、log4なら2(2^2=4)、log1024なら10(2^10=1024)となります。
例えば、２分検索の場合、階層が1深くなれば(処理回数が1回増えれば)２倍のデータを検索できるようになるので、「2^処理回数=データ量」の関係が成り立ち、O(logN)と表記できます。

例として、データ量が４倍になった時の処理時間の増加量を以下に示します。

・線形検索

4倍(N)

・２分検索

2倍(logN)

・バブルソート、基本選択法、基本挿入法

16倍(N^2)

・クイックソート、マージソート、ヒープソート

8倍(NlogN)

なお、実務で処理時間を見積もる際、OSや製品で用意されている検索・ソートアルゴリズムは原則として高速なものが用意されているので、２分検索やクイックソート・マージソート・ヒープソートと同じオーダで計算して良いでしょう。

いかがでしたでしょうか。

情報処理技術者試験で学んだ知識が本当に実務で役に立ったのが個人的に印象的だったので、記事として書きました。
これ以外にも実務で役に立つ知識は少なくないので、単に合格するために試験勉強するのではなく、実務で使える引き出しを増やすために勉強した方が良いと個人的には思っています。

これからも実務で使える/使えたことがあれば、記事として発信していきたいと思います！

2019年8月10日

プログラムによる小数点以下の計算で誤差が生じる原因と対処法２選

プログラムで小数点以下の計算を行う際、誤差が生じることがあります。
金額計算を行う時はこの誤差が即障害に繋がるので、誤差が生じないように実装する必要があります。

今回の記事では、誤差が生じる原因とその対処法を２つ挙げていきたいと思います。

１．浮動小数点型の丸め誤差

丸め誤差とは、小数点以下の数を２進数で表現できない（近似値を使わざるを得ない）ことにより発生する誤差です。
浮動小数点型（javaで言うとfloat型やdouble型）の変数を使用する際に、この問題が発生することがあります。
浮動小数点型を使用すると、例えば「0.3」が「0.29999999…」になったりするので、小数点以下の誤差が許されない場合には浮動小数点型を使用するべきではありません。

最も簡単な対処法は、整数型（javaで言うとint型等）で計算できるように、ファイルやテーブルの数値項目の単位を変えるという対処法です。
例えば、「金額項目は0.01円単位とする」という設計とすれば、「1.01円」を「101」と表すことが可能となり、整数型で計算できるようになります。

また、プログラム言語が任意精度型（javaで言うとBigDecimal型）の変数を用意している場合は、その型を使用することで丸め誤差の発生を防ぐことができます。
なお、COBOLの場合は丸め誤差が発生しないので、COBOLで小数点以下の項目を定義する場合は任意精度型であると考えて良いです。

２．中間結果を格納する領域の桁数不足による切り捨て発生

複数の四則演算を行って最終的な結果を得る際、中間結果を格納するための領域が必要になります。
もちろん、その領域が自分で定義した整数型の変数だったりすると、その時点で切り捨てが発生し、誤差が発生してしまいます。

このようなケースはレビューをすれば一目瞭然なのであまり心配はいらないのですが、問題なのはその中間結果がコンパイラにより暗黙的に用意される場合です。
具体的に言えば、COBOLでCOMPUTE文を使うような場合に問題になります。
基本的には、乗算を除算よりも先に行う、というのが誤差を防ぐための方法になりますが、中間結果の桁数の仕様を把握した上でそのような対処法を採用するのが望ましいです。
中間結果の桁数はコンパイラを用意しているベンダー毎で異なるので、詳しくはベンダーが用意しているマニュアル等で調べる必要があります。

例えば、COMPUTE文の中間領域が小数点以下0桁（コンパイラが暗黙的に設定）、最終結果を格納する領域が小数点以下0桁（プログラマが明示的に定義）である場合、以下のような計算結果になります。

・正しい計算

　　123456円の消費税8%
　→123456円 * 1.08
　→133332.48円
　→133332円
　　（小数点以下切り捨て）

・COMPUTE文で問題のある計算順

　　123456 / 100 * 108
　→1234 * 108
　　（下２桁が意図せず失われる）
　→133272

・COMPUTE文で問題のない計算順

　　123456 * 108 / 100
　→13333248 / 100
　→133332
　　（下２ケタを切り捨てる）

金額計算を行う場合、誤差が生じると重大な障害を生み出しかねません。
小数点以下の計算は特に誤差が生じやすく、上記で述べたことも実際のシステム開発で障害になりやすいポイントです。
多くの場合は、開発者のプログラミングの知識不足により小数点以下の計算の誤差が発生するので、そのような障害を少しでも減らしたいという思いで今回の記事を書きました。

これからも、開発者の役に立てるような記事を書いていきたいと思います！

2019年8月3日

gitとsubversionの違い

gitとsubversionの違いについて良く聞かれるので、記事にしてみました。

【git・subversionとは？】

gitもsubversionも共にバージョン管理システムであり、古典的なバージョン管理システムであるCVSからの流れを汲んでいます。
バージョン管理システムとは、ソースコード等のファイルを管理するシステムであり、過去のバージョンを保持することができるため、障害や要望が発生した時にある時点のバージョンまで遡ることが容易になります。
（バージョン管理システムを使っていれば過去のバージョンを指定して落としてくるだけで良いですが、使っていないと手動で過去バージョンのファイルをかき集めたり復元したりという作業が発生します）
gitの方が後発ですが、現在はgitの方がメジャーです（少なくとも国際的には）。

【gitとsubversionの違い】

一言で言うと、subversionは集中型バージョン管理システム、gitは分散型バージョン管理システムという違いがあります。
集中型と分散型の違いについては、下記図に表しました。

集中型管理システムでは、リポジトリ（ファイルのバージョン管理を行う書庫）はリモート環境にのみ存在します。
メンバーはリモート環境のリポジトリにアクセスし、各メンバーのローカル環境にあるファイルをコミット（新バージョンとしてファイルを保存）したり、ローカル環境へチェックアウト（特定のバージョンのファイルを取得）したりします。

一方、分散型管理システムでは、リポジトリはリモート環境のみでなく、各メンバーのローカル環境にも存在します。
メンバーは自分のローカル環境のリポジトリに対し、コミットやチェックアウトを行います。
ローカル環境でコミットしたファイルについては、適切なタイミング（テストが完了したタイミング、リリース準備を行うタイミング等）でプッシュを行い、リモート環境のリポジトリへコミットを反映させます。
また、ローカル環境のリポジトリを作る際は、リモート環境のリポジトリから特定のバージョンの情報をプルで取得します。

【分散型管理システムの利点】

利点はいくつか挙げられますが、一番本質的な利点は自分のコミットが他のメンバーへ影響を与えずに済むという点です。
集中型管理システムの場合は、コミットしたファイルは即座に他のメンバーも取得可能となるため、仮にバグを取り除き切れていないソースコード等をコミットしてしまうと他のメンバーに迷惑をかけてしまいます。
しかし、分散型管理システムであれば、自分のリポジトリでチェックしてからリモート環境のリポジトリへ反映させることができるので、他のメンバーへ迷惑をかけずに作業を進めることができ、生産性が向上します。

他には、「分散型管理システムであればローカル環境のリポジトリがバックアップとなるため障害耐性が向上する」等の利点を挙げる文献もありますが、個人的には本質的な利点だと思っていません。
（例えばバックアップの例なら、集中型管理システムでも定期的にバックアップを取得する運用体制とすれば障害耐性を向上させられます）

【gitにおけるブランチの使い方】

gitではブランチを使用することができ、コミットを複数に枝分かれさせることができますが、自分のコミットが他のメンバーへ影響を与えないという利点は、ブランチ機能と親和性があります。
gitの場合は、「機能毎に担当者を決める→各々の担当者がブランチを切る→自分が開発した機能を自分のリポジトリへコミットする→自分の環境で機能の検証を行う→検証済みのコミットをリモート環境のリポジトリへプッシュし、枝分かれしたコミットをマージする」という開発体制を取ることができます。

このように、担当者毎・機能毎でブランチを切ることができるため、機能毎にプッシュ可否を判定する、ある機能だけバージョンを戻す、といった柔軟な運用が可能になります。

なお、subversionにもブランチの機能はあるのですが、各担当者が思い思いにブランチを切るという使い方はできないので、バージョン毎（マスターバージョンとβバージョン等）に複数機能をまとめてブランチを切る、という使い方になります。

システム開発の仕事をする上では、単にプログラムを作れるだけでなく、開発環境についても理解する必要があります。
プログラミング研修を終えていきなりバージョン管理システムに触れると色々疑問に思うことが出てくると思いますので、今回の記事が助けになれば幸いです。

これからも、開発者のためになる記事を書いていきたいと思います！

2019年7月27日

java：ミュータブルな参照型変数の初期化の注意点

ミュータブルな参照型変数を初期化する場合、初期化の方法を間違えると他の変数も一緒に初期化してしまいます。
この記事では、ミュータブルな参照型変数の初期化方法を説明します。

【基本データ型変数と参照型変数】

変数は大きく分けて、基本データ型変数（プリミティブ型変数、値型変数）と参照型変数（オブジェクト型変数、クラス型変数）の２つに分けることができます。

基本データ型変数とは、以下の８つの内の何れかの型で定義された変数であり、オブジェクトを持ちません。
・byte
・short
・int
・long
・float
・double
・boolean
・char

参照型変数は以上の８つの型以外の型で定義された変数であり、オブジェクトを持ちます。
実際には、メモリ領域の番地を指し示すポインタのようなものが格納され、ポインタを辿って値を参照します。
C言語のポインタの概念を理解しているとこの概念も理解できます。C言語のポインタについては以下のページをご参照ください。

C言語：ポインタの概念の図解

【イミュータブルとミュータブル】

参照型変数は、更にイミュータブルとミュータブルの２つに大別することができます。

イミュータブルは、日本語で言うと「不変」という意味であり、オブジェクトの中の値を変更することができない変数を指します。
setter等でオブジェクトの中の値を変更できないようにする、メンバ変数をprivateで定義してオブジェクトの中の値を変更できないようにする、等の条件を満たすと、イミュータブルな型となります。
イミュータブルな型となる条件はかなり例外的であり、自分でクラスを作成する場合は意識的に条件を満たそうとしなければイミュータブルな型にはならないはずです。
標準で用意されている型の中では、String型がイミュータブルな型として有名です。
イミュータブルな参照型変数はオブジェクトの中の値を変更できないため、中の値を変更する場合は新たにメモリ領域を確保してオブジェクトを作り直すような動きになります。今回取り上げる記事上は、基本データ型変数と同じような動きになります。

ミュータブルはその逆で、オブジェクトの中の値を変更することができる変数のことであり、多くの参照型変数はこちらに該当します。
String型も、配列にした場合はミュータブルな型になります（配列がミュータブルなので）。
そして、注意が必要なのはこのミュータブルな参照型変数です。

【ミュータブルな参照型変数の初期化の注意】

参照型変数の中には、ポインタが格納されています。

例えば、

String[] hoge = {"あ","い","う"};
String[] fuga = hoge;

1 2	String[] hoge = {"あ","い","う"}; String[] fuga = hoge;

とした場合、fugaには「{“あ”,”い”,”う”}」が入るわけではなく、fugaのアドレスが格納されます。
つまり、hogeとfugaは同じ位置を指し示すことになります。

ここで、fugaのみ初期化（値を変更）しようとしたとします。
String型のようにイミュータブルな型であれば、fugaの値を変更された時点でメモリ領域が新たに確保されるので、hogeとfugaは別々の値となり、何の問題もありません。
しかし、String[]型のようにミュータブルな型の場合は、hogeとfugaが同じ位置を示しており、新たにメモリ領域が確保されることもないので、hogeが示す値も一緒に書き変わってしまいます。

例えば、

String[] hoge = {"あ","い","う"};
String[] fuga = hoge;
for (int i=0;i&lt;3,i++){
    fuga = "　";
}

String[] hoge = {"あ","い","う"};

String[] fuga = hoge;

for (int i=0;i<3,i++){

fuga = "　";

}

のようにfugaを全角スペースで初期化しようとすると、fugaだけでなくhogeも初期化されてしまいます。

これを防ぐためには、以下の２つの手順を踏む必要があります。
１．初期化したい変数にnullを代入してメモリ領域への参照を切る
２．newで初期化したい変数用のメモリ領域を新たに確保する

以下、サンプルコードで動きをまとめたいと思います。

【サンプルコード】

public class InitTestMain {

    public static void main(String[] args) {

        System.out.println("■プリミティブ型");
        int a = 1;
        int b = a;
        b = 2;
        System.out.println(a);
        System.out.println(b);

        System.out.println("■参照型（イミュータブル）");
        String c = "あ";
        String d = c;
        d = "い";
        System.out.println(c);
        System.out.println(d);

        System.out.println("■参照型（ミュータブル）");
        String[] e = {"か"};
        String[] f = e;
        f[0] = "き";
        System.out.println(e[0]);
        System.out.println(f[0]);

        System.out.println("■参照型（ミュータブル）…初期化実施");
        String[] g = {"さ"};
        String[] h = g;
        h = null;
        h = new String[1];
        h[0] = "し";
        System.out.println(g[0]);
        System.out.println(h[0]);
    }

}

public class InitTestMain {

public static void main(String[] args) {

System.out.println("■プリミティブ型");

int a = 1;

int b = a;

b = 2;

System.out.println(a);

System.out.println(b);

System.out.println("■参照型（イミュータブル）");

String c = "あ";

String d = c;

d = "い";

System.out.println(c);

System.out.println(d);

System.out.println("■参照型（ミュータブル）");

String[] e = {"か"};

String[] f = e;

f[0] = "き";

System.out.println(e[0]);

System.out.println(f[0]);

System.out.println("■参照型（ミュータブル）…初期化実施");

String[] g = {"さ"};

String[] h = g;

h = null;

h = new String[1];

h[0] = "し";

System.out.println(g[0]);

System.out.println(h[0]);

}

【実行結果】

■プリミティブ型
1
2
■参照型（イミュータブル）
あ
い
■参照型（ミュータブル）
き
き
■参照型（ミュータブル）…初期化実施
さ
し

■プリミティブ型

■参照型（イミュータブル）

あ

い

■参照型（ミュータブル）

き

■参照型（ミュータブル）…初期化実施

さ

し

「参照型」や「イミュータブル」といった概念は、プログラム経験の浅い人には難しいと思います
私の場合はC言語でポインタの概念を理解してからこれらの概念を学んだのですが、それでも初めの内はjava独特の仕様に戸惑いました。
しかし、概念を理解すればコーディングする上で便利だと感じることもあるので、この記事を通して理解を深めていただければ幸いです。

今後も、つまずきやすいポイントを記事にしていきたいと思います！

2019年7月13日2019年7月21日

java：Unicodeの絵文字をjavaで取り扱う

メールや掲示板等の文章を見ていると時々「🗿」のような絵文字が出てきますが、これはUnicodeにより定義されています。
このような絵文字を取り扱うには少々知識が必要なので、この記事を通して必要な知識をお伝えしたいと思います。
また、絵文字を含む文字列を１文字ずつ切り出すjavaのサンプルコードも作りました。

【絵文字の定義と背景】

絵文字は符号化文字集合「Unicode」で定義されており、Unicodeの文字符号化方式である「UTF-8」「UTF-16」等で使用することができる。
（「符号化文字集合」とは「文字」と「文字に割り当てた番号」の対応表、「文字符号化方式」とは「文字に割り当てた番号」と「実際にコンピュータが扱う数字」の対応表のことである）
なお、「UTF-16」は狭義の「Unicode」として呼ばれることもある。

Unicodeは元々1～2バイト文字を定義していたが、世界中の文字を取り扱いたいという要望に応えるために4バイト文字を拡張領域として定義した。
絵文字は、この拡張領域に含まれる。
4バイト文字は、「上位サロゲート(2バイト)＋下位サロゲート(2文字)」の組み合わせで定義される。
「上位サロゲート」は0xD800～0xDBFF（1024通り）、「下位サロゲート」は0xDC00～0xDFFF（1024通り）で定義され、何れも2バイト文字では使用しないコードであるため、表現が衝突することはない。

4バイト文字は定義当時は実際に扱われることが少なかったが、日本の携帯の絵文字の普及により一般的に使われるようになり、Webシステム等では無視できない存在となった。

【サンプルコード】

・ソースコード（UTF-8で作成）

public class Sample {
  public static void main(String args[]){
    // 変数で直接４バイト文字込みの文字列を定義し表示
    String str = "🚅Unicode🌏絵文字で遊んでみよう😮";
    System.out.println("変数から取得："+str);
    // 何も考えず１文字ごと文字と文字コードを出力
    // ４バイト文字は２文字扱い
    for (int i = 0; i &lt; str.length() ; i++) {
      int code = (int)str.charAt(i);
      String hex = Integer.toHexString(code);
      System.out.println
        ((i + 1) + "番目の文字：" +
         str.charAt(i) + " 16進数：" + hex);
    }
    // サロゲート文字で４バイト文字を判定
    // 正しく１文字ずつ切り出す
    String upperSurStart = "d800";
    String upperSurEnd = "dbff";
    int fourByteMojiCount = 0;
    for (int i = 0; i &lt; str.length() ; i++) {
      int mojiPos = i+1-fourByteMojiCount;
      int code = (int)str.charAt(i);
      String hex = Integer.toHexString(code);
      String strOneMoji = "";
      if (hex.compareTo(upperSurStart)>=0 &amp;&amp; 
          hex.compareTo(upperSurEnd)&lt;=0) {
        strOneMoji = str.substring(i,i+2);
        i++;
        fourByteMojiCount++;
      } else {
        strOneMoji = str.substring(i,i+1);
      }
      System.out.println(mojiPos + "番目の文字：" +
                         strOneMoji);
    }
  }
}

public class Sample {

public static void main(String args[]){

// 変数で直接４バイト文字込みの文字列を定義し表示

String str = "🚅Unicode🌏絵文字で遊んでみよう😮";

System.out.println("変数から取得："+str);

// 何も考えず１文字ごと文字と文字コードを出力

// ４バイト文字は２文字扱い

for (int i = 0; i < str.length() ; i++) {

int code = (int)str.charAt(i);

String hex = Integer.toHexString(code);

System.out.println

((i + 1) + "番目の文字：" +

str.charAt(i) + " 16進数：" + hex);

}

// サロゲート文字で４バイト文字を判定

// 正しく１文字ずつ切り出す

String upperSurStart = "d800";

String upperSurEnd = "dbff";

int fourByteMojiCount = 0;

for (int i = 0; i < str.length() ; i++) {

int mojiPos = i+1-fourByteMojiCount;

int code = (int)str.charAt(i);

String hex = Integer.toHexString(code);

String strOneMoji = "";

if (hex.compareTo(upperSurStart)>=0 &&

hex.compareTo(upperSurEnd)<=0) {

strOneMoji = str.substring(i,i+2);

i++;

fourByteMojiCount++;

} else {

strOneMoji = str.substring(i,i+1);

}

System.out.println(mojiPos + "番目の文字：" +

strOneMoji);

}

・出力

変数から取得：🚅Unicode🌏絵文字で遊んでみよう😮
1番目の文字：? 16進数：d83d
2番目の文字：? 16進数：de85
3番目の文字：U 16進数：55
4番目の文字：n 16進数：6e
5番目の文字：i 16進数：69
6番目の文字：c 16進数：63
7番目の文字：o 16進数：6f
8番目の文字：d 16進数：64
9番目の文字：e 16進数：65
10番目の文字：? 16進数：d83c
11番目の文字：? 16進数：df0f
12番目の文字：絵 16進数：7d75
13番目の文字：文 16進数：6587
14番目の文字：字 16進数：5b57
15番目の文字：で 16進数：3067
16番目の文字：遊 16進数：904a
17番目の文字：ん 16進数：3093
18番目の文字：で 16進数：3067
19番目の文字：み 16進数：307f
20番目の文字：よ 16進数：3088
21番目の文字：う 16進数：3046
22番目の文字：? 16進数：d83d
23番目の文字：? 16進数：de2e
1番目の文字：🚅
2番目の文字：U
3番目の文字：n
4番目の文字：i
5番目の文字：c
6番目の文字：o
7番目の文字：d
8番目の文字：e
9番目の文字：🌏
10番目の文字：絵
11番目の文字：文
12番目の文字：字
13番目の文字：で
14番目の文字：遊
15番目の文字：ん
16番目の文字：で
17番目の文字：み
18番目の文字：よ
19番目の文字：う
20番目の文字：😮

変数から取得：🚅Unicode🌏絵文字で遊んでみよう😮

1番目の文字：? 16進数：d83d

2番目の文字：? 16進数：de85

3番目の文字：U 16進数：55

4番目の文字：n 16進数：6e

5番目の文字：i 16進数：69

6番目の文字：c 16進数：63

7番目の文字：o 16進数：6f

8番目の文字：d 16進数：64

9番目の文字：e 16進数：65

10番目の文字：? 16進数：d83c

11番目の文字：? 16進数：df0f

12番目の文字：絵 16進数：7d75

13番目の文字：文 16進数：6587

14番目の文字：字 16進数：5b57

15番目の文字：で 16進数：3067

16番目の文字：遊 16進数：904a

17番目の文字：ん 16進数：3093

18番目の文字：で 16進数：3067

19番目の文字：み 16進数：307f

20番目の文字：よ 16進数：3088

21番目の文字：う 16進数：3046

22番目の文字：? 16進数：d83d

23番目の文字：? 16進数：de2e

1番目の文字：🚅

2番目の文字：U

3番目の文字：n

4番目の文字：i

5番目の文字：c

6番目の文字：o

7番目の文字：d

8番目の文字：e

9番目の文字：🌏

10番目の文字：絵

11番目の文字：文

12番目の文字：字

13番目の文字：で

14番目の文字：遊

15番目の文字：ん

16番目の文字：で

17番目の文字：み

18番目の文字：よ

19番目の文字：う

20番目の文字：😮

文字の16進数表現は奥深いです。
先日公開したゾーン10進数・パック10進数もそうですが、文字が16進数でどのように表現されているのかを意識しないとコーディングに支障をきたすこともあります。
新人の時は16進数をあまり意識しておらず、エラーが出てもその理由がわからなかったりして色々苦労しました…。

今後も、文字の16進数表現でお伝えできることがあれば、記事にしていきたいと思います！