ホーム » スタッフ » 斉藤徹

斉藤徹」カテゴリーアーカイブ

2018年4月
« 3月    
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

実数の注意点

C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか?解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか?

まずは動く例

以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。

// sin の値を出力
#include <stdio.h>
#include <math.h>

int main() {
    double th , y ;
    for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) {
        y = sin( th / 180.0 * 3.1415926535 ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}

動かないプログラム

では、以下のプログラムはどうだろうか?

// case-1 ---- プログラムが止まらない
#define PI 3.1415926535
int main() {
    double th , y ;
    // 0〜πまで100分割でsinを求める
    for( th = 0.0 ; th != PI ; th += PI / 100.0 ) {
        y = sin( th ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}
// case-2 ---- y の値が全てゼロ
int main() {
    int    th ;
    double y ;
    for( th = 0 ; th <= 360 ; th += 5 ) {
        y = sin( th / 180 * 3.1415926535 ) ;
        printf( "%d %lf¥n" , th , y ) ;
    }
    return 0 ;
}

どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。

では何が悪かったのか…
回答編

数値の範囲に注意

前節の回答編で示したが、数値の扱える値の範囲に注意すべきである。
私自身が自分で書いたプログラムで悩んだ例を以下に示す。

// 16bit コンピュータの時代に、
//   画面上のマウスとターゲットの距離を計算したかった
int distance( int x0 , int y0 , int x1 , int y1 ) {
    int dx = x1 - x0 ;
    int dy = y1 - y0 ;
    return sqrt( dx * dx + dy * dy ) ;
}

このプログラムを実行した時、通常はうまく動くのだけど、時々「sqrt は、負の値では計算できません」というエラーを表示する。

なぜだろうか?
回答編

2進数への変換(補助資料)

10進数で 123.45 は、1*102 + 2*101 + 3*100 + 4*10-1 + 5*10-2 を意味する。(あたりまえ)

2進数に変換する場合、整数部と小数部に分けて考えると、

10進数なら、それぞれを 10 で割る、10 をかけると
  123 / 10 = 12.3 小数部に3 が出てくる。
  0.45 * 10 = 4.5 整数部に4 が出てくる。

2進数なら、それぞれを 2 で割る、2をかけると...
123.45 を 2進数に変換

 2)123 )10 = 1111011 )2
    ̄ ̄ ̄ ̄
 2) 61 ... 1    次々と2で割って、余りを求める
    ̄ ̄ ̄ ̄
 2) 30 ... 1
    ̄ ̄ ̄ ̄
 2) 15 ... 0
    ̄ ̄ ̄ ̄
 2)  7 ... 1
    ̄ ̄ ̄ ̄
 2)  3 ... 1
    ̄ ̄ ̄ ̄
 2)  1 ... 1
    ̄ ̄ ̄ ̄
     0 ... 1

✕2)0.45 )10 = 0.01110011001100...)2
    ̄ ̄ ̄ ̄ ̄
✕2)0.9 ... 0    次々と2倍して、整数部を求める
    ̄ ̄ ̄ ̄ ̄
✕2)1.8  ... 1 ※
    ̄ ̄ ̄ ̄ ̄
✕2)1.6 ... 1
    ̄ ̄ ̄ ̄ ̄
✕2)1.2 ... 1
    ̄ ̄ ̄ ̄ ̄
✕2)0.4 ... 0
    ̄ ̄ ̄ ̄ ̄
✕2)0.8 ... 0 ※の繰り返し
    ̄ ̄ ̄ ̄ ̄
✕2)1.6 ... 1
    ̄ ̄ ̄ ̄ ̄
   :
よって、123.45 )10 = 1111011 .011100110011...)2

大域変数・局所変数・スコープ

繰り返しが動かない例

#include <stdio.h>
int i ;
void foo() { // foo() は 3個Aを表示するプログラム。
   for( i = 0 ; i < 3 ; i++ )
      printf( "A" ) ;
}
int main() {
   foo() ;
   return 0 ;
}

では、

#include <stdio.h>
int i ;
void foo() { // foo() は 3個Aを表示するプログラム。
   for( i = 0 ; i < 3 ; i++ )
      printf( "A" ) ;
}
int main() {
   // A はいくつ表示される?
   for( i = 0 ; i < 3 ; i++ )
      foo() ;
   return 0 ;
}

大域変数と局所変数

編集中:もう少し加筆予定

引数渡しと構造体からオブジェクト指向へ

値渡し、ポインタ渡し、参照渡し

構造体の使い方の話では、関数との構造体のデータ渡しでポインタなどが出てくるので、 値渡し・ポインタ渡し・参照渡しの復習。(参照渡しはC++で導入された考え方)

値渡し

C言語の基本は、値渡し。呼び出し側の実引数は、関数側の仮引数に値がコピーされる。 このため、呼び出し側の変数(下の例ではa)の中身は変化しない。 よって、関数の呼び出しで呼び出し側の変数が勝手に中身が変わらないので、予想外の変数の中身の変化が無く分かりやすい。

// 値渡し(call by value)の例
void foo( int x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124が表示
   foo( a ) ;  // 124が表示
}

ポインタ渡し

しかし、上の例では、foo()の呼び出しで、変数aの中身が変化してくれたほうが都合が良い場合もある。 この場合は、C言語ではポインタを使って記述する。 このように、関数を呼び出して、手元の変数が変化することは、副作用と呼ばれる。 副作用の多いプログラムは、変数の値の管理がわかりにくくなるので、副作用は最小限に記述すべき。

// ポインタ渡し(call by pointer)の例
void foo( int *px ) {
   (*px)++ ;
   printf( "%d¥n" , (*px) ) ;
}
void main() {
   int a = 123 ;
   foo( &a ) ;  // 124が表示
   foo( &a ) ;  // 125が表示
}

参照渡し

しかし、ポインタを多用すると、ポインタを動かしてトラブルも増えることから、ポインタはあまり使わない方が良い。 そこで、C++では参照型というものがでてきた。

// 参照型(call by reference)の場合
void foo( int &x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124が表示
   foo( a ) ;  // 125が表示
}

参照型は、ポインタを使っていないように見えるけれども、機械語レベルでみればポインタを使ったものと同じ。

構造体でオブジェクト指向もどき

例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者データ利用者で分けて 仕事ができることを説明。

// この部分はデータ構造の設計者が書く
// データ構造を記述
struct Person {
   char name[10] ;
   int  phone ;
} ;
// データに対する処理を記述
void readPerson( struct Person* p ) {
   // ポインタの参照で表記
   scanf( "%s%d" ,
          (*p).name , &(*p).phone ) ;
}
void printPerson( struct Person* p ) {
   // アロー演算子で表記
   printf( "%s %d¥n" ,
           p->name , p->phone ) ;
}
// この部分は、データ利用者が書く
int main() {
   // Personの中身を知らなくてもいいから配列を定義(データ隠蔽)
   struct Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      // 入力して、出力する...という雰囲気で書ける(手続き隠蔽)
      readPerson( &table[i] ) ;
      printPerson( &table[i] ) ;
   }
   return 0 ;
}

このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。

C++のクラスで表現

上記のプログラムをそのままC++に書き直すと以下のようになる。

// この部分はクラス設計者が書く
class Person {
private: // クラス外からアクセスできない部分
   // データ構造を記述
   char name[10] ; // メンバーの宣言
   int  phone ;
public: // クラス外から使える部分
   // データに対する処理を記述
   void read() { // メソッドの宣言
      // pのように対象のオブジェクトを明記する必要はない。
      scanf( "%s%d" , name , &phone ) ;
   }
   void print() {
      printf( "%s %d¥n" , name , phone ) ;
   }
} ; // ← 注意ここのセミコロンを書き忘れないこと。

// この部分はクラス利用者が書く
int main() {
   Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      table[i].read() ;   // メソッドの呼び出し
      table[i].print() ;  // オブジェクト.メソッド()
   }
   // 文法エラーの例
   printf( "%d¥n" , table[0].phone ) ;
   // phoneはprivateなので参照できない。
   return 0 ;
}

用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。

制御構文について

プログラムの基本は、処理の順序を正しく理解していること。

まずは理解度確認

では、過去の電子情報3年プログラム応用のテスト問題から、以下のプログラムの実行順序を答えて下さい。

制御構文とフローチャート

構文の入れ子

繰り返し処理とオーダ記法

先週に、単純繰り返し処理の時間分析をやったので、次のステップに。

2分探索法の処理時間

データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。

// 2分探索法 O(log N)
int a[ 1000 ] ;
int size ;      // データ数 N
int L = 0 ;     // L=下限のデータの場所
int R = size ;  // R=上限のデータ+1の場所
while( L != R ) {
   int M = (L + R) / 2 ;  // 計算は整数型で行われることに注意
   if ( a[M] == key )     // 見つかった
      break ;
   else if ( a[M] < key ) // |L         |M.         |R
      L = M + 1 ;         // |----------|-+---------|
   else                   // |L---------|M|
      R = M ;             //              |M+1------|R
}

上記のようなプログラムの場合、処理に要する時T(N)は、

 # Mは繰り返し回数

処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、

となることから、 の関係が成り立つ。よって、は、以下のように表せる。

単純なソート(最大選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

int a[ 1000 ] ;
int size ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は…

となる。

オーダー記法

ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、赤字の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
2分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ オーダーNのアルゴリズム
2分探索法 オーダー log N のアルゴリズム
最大選択法 オーダー N2 のアルゴリズム

練習問題

  1. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
    データ10000件なら何[sec]かかるか?
  2. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
  3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?

緊急連絡システムとメール分析システム

私が管理している丹南地区緊急連絡システムで、利用者の方から『「受信確認」作業をしているのに、記録されていない…』との相談を受ける。

メール分析システム

上記の現象は、昨年度に行った迷惑メールの分析システム対策が原因であった。

緊急連絡システムでは、ユーザに送った文面の末尾に URL を添付し、その URL をユーザにアクセスしてもらうことで、受信確認を行っている。

一方、連絡システムで、ユーザがメールアドレスを変更したり、ユーザ登録にミスがあると、相手に届かないメールが発生する。最近のメールシステムでは、プロバイダが迷惑メールの分析をすることがあり、この分析処理の中でメール内のURLを、分析システムがアクセスしていると思われる。

コレ以外にも、チャット表示形式のメールアプリでは、届いたメールの概要を確認するために、文中のURLをアクセスするものもある。このような処理が行われると、ユーザがメールを読んでいないのに、受信確認の URL をアクセスされ、受信確認が済んだことになってしまう。

最初、この現象を把握し状況を確認したら、このような分析システムの多くは逆引きできないIPアドレスからアクセスしていることが判明した。そこで、逆引きできないIPアドレスからの受信確認は、アクセス履歴を保存しないように改良を行っていた。

さらなる対策

しかし、今回相談を受け確認を行った所、逆引きできないIPアドレスの中に、通常のユーザからのアクセスも含まれていることが分かった。

そこで、今回以下のような改良を行った。

逆引きできないアドレスからのアクセスの場合には、以下のような送信フォームを表示し、ユーザが「確認」ボタンを押すことで受信確認の記録を行うようにした。

この方法は、ユーザが受信確認のために2回ボタンを押す必要があるが、止む終えないかな。

macOSのOneDriveでキーチェーンのパスワード

OneDrive アプリの更新がかかったら、「キーチェーンが一致しない」というエラーで OneDrive が起動しなくなった。

対応法法を調べると、キーチェーンのリセットとか書いてあるので色々と調べたけど、いい方法がない。グダグダ考えてもアプリの一時的な問題かと思い、macOS を再起動かけたら、普通に起動してくれた。

はぁ…

オブジェクト指向(2018) / ガイダンス

専攻科2年のオブジェクト指向プログラミングの授業の1回目。最初に授業全般の概要を説明した後、オブジェクト指向の歴史とC言語の構造体の説明。

オブジェクト指向プログラミングの歴史

最初のプログラム言語のFortran(科学技術計算向け)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct …}の考えができた。 その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができて、処理の構造化・データの構造化ができる。これが「構造化プログラミング(structured programming)」 の始まりとなる。
この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向の始まりとなる。

この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから普及が拡大する。

C言語にこのオブジェクト指向を取り入れて、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発される。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。

構造体の導入

C++でのオブジェクト指向は、構造体の表記がベースになっているので、まずは構造体の説明。

// 構造体の宣言
struct Person {      // Personが構造体につけた名前
   char name[ 20 ] ; // 要素1
   int  phone ;      // 要素2
} ;                  // 構造体定義とデータ構造宣言を
                     // 別に書く時は「;」の書き忘れに注意
// 構造体変数の宣言
struct Person saitoh ;
struct Person data[ 10 ] ;
// 実際にデータを参照 構造体変数.要素名
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.phone = 272925 ;
for( int i = 0 ; i < 10 ; i++ ) {
   scanf( "%d%s" , data[ i ].name , &(data[ i ].phone) ) ;
}

情報構造論ガイダンス

情報構造論のガイダンス

プログラム作成でのポイント

この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。

  • プログラムの速度
  • プログラムのわかり易さ
  • メモリの使用量

プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

プログラム例

例えば、配列の中から、目的データを探すプログラムの場合、最もスタンダードなプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。

// ((case-2))
// 2分探索法 O(log N)
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

でももっと速いプログラムとしたければ、

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば
int a[ 1000000 ] ;
a[ key ] に保存
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られる予算から、メモリやCPUが決まり、その会社の人員やら経験やらで、プログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

動作時間の予測

ここで、プログラムの実行時間を細かく分析してみる。例えば、前節のcase-1単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その1つ1つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか?

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか? 上記のT(N)=Tα+N ✕ Tβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。

猫バカ

新入生歓迎会の教員紹介で、猫バカ認定を頂いたので、昨日の写真を上げとこう。

うわぁ、黒猫ちゃん、極悪そうに写ってるな。