ハノイの塔

ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

　… ③より
 … ①を代入
      … ①のの場合

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

これらのことから、ハノイの塔の処理時間は、で表せる。

再帰を用いた並び替え

データを並び替えるプログラムとして、繰り返し処理の分析では「選択法」について説明した。

選択法は、のアルゴリズムで、あまり速い並び替え手法ではない。

ここで、最も高速なアルゴリズムとしては、クイックソートが有名である。クイックソートプログラムは、処理時間のオーダはで表せる。

本当であれば、クイックソートのプログラムの処理時間の分析を説明したいけど、イメージがわかりにくいので、同じオーダ式であらわせるマージソートで説明を行う。
(マージソートのオーダは、クイックソートと同じだけど、計算途中のデータを一時的に覚える場所を確保する処理が必要で、その処理に手間がかかるため、効率はクイックソートに比べ遅くなる。)

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

• 
• 

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。

：

よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

再帰呼び出しの基本

次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

import java.util.*;

public class Main {
    // 階乗(末尾再帰)
    public static int fact( int x ) {
        if ( x <= 1 )
            return 1 ;
        else
            return x * fact( x - 1 ) ;
    }
    // ピラミッド体積(末尾再帰)
    public static int pyra( int x ) {
        if ( x <= 1 )
            return 1 ;
        else
            return x * x + pyra( x - 1 ) ;
    }
    // フィボナッチ数列 (非末尾再帰) 
    public static int fib( int x ) {
        if ( x <= 2 )
            return 1 ;
        else
            return fib( x - 1 ) + fib( x - 2 ) ;
    }
    public static void main(String[] args) throws Exception {
        System.out.println( "fib(5)=" + fib( 5 ) ) ;
        System.out.println( "pyra(5)=" + pyra( 5 ) ) ;
        System.out.println( "fib(5)=" + fib( 5 ) ) ;
    }
}

• 単純な再帰関数(Paiza.io)

階乗 fact(N) を求める処理は、以下の様に再帰が進む。

また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。

再帰呼び出しの処理時間

次に、この再帰処理の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=T_a で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=T_b=T(N-1)で表せる。

	}	再帰方程式

このような、式の定義自体を再帰を使って表した式は再帰方程式と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式  が得られる。

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b + (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

ここで、フィボナッチ数列のプログラムは、末尾再帰ではない。この fib( intx ) の処理時間を表す再帰方程式は、どのような式で表せるだろうか？

再帰を含む一般的なプログラム例

ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

import java.util.*;

public class Main {
    public static int[] array = {
        3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
    } ;
    public static int sum( int[] a , int L , int R ) {
        if ( R - L == 1 ) {
            return a[ L ] ;
        } else {
            int M = (L + R) / 2 ;
            return sum( a , L , M ) + sum( a , M , R ) ;
        }
    }
    public static void main(String[] args) throws Exception {
        System.out.println( "sum()=" + sum( array , 0 , array.length ) ) ;
    }
}

• 再帰による配列の合計(分割統治法?)(Paiza.io)

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

   ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

ということで、このプログラムの処理時間は、 で表せる。

---

ハノイの塔

ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

　… ③より
 … ①を代入
      … ①のの場合

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

これらのことから、ハノイの塔の処理時間は、で表せる。

単純サーチの処理時間

ここで、プログラムの実行時間を細かく分析してみる。

// ((case-1))
// 単純サーチ O(N)
#include <stdio.h>

int main() {
    int a[ 10 ] = {
        12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
    } ;
    int N = 10 ;  // 実際のデータ数(Nとする)
    int key = 21 ;   // 探すデータ
    for( int i = 0 ; i < N ; i++ )
        if ( a[i] == key )
            break ;
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        int a[] = {
            12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
        } ;
        int N = a.length ;
        int key = 21 ;
        for( int i = 0 ; i < N ; i++ )
            if( a[i] == key )
                break ;
    }
}

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

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

ここで例題

この単純サーチのプログラムを動かしてみたら、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μ秒 となる。

2分探索法と処理時間

次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。データはあらかじめ昇順に並べておくことで、一度の比較で対象件数を減らすことで高速に探すことができる。

下記プログラムを読む場合の注意点：

• Lは、探索範囲の一番左端のデータのある場所。
• Rは、探索範囲の一番右端のデータのある場所 + 1

// ((case-2))
// 2分探索法 O(log N)
#include <stdio.h>

int main() {
    int a[] = {
        9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
    } ;
    int L =  0 ; // L : 左端のデータの場所
    int R = 10 ; // R : 右端のデータの場所+1 
    while( L != R ) {
        int M = (L + R) / 2 ;
        if ( a[M] == key )
            break ;
        else if ( a[M] < key )
            L = M + 1 ;
        else
            R = M ;
    }
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int a[] = {
            9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
        } ;
        int L = 0 ;        // L : 左端のデータの場所
        int R = a.length ; // R : 右端のデータの場所+1
        int key = 73 ;
        while( L != R ) {
            int M = (L + R) / 2 ;
            if ( a[M] == key )
                break ;
            else if ( a[M] < key )
                L = M + 1 ;
            else
                R = M ;
        }
    }
}

このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。

    …両辺のlogをとる

2分探索は、繰り返し処理であるから、処理時間は、

  … (Mはループ回数)

ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式 ()で係数が出てくるが、これはT_βに含めて考えればいい。

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

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

単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。

// ((case-3))
// 選択法 O(N^2)
#include <stdio.h>

int main() {
    int a[] = {
        12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
    } ;
    int size = 10 ;
    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 ;
    }
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int a[] = {
            12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
        } ;
        int size = a.length ;
        for( int i = 0 ; i < size - 1 ; i++ ) {
            int tmp ;
            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)は…

… i=0の時
… i=1の時
:
         … i=N-1の時

        …(参考 数列の和の公式)

となる。

オーダー記法

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

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

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

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

練習問題

1. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか？
2. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
   データ10000件なら何[sec]かかるか？
   (ヒント: 底変換の公式)
3. の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
4. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

• 2と4の解説
• 1は、N→∞において、N² ≪ 2^Nなので、O(2^N) 。厳密に回答するなら、練習問題4と同様の証明が必要。
• 3は、O(1)。
  • 誤答の例：O(0)と書いちゃうと、T(N)=T_α×0=0になってしまう。
  • 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)

基本的なガイダンス

情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。

• 情報構造論の講義録は、すべてこの BLOG に残します。
• 過去のテスト問題は、こちらにすべて残ってます。

プログラムを評価する3つのポイント

まずは以下を読む前に、質問。

• あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
  • ここまでの段階で3つの要点を考えメモしてください。

具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。

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

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

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

int 型のメモリ使用量は？

int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。

32bit の0/1情報の組み合わせで、2³²通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-2³¹～0～2³¹-1 の範囲を扱うことができる。2³¹ = 2×2¹⁰×2¹⁰×2¹⁰ ≒ 2×1000³

32bit = 4byte

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？

• アルゴリズム – 計算手順の考え方。
• プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
• ソフトウェア – プログラムと、その処理に必要なデータ。
  (日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない)
• パラダイム – プログラムをどう表現すると分かりやすいか？

トレードオフ関係をプログラムで確認

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

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int main() {
   int a[ SIZE ] = {
      52 , 14 , 82 , 62 , 15
   } ; // 配列
   int size =  5 ;      // 実際のデータ数(Nとする)
   int key  = 62 ;      // 探すデータ
   for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル
      if ( a[i] == key ) {
         printf( "Find %d¥n" , key ) ;
         break ;
      }
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         52 , 14 , 82 , 62 , 15
      } ;
      int key = 62 ;
      for( int i = 0 ; i < a.length ; i++ ) {
          if ( a[i] == key ) {
             System.out.println( "Find " + key ) ;
             break ;
          }
      }
   }
}

// import java.util.Arrays;  // こういった正当なJavaのプログラムでは、
// public class Main {       // データ件数が大きくなった時の挙動がわからない
//    public static void main( String[] args ) {
//       Integer a[] = {
//          52 , 14 , 82 , 62 , 15    // Integer型 int 型は何が違うの？
//       } ;
//       if ( Arrays.asList( a ).contains( 62 ) ) {
//          System.out.println("配列内に値が存在しています。");
//       }
//    }
// }

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法 O(log N)
// 速いけど、プログラムは分かりにくく(複雑に)なった
int main() {
   int a[] = {
      14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
   } ; 
   int L=0 , R= 5 ; 
   while( L != R ) {
      int M = (L + R) / 2 ;
      if ( a[M] == key )
         break ;
      else if ( a[M] < key )
         L = M + 1 ;
      else
         R = M ;
   }
}

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      int a[] = {
         14 , 15 , 52 , 62 , 82  // データはあらかじめ昇順に並べておく
      } ;
      int key = 62 ;
      int L = 0 ;
      int R = a.length ;
      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[ 272925 ] = 272925 ;
：
// データを探したければ a[ 電話番号 ] で探せばいい
printf( "%d\n" , a[ 621111 ] ) ;
// 処理速度はクソ速いけど、メモリは大量消費

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

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

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

皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!

• 繰り返し処理と処理時間の見積もり
• 値渡しと参照渡しとポインター
• ポインタと文字列処理
• 情報構造論のレポート課題
• 配列に要素を追加
• Javaのオブジェクト指向入門
• Javaでリスト構造
• スタックと待ち行列
• 前期期末前の課題レポート
• 集合とリスト処理
• ランダムアクセス・シーケンシャルアクセスから双方向リスト
• 双方向リストとdeque
• 2分探索木
• 2分探索木への追加とAVLと2分ヒープ
• 2分木の応用(意思決定木と演算子)
• 2分木による構文木
• 木構造の探索・深さ優先探索・幅優先探索
• データベースとB木
• ハッシュ法
• メモリ管理・スタック領域とヒープ領域
• ガベージコレクタとヒープ管理
• 関数ポインタとラムダ式
• レポート課題(後期期末) ハッシュ法
• Javaでラムダ式の呼び出し

課題内容

以下の内容の中から１つを選びハッシュ法でデータを登録・検索するプログラムを作成せよ。

• 名前と電話番号 – 名前で検索、電話番号で検索などができること。
• 名前とメールアドレス – メールアドレスで検索し、名前を表示… などができること。
• 名前と生年月日 – 名前で誕生日を検索などができること。

ハッシュ衝突が発生しているかどうかを確認し、ハッシュ関数を変更することでハッシュ衝突がどうなるかの違いなどを検証すること。

レポート提出先

• 2025-01-27-ハッシュ法

関数ポインタとコールバック関数

JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワードが出てきているが、この意味を正しく理解しているだろうか？

このような (function()…)は、無名関数と呼ばれている。(=>を使った書き方はアロー関数と呼ばれている)　これは「関数を引数として渡す機能」と、「一度しか使わないような関数にいちいち名前を付けないで関数を使うための機能」であり、このような機能は、関数を引数で渡す機能はC言語では関数ポインタと呼ばれたり、新しいプログラム言語では一般的にラムダ式などと呼ばれる。

// JavaScriptの無名関数の例 3+4=7 を表示
console.log( (function( x , y ) {
                 return x + y ;
              })( 3 , 4 ) ) ; // 無名関数
console.log( ((x,y) => {
                 return x + y ;
              })( 3 , 4 ) ) ; // アロー関数(ラムダ式)

C言語の関数ポインタの仕組みを理解するために、以下のプログラムを示す。

int add( int x , int y ) {
   return x + y ;
}
int mul( int x , int y ) {
   return x * y ;
}
void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = add ;               // f = add( ... ) ; ではないことに注意
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
                 // f( 3 , 4 ) と書いてもいい
   f = mul ;
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}

このプログラムでは、関数ポインタの変数 f を定義している。「 int (*f)( int , int ) ; 」 は、“int型の引数を2つ持つ、返り値がint型の関数”へのポインタであり、「 f = add ; 」では、f に加算する関数addを覚えている。add に実引数を渡す()がないことに注目。C言語であれば、関数ポインタ変数 f には、関数 add の機械語の先頭番地が代入される。

そして、「 (*f)( 3 , 4 ) ; 」により、実引数を3,4にて f の指し示す add を呼び出し、7 が答えとして求まる。

こういう、関数に「自分で作った関数ポインタ」を渡し、その相手側の関数の中で自分で作った関数を呼び出してもらうテクニックは、コールバックとも呼ばれる。コールバック関数を使うC言語の関数で分かり易い物は、クイックソートを行う qsort() 関数だろう。qsort 関数は、引数にデータを比較するための関数を渡すことで、様々な型のデータの並び替えができる。

#include <stdio.h>
#include <stdlib.h>

// 整数を比較するコールバック関数
int cmp_int( int* a , int* b ) {
   return *a - *b ;
}
// 実数を比較するコールバック関数
int cmp_double( double* a , double* b ) {
   double ans = *a - *b ;
   if ( ans == 0.0 )
      return 0 ;
   else if ( ans > 0.0 )
      return 1 ;
   else
      return -1 ;
}

// ソート対象の配列
int    array_int[ 5 ] = { 123 , 23 , 45 , 11 , 53 } ;
double array_double[ 4 ] = { 1.23 , 12.3 , 32.1 , 3.21 } ;

void main() {
   // 整数配列をソート
   qsort( array_int , 5 , sizeof( int ) ,
          (int(*)(const void*,const void*))cmp_int ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~この分かりにくい型キャストが必要なのがC言語の面倒な所
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%d\n" , array_int[ i ] ) ;
   // 実数配列をソート
   qsort( array_double , 4 , sizeof( double ) ,
          (int(*)(const void*,const void*))cmp_double ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%f\n" , array_double[ i ] ) ;
}

無名関数

コールバック関数を使っていると、データを比較するだけの関数とか簡単な短い処理が使われることが多い。こういった処理を実際に使われる処理と離れた別の場所に記述すると、プログラムが読みづらくなる。この場合には、その場で関数の名前を持たない関数(無名関数)を使用する。(C++の無名関数機能は、最近のC++の文法なのでテストには出さない)

void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = []( int x , int y ) { return x + y ; } ; // add を無名関数化
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7

   // mul を無名関数にしてすぐに呼び出す3*4=12 
   printf( "%d¥n" , []( int x , int y ) { return x * y ; }( 3 , 4 ) ) ;
   // メモ：C++11では、ラムダ式=関数オブジェクト
   //      C++14以降は、変数キャプチャなどの機能が追加されている。
}

C++の変数キャプチャとJavaScriptのクロージャ

JavaScript のクロージャ

JavaScriptにおいて、関数オブジェクトの中で、その周囲(レキシカル環境)の局所変数を参照できる機能をクロージャと呼ぶ。クロージャを使うことでグローバルな変数や関数の多用を押さえ、カプセル化ができることから、保守性が高まる。

// JavaScriptにおけるクロージャ
function foo() {
   let a = 12 ; // 局所変数
   console.log( (function( x , y ) {
                    return a + x + y ;  // 無名関数の外側の局所変数aを参照できる
                 })( 3 , 4 ) ) ;
}
foo() ;

C++の変数キャプチャ

C++でも無名関数などでクロージャと同様の処理を書くことができるようにするために変数キャプチャという機能がC++14以降で使うことができる。

// C++のラムダ関数における変数キャプチャ
void main() {
   int a = 12 ;
   printf( "%d\n" ,
           [a]( int x , int y ) {  // 変数キャプチャ[a]の部分
              return a + x + y ;   // 局所変数aをラムダ関数内で参照できる。
           }( 3 , 4 ) ) ;
   return 0 ;
}

Javaでラムダ式を使う例

Javaでも Java8 以降でラムダ式の機能が使えるようになっている。以下のように、ArrayList や Array の全要素に対して処理を行う forEach() メソッドでは、各要素に対して実行する関数を、無名関数として渡すことで、ループを回す繰り返し文を使わずにプログラムを記述できる。

// ArrayList<> の forEach() メソッド (Google Geminiの生成した例)
import java.util.List ;
import java.util.ArrayList ;

public class ForEachExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        // forEachを使ってリストの要素を出力
        names.forEach( name -> System.out.println(name) );
    }               // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 無名関数(ラムダ式)
}                   // 　　型推論のおかげで name の変数宣言も書く必要がない...
                    //    names.forEach( (String name) -> System.out.println( name ) ) ;
-------------------------------------------------------------------------------------
// Array の forEach() メソッド
import java.util.Arrays ;

public class ForEachExample2 {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        // 配列の要素を2倍にして出力
        Arrays.stream(numbers).forEach( number -> System.out.println(number * 2) );
    }                                // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 無名関数(ラムダ式)
}

Javaでは、ラムダ式は 関数型インタフェースと組み合わせて使う必要がある。forEach() メソッドは、Consumer という関数型インタフェースを持ち、引数に書いたラムダ式は、関数型インタフェースの実装として扱われている。
(JavaScriptみたいに、let f = (x) => { return x*x ; } のような単純なラムダ式は使えない)

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

排他処理の実装方法

排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。

ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)

• C言語でのファイルロック(共有ロック,排他ロックの機能あり)
• 共有ロック：他のプロセスの読み込みは許可するけど、書き込みは禁止。
• 排他(占有)ロック：他のプロセスの読み込みも書き込みも禁止する。
• 使い終わったらアンロック。

セマフォの例としては、カウンタセマフォが使われる。

• 対象資源を使用中のプロセスの数を表す、カウンタを使う。
• 初期値0の状態は、だれも使っていない状態。
• 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。

ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。

ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

1. ロッキング方式(悲観的制御)
   先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。
   • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
     
   • ロックの種類
     ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
     この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
   • 2相ロッキングプロトコル
     トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
2. 時刻印方式/タイムスタンプ方式(楽観的制御)
   データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。