Javaでの引数に対する副作用

Javaでのプログラムにおいて、下記のように関数に引数でデータが渡された場合、呼び出し元の変数が変化する／変化しないの違いが分かるであろうか？

import java.util.*;

class A {
    private int a ;
    public A( int x ) { a = x ; }
    public void set( int x ) { a = x ; }
    public int get() { return a ; }
}

public class Main {
    public static void foo( int x , Integer y , String s , int z[] , A a ) {
        x = 12345 ;        // プリミティブな引数の書き換え
        y = 23456 ;        // イミュータブルな引数の書き換え
        s = "hoge" ;
        z[0] = 34567 ;     // 参照で渡されたオブジェクトの書き換え
        a.set( 45678 ) ;
    }
    public static void main(String[] args) throws Exception {
        int     mx = 11111 ;        // プリミティブなデータ
        Integer my = 22222 ;        // イミュータブルなオブジェクト
        String  ms = "aaa" ;
        int     mz[] = { 33333 } ;  // それ以外のオブジェクト
        A       ma = new A( 44444 ) ;

        foo( mx , my , ms , mz , ma ) ;

        System.out.println( "mx="+mx+",my="+my+",ms="+ms+",mz[0]="+mz[0]+",ma="+ma.get() );
    }
}

• Paiza.ioのプログラム

上記のプログラムでは、foo() の第1引数 mx は、プリミティブ型なので関数の引数に渡される際には、コピーが生成されて渡されるため、呼び出し元の変数 mx の値は変化していない。

Javaでは、プリミティブ型以外のデータは、ヒープ領域に実体が保存され、そのデータの場所(ポインタ)によって管理される。

しかし、Integer型のオブジェクト my や、String型のオブジェクト ms は、参照(データの場所)が渡されるが、イミュータブルな(変更できない)オブジェクトなので、値の代入が発生すると新しいオブジェクトが生成され、そのアドレスが参照を保存している変数(ポインタ)に代入される。このため、呼び出し元の my や ms は値が変化しない。

これに対し、配列 mz や クラスオブジェクト ma は、オブジェクトの中身を関数 foo で値を変更すると、呼び出し元の変数の内容が変更される。こういった関数やメソッドの呼び出しによって、呼び出し元の値が変化することは「副作用」と呼ばれる。

こういった参照のメカニズムは、データの管理の仕方を正しく理解する必要があることから、もっと原始的な C 言語にて理解を目指す。

C言語の基礎

#include <stdio.h>

int main() {
   int n ;
   scanf( "%d" , &n ) ;  // 標準入力から整数をnに保存
   int m = 1 ;
   for( int i = 1 ; i <= n ; i++ )
      m *= i ;
   printf( "%d! = %d\n" , n , m ) ; // 
   return 0 ;
}

printf の最初の引数は、表示する際のフォーマットであり、%d の部分には対応する引数の値に置き換えて表示される。

   型                |   基数             |   型            |   表示方式
  long int      %ld  |  10進数        %d  |  double    %lf  |  固定小数点表示 %f  12.34
  int           %d   |  16進数        %x  |  float     %f   |  指数小数点表示 %e  1.234e+1
  short int     %hd  |   8進数        %o  |                 |  固定/指数自動  %g
  char          %c   |                    |  printf( "%5.2f" , 1.2345 ) ; □1.23
  char[], char* %s   |                    |

// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'
// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'\0'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}
'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}

C言語でのポインター

#include <stdio.h>

int main() {
    int  x  = 123 ; //                             px [ 〇 ]
    int* px ;       // px はポインタ                      ↓
    px = &x ;       // x の変数の番地を px に代入      x [ 123 ]
    *px = 321 ;     // px の指し示す場所に 321 を代入
    printf( "%d\n" , x ) ; // 321 を出力
    return 0 ;
}

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

前回の講義で説明できなかった、オーダーの問題の解説

練習問題

1. の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
2. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか？
3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

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

再帰呼び出しの基本

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

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

// 階乗 (末尾再帰)
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 ) ;
}

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

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

再帰呼び出しの処理時間

次に、この再帰処理の処理時間を説明する。 最初の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 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

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

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

// 分割統治法による配列合計

#include <stdio.h>

int sum( int a[] , int L , int R ) { // 非末尾再帰
    // L : 左端のデータ
    // R : 右端のデータが入っているの場所+1
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    int array[ 8 ] = {
    // L=0  1   2   3   4   5   6   7   R=8
        3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
    } ;
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

// 分割統治法による配列合計

import java.util.*;

public class Main {
    static int sum( int a[] , int L , int R ) { // 非末尾再帰
        // L : 左端のデータ
        // R : 右端のデータが入っているの場所+1
        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 {
        int array[] = {
        // L=0  1   2   3   4   5   6   7  R=8  
            3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
        } ;
        System.out.println( sum( array , 0 , array.length ) );
    }
}

このプログラムでは、配列の合計を計算しているが、引数の 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枚以上で予想が常に成り立つことが証明できた。

また、ハノイの塔の処理時間は、で表せる。