データが登録済みかどうかを判定する処理を作るために、登録された値を配列に次々と値を追加保存する場合、どのようにプログラムを記述するだろうか？

配列にデータを追加

次々と与えられた値を保存していくのであれば、Java であれば下記のようなコードが一般的であろう。
でも、ArrayList とはどのようにデータを覚えているのだろうか? なぜ 宣言は ArrayList<Integer> array であって ArrayList<int> array で宣言するとエラーが出るのであろうか?

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // ArrayList は連続アドレス空間に保存してくれる可変長配列
        //   ランダムアクセスをする場合に向いている
        ArrayList<Integer> array = new ArrayList<Integer>() ;
        array.add( 11 ) ;
        array.add( 2 ) ;
        array.add( 333 ) ;
        
        for( Integer i : array ) {
            System.out.println( i ) ;
        }
    }
}

このような ArrayList のようなデータ構造の仕組みを考えるために、最も単純な配列でプログラムを作ってみる。

末尾に追加

import java.util.*;

public class Main {
    static int[] array = new int[ 10 ] ;
    static int   size  = 0 ;

    public static void add( int x ) {
        array[ size ] = x ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        add( 11 ) ;
        add( 2 ) ;
        add( 333 ) ;
        
        for( int i = 0 ; i < size ; i++ )
            System.out.println( array[i] ) ;
    }
}

同じ処理をC言語で書いてみる。

#include <stdio.h>

int array[ 10 ] ;
int size = 0 ;

void add( int x ) {          // if ( size < array.length ) ... の判定が必要かも
    array[ size ] = x ;
    size++ ;
}

int main() {
    add( 11 ) ;
    add( 2 ) ;
    add( 333 ) ;

    for( int i = 0 ; i < size ; i++ )
        printf( "%d\n" , array[ i ] ) ;
    return 0 ;
}

しかし、このプログラムでは、最初に宣言した要素数10個を越えてデータを保存できないし、配列溢れさせないためには要素数の上限チェックも必要となるだろう。

昇順に並べながら途中に要素を追加

前述のプログラムでは、配列の末尾の場所を size で覚えておき、末尾にデータを追加していた。でも、配列に保存されている値の中から目的の値が含まれているか検索したいのであれば、配列に要素を昇順に保存しておいて2分探索法を使うのが一般的であろう。では、前述のプログラムを昇順で保存するにはどうすべきか？

最も簡単な方法で書くのであれば、下記のようなコードになるかもしれない。

public static void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) { // ここは2分探索で書けば O( log N ) にできるかも
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )   // 途中に挿入は、コレじゃダメ?
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- ) // 途中にデータを入れるために要素を１つ後ろに移動
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) {
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- )
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

このプログラムでは、for( i … ) の処理でデータを挿入すべき場所を見つけ、for( int j … ) の繰り返しでデータを1つ後ろにずらしてから要素を加えている。

for( i … ) の処理は、このプログラムでは O( N ) となっているが、2分探索法を用いれば O( log N ) に改善ができるかもしれない。しかし、for( int j… ) の処理は、データを1つ後ろにずらす必要があるため O( N ) の処理が必要となる。

ここで、途中にデータを追加する処理の効率を改善することを考える。

リスト構造の導入

以下のデータ構造では、配列にデータと次のデータの場所を覚えることで、一見デタラメな順序に保存されているようにみえるが、next[] に次の値の保存されている場所が入っている。

import java.util.*;

public class Main {           //    0    1    2    3    4    5
    static int[] data = new int[] { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
    static int[] next = new int[] { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
    static int   size = 5 ;
    static int   top = 0 ;

    static void insert( int n , int x ) {
        data[ size ] = x ;
        next[ size ] = next[ n ] ;
        next[ n ] = size ;
        size++ ;
    }
    
    public static void main(String[] args) throws Exception {
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
        insert( 2 , 25 ) ;
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
    }
}

#include <stdio.h>

int  data[ 10 ] = { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
int  next[ 10 ] = { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
int  size = 5 ;
int  top  = 0 ;

void insert( int n , int x ) {
    data[ size ] = x ;
    next[ size ] = next[ n ] ;
    next[ n ] = size ;
    size++ ;
}

int main() {
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    insert( 2 , 25 ) ;
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    return 0 ;
}

このようなデータ構造であれば、データ自体は末尾に保存しているが、次の値が入っている場所を修正することで途中にデータを挿入することができる。この方法であれば、途中にデータを入れる場合でもデータを後ろにずらすような処理が不要であり、O(1)で途中にデータを挿入できる。

同じプログラムを、データと次のデータの配列番号のオブジェクトで記述してみた。

import java.util.*;

class DataNext {
    public int data ;
    public int next ;
    DataNext( int d , int n ) {
        this.data = d ;
        this.next = n ;
    }
}

public class Main {
    public static DataNext[] table = {
        new DataNext( 11 , 2 ) ,
        new DataNext( 55 , -1 ) ,
        new DataNext( 22 , 4 ) ,
        new DataNext( 44 , 1 ) ,
        new DataNext( 33 , 3 ) ,
        null , 
        null , 
        null ,
        null ,
        null ,
    } ;
    public static int size = 5 ;
    
    public static void insert( int n , int x ) {
        table[ size ] = new DataNext( x , table[ n ].next ) ;
        table[ n ].next = size ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        for( int idx = 0 ; idx >= 0 ; idx = table[ idx ].next )
            System.out.println( table[ idx ].data ) ;
            
        insert( 2 , 25 ) ;
        
        for( int idx = 0 ; idx >= 0 ; idx = table[ idx ].next )
            System.out.println( table[ idx ].data ) ;
    }
}

• オブジェクトで途中に挿入(Paiza.io)

このプログラムでは、配列の当初の長さを超えてデータを格納することはできない。

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存するために、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;

        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

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

struct ListNode {
    int       data ;
    ListNode* next ;
} ;

ListNode* newListNode( int d , ListNode* nx ) {
    ListNode* _this = new ListNode() ;
    if ( _this != NULL ) {
        _this->data = d ;
        _this->next = nx ;
    }
    return _this ;
}

int main() {
    ListNode* top = newListNode( 11 , newListNode( 22 , newListNode( 33 , NULL ) ) ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    top->next = newListNode( 15 , top->next ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    return 0 ;
}

Javaのジェネリクス

Javaのジェネリクス(C++のテンプレート)を使って書いてみた。ジェネリクスは、クラスやメソッドにおいて、特定の型を指定することなく動作するコードを記述することができる機能。これにより、型安全性を保ちながら、コードの再利用性と柔軟性を向上させることがでる。

import java.util.*;

class ListNode<T> {
    T           data ;
    ListNode<T> next ;
    
    ListNode( T d , ListNode<T> n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        // var 宣言は型推論で、右辺のデータ型を自動的に選択してくれる。
        // itop は整数型のリスト
        var itop = new ListNode<Integer>( 11 , new ListNode<Integer>( 22 , new ListNode<Integer>( 33 , null ) ) ) ;
        // new List<int>( 11 , ... ) と書くと、<>の中は reference しか使えないと言われる。
        for( var p = itop ; p != null ; p = p.next )
            System.out.println( p.data ) ;

        // stop は文字列型のリスト
        var stop = new ListNode<String>( "aa" , new ListNode<String>( "bb" , new ListNode<String>( "cc" , null ) ) ) ; 
        for( var p = stop ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

前述のプログラムをJavaのジェネリッククラスで記述

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // LinkedList は上記のリスト構造で保存される。
        //    途中に要素の追加削除を行ったり、シーケンシャルアクセスに向いたデータ構造
        var top = new LinkedList<Integer>() ;
        top.add( 11 ) ;
        top.add( 22 ) ;
        top.add( 33 ) ;
        for( int i : top )            // 11 22 33
            System.out.println( i ) ;
        top.add( 1 , 15 ) ;
        for( int i : top )            // 11 15 22 33
            System.out.println( i ) ;
    }
}

---

クラスの宣言とコンストラクタ・メソッド

import java.util.*;

// クラス宣言
class Person {
    // データ構造
    String name ;
    int    age ;

    // コンストラクタ(データ構造を初期化する関数)
    Person( String n , int x ) {
        this.name = n ;    // this は対象となるデータそのものを指す
        this.age  = x ;    // 対象が明言されていれば、this は省略可能
    }
    // データを扱うメソッド
    void print() {                 // データを表示
        System.out.println( this.name + "," + this.age ) ;
    }
    boolean sameAge( Person x ) {  // 同じ年齢か判断するメソッド
        return this.age == x.age ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {

        Person tsaitoh = new Person( "Tohru Saitoh" ,  59 ) ;
        Person tomoko  = new Person( "Tomoko Saitoh" , 48 ) ;

        tsaitoh.print() ;  // Tohru Saitoh, 59
        tomoko.print() ;   // Tomoko Saitoh,48

        if ( tsaitoh.sameAge( tomoko ) ) {
            // sameAge( Person x ) では、
            // this = tsaitoh , x = tomoko となって呼び出される
            System.out.println( "同じ年齢ですよ" ) ;
        }
        Person[] family = new Person[ 2 ] ;
        family[0] = tsaitoh ;
        family[1] = tomoko ;
        for( int i = 0 ; i < 2 ; i++ )
            family[ i ].print() ;
    }
}こ

このプログラムのデータ構造は下記のような状態。

前期中間前レポート課題(選択2)

4年の情報構造論で、リスト構造などの内容を進める前に、3年プログラミング応用でクラスなどに自信がない人向けの簡単レクチャ。

クラスは、データ構造と手続き

例えば、名前と年齢のデータをクラスで扱うのであれば、以下のようなコードが基本となるだろう。

import java.util.*;

class NameAge {
    String name ;          // インスタンス変数
    int    age ;           // インスタンス変数
    static int count = 0 ; // クラス変数
    // コンストラクタ
    NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

実行結果
tsaitoh,59
member = 1
age = 59
tomoko,48
member = 2

• オブジェクト指向の基礎(Paiza.io)

クラスとは、データ構造(オブジェクト)とそのデータ構造を扱うための関数(メソッド)をまとめて扱う。

クラス NameAge の中で宣言されている、NameAge() の関数は、オブジェクトを初期化するための関数(メソッド)であり、特にコンストラクタと呼ばれる。

実際にデータを保存するための tsaitoh や tomoko とよばれる変数に NameAge オブジェクトの実体(インスタンス)を作る時には 「new クラス名」 とやることで、初期化ができる。

イメージでは、下図のようなデータ構造ができあがる。

でも、年齢の覚え方は、将来的に誕生日を覚えるように変化するかもしれない。この際に、Main 関数の中で age を使うと後で混乱の元になるかもしれない。こういう時は、NameAge クラス以外では中身を勝手に使わせないために、インスタンス変数などに public / private といったアクセス制限を加える。

import java.util.*;
class NameAge {
    private String name ;          // インスタンス変数
    private int    age ;           // インスタンス変数
    public  static int count = 0 ; // クラス変数
    // コンストラクタ
    public  NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    public void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ここがエラーになる。NameAge::age は private 
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

クラス自体も、public class NameAge … のように宣言することもあるが、public なクラスは 1つ の *.java ファイルの中に1つしか書けないというルールがあるので要注意。

練習問題

科目(Subject)と学生(Student)の情報があり、科目を受講した成績(Result)で成績を管理している。
このデータを管理するためのクラスを宣言し、下に示すようなデータSubject,Result,Studentの配列を作り、下に示したような出力が得られるプログラムを作成せよ。

科目: Subject
id    name      teacher    // Subject[] subject_table = {
10010 情報構造論 t-saitoh   //    new Subject( 10010 , "情報構造論" , "t-saitoh" ) ,
10020 電気磁気学 takaku     //    new Subject( ....
10030 電気回路   komatsu    // } ;

成績: Result
s_id  id         point      // Result[] result_table = {
58563 10020      83         //    new Result( 16213 , 10020 , 83 ) ,
58564 10010      95         //    new Result( ...
58573 10030      64         // } ;
58563 10010      89

学生: Student
s_id  name      age        // Student[] student_table = {
58563 斉藤太郎   18          //    new Student( 16213 , "斉藤太郎" , 18 ) ,
58564 山田次郎   19          //    new Student( ...
58573 渡辺花子   18          // } ;

以下のようなデータが出力されること
斉藤太郎 電気磁気学 83
渡辺花子 情報構造論 95
山田次郎 電気回路   64
斉藤太郎 情報構造論 89

• 課題のひな形(Paiza.io)

前期中間前レポート課題(選択1)

例年であれば、プログラム作成中心のレポート課題をやってもらっているけど、前期中間試験は今回早めに行われるので、プログラム作成か、処理速度のオーダを実際に計測実験のいずれかとする。

現在時間を ミリ秒の精度で求める System.currentTimeMills() を使って、様々なプログラムの処理時間を計測してみよう。ただし、OS によって 100ミリ秒未満はあまり正確に測れない。このため、処理時間は繰り返し処理などを入れることで、10秒程度になるようにすること。また、動作例で示した Paiza.io では、長い処理時間のプログラムは、途中で強制終了させられるので、自分のパソコンにインストールしてある環境で動作させること。また、並列処理しているプログラムの影響を受ける可能性もあることから、他の処理の影響がでないように工夫すること。

様々なプログラムの実行時間を計測してみよう

import java.util.*;

public class Main {
    // 乱数を配列にセット
    public static void array_set_random( int[] array ) {
        Random rnd = new Random() ;
        for( int i = 0 ; i < array.length ; i++ )
            array[ i ] = rnd.nextInt( array.length ) ;
    }
    // 配列を選択法でソート
    public static void array_sort( int[] array ) {
        for( int i = 0 ; i < array.length - 1 ; i++ ) {
            int min = i , j ;
            for( j = i + 1 ; j < array.length ; j++ ) {
                if ( array[ min ] > array[ j ] )
                    min = j ;
            }
            int tmp = array[ i ] ;
            array[ i ] = array[ min ] ;
            array[ min ] = tmp ;
        }
    }
    public static void main(String[] args) throws Exception {
        // 変化させるデータ件数
        int[] data_n = {
            2500 ,
            5000 ,
            7500 ,
            10000
        } ;
        for( int i = 0 ; i < data_n.length ; i++ ) {
            int[] array = new int[ data_n[ i ] ] ;
            // 配列を乱数で埋める時間は測りたくない
            array_set_random( array ) ;
            long start = System.currentTimeMillis() ;
            array_sort( array ) ;
            // ソート結果の表示時間は測りたくない
            //for( int x = 0 ; x < array.length ; x++ )
            //    System.out.print( array[ x ] + " " ) ;
            //System.out.println() ;
            long end   = System.currentTimeMillis() ;
            System.out.println( "Time = " + (end - start) ) ;
        }
    }
}

• データ件数と処理時間の計測(Paiza.io)

プログラムによっては、処理時間が短すぎる場合があるので、下記のように 1000 回ループさせるなどで、一定時間以上の処理となるように工夫すること。

public static int fact( int x ) {
    if ( x == 1 )
        return 1 ;
    else
        return x * fact( x - 1 ) ;
}
public static void main(String[] args) throws Exception {
    int[] data_n = { 2 , 4 , 6 , 8 , 10 } ;
    for( int i = 0 ; i < data_n.length ; i++ ) {
        long start = System.currentTimeMillis() ;
        for( int j = 0 ; j < 1000 ; j++ ) {
            int ans = fact( data_n[ i ] ) ;
        }
        long end = System.currentTimeMillis() ;
        System.out.println( "Time = " + ( end - start ) ) ;
    }
}

レポート内容

データ件数や 引数に与える数によって、処理時間が変化するプログラムを記述し、そのプログラムを N を変化させながら上記のプログラムなどを参考に処理時間を計測する。時間計測には誤差が大きく含まれる可能性があることから、複数回実行して平均をとるなどの工夫もすること。

授業中に示したプログラムなどの計測を行う場合は、ループのプログラムの変化と、別プログラムの再帰の場合の変化の２つについて結果を示すこと。創造工学演習の再帰問題の課題の整数比の直角三角形探索、辺の組み合わせ問題、N Queen、ハノイの塔など、自分で興味のあるテーマを選んだ場合は1つでも良い。

この上で、(1) プログラムリスト, (2) 時間計測にあたり工夫したこと, (3) 実際の実行結果のグラフ, (4) その結果の考察した結果をレポートにまとめて提出せよ。

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

1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
   • T_S(10)=T_s x 100 = 10msec よって T_s = 0.1msec
     • 0.1msec * 100 * 100 = 1000 msec
   • T_Q(10)=T_q x 10 x log₁₀ 10 = 20msec よって T_q=2msec
     • 2msec * 100 * log₁₀ 100 = 400 msec
2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

• • 2025-05-01-qsort-sel.xlsx より 30件以上

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

上記の計算時間は、計算しやすい値を例に示したが、一般的なプロセッサであれば、10件～30件程度で選択ソートとクイックソートの処理時間が入れ替わる。

これらを踏まえ、ライブラリとして使われるクイックソートプログラムでは、データ件数が20件ほど未満になったら、ソート方法を選択ソートに切り替えるように作られている。

ハノイの塔

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

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

一般解の予想

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

 … ①

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

再帰方程式

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

 … ②
　… ③

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

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

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

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

再帰を用いた並び替え

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

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

 

	アルゴリズム	処理時間のオーダー
	バブルソート
	選択ソート
	クイックソート, マージソート

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

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

import java.util.*;

// マージソートは、リスト構造を使っているので、
// クイックソートより効率が悪い。
// でもオーダーとしては、O( N log N ) のアルゴリズム

public class Main {
    public static LinkedList merge_sort( LinkedList list ) {
        // データ件数が1件ならソート不要
        if ( list.size() <= 1 ) {
            return list;
        }
        // 左右2つに分割
        int mid = list.size() / 2 ;
        LinkedList<Integer> left  = new LinkedList<>( list.subList( 0 ,   mid         ) ) ;
        LinkedList<Integer> right = new LinkedList<>( list.subList( mid , list.size() ) ) ;

        // 左右をそれぞれマージソート
        LinkedList<Integer> sorted_left  = merge_sort( left  ) ;
        LinkedList<Integer> sorted_right = merge_sort( right ) ;

        // 左右のリストをマージする。
        LinkedList merged = new LinkedList<>() ;   // 初期状態は空っぽ
        // 左右のリストの小さい方を取り出して答えに追加していく
        while( !sorted_left.isEmpty() && !sorted_right.isEmpty() ) {
            int left_top  = sorted_left.get( 0 ) ;
            int right_top = sorted_right.get( 0 ) ;
            if ( left_top > right_top ) {
                merged.add( sorted_right.removeFirst() ) ;
            } else {
                merged.add( sorted_left.removeFirst() ) ;
            }
        }
        // 残ったリストを追加
        while( !sorted_left.isEmpty() )
            merged.add( sorted_left.removeFirst() ) ;
        while( !sorted_right.isEmpty() )
            merged.add( sorted_right.removeFirst() ) ;
        
        return merged ;
    }

    public static void main( String[] args ) {
        // ソート対象のデータ
        LinkedList<Integer> data = new LinkedList<>() ;
        data.add( 38 ) ;
        data.add( 27 ) ;
        data.add( 43 ) ;
        data.add(  3 ) ;
        data.add(  9 ) ;
        data.add( 82 ) ;
        data.add( 10 ) ;

        System.out.println( "ソート前: " + data ) ;
        LinkedList<Integer> sorted_data = merge_sort( data ) ;
        System.out.println( "ソート後: " + sorted_data ) ;
    }
}

• LinkedListを用いたマージソート(Paiza.io)

マージソートの分析

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

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

• 
• 

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

：

よって、

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

データ数 N = 10 件でソート処理の時間を計測したら、選択法で 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でラムダ式の呼び出し