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

配列にデータを追加

次々と与えられた値を保存していくのであれば、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件ほど未満になったら、ソート方法を選択ソートに切り替えるように作られている。