リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。集合処理の記述には、2進数を使った方式やリストを用いた方法が一般的である。以下にその処理について示す。

bit演算子

2進数を用いた集合処理を説明する前に、2進数を使った計算に必要なbit演算子について復習してみる。

bit演算子は、その数値を2進数表記とした時の各ビットをそれぞれAND,OR,EXOR,NOTなどの計算を行う。

bit演算子	計算の意味	関連知識
& bit AND	3 & 5 0011)2 & 0101)2= 0001)2	論理積演算子 if ( a == 1 && b == 2 ) …
| bit OR	3 | 5 0011)2 | 0101)2= 0111)2	論理和演算子 if ( a == 1 || b == 2 ) …
~ bit NOT	~5 ~ 00..00,0101)2= 11..11,1010)2	論理否定演算子 if ( !a == 1 ) …
^ bit EXOR	3 ^ 5 0011)2 ^ 0101)2= 0110)2
<< bit 左シフト	3 << 2 0011)2 << 2 = 001100)2	x << y は と同じ
>> bit 右シフト	12 >> 2 1100)2 >> 2 = 11)2	x >> y は  と同じ

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      System.out.println( 12 & 5 ) ;    // 1100 & 0101 = 0100 = 4
      System.out.println( 12 | 5 ) ;    // 1100 | 0101 = 1101 = 13
      System.out.println( ~12 & 0xF ) ; // ~1100 & 1111 = 0011 = 3
      System.out.println( 3 << 2 ) ;    // 0011 << 2 = 1100
      System.out.println( 12 >> 2 ) ;   // 1100 >> 2 = 0011
      System.out.println( ~12 + 1 ) ;   // ~0..00001100 + 1 = 1..11110011 + 1 = 1..11110100 = -12
   }
}

論理演算子とbit演算子の違い

論理積,論理和という点では、論理演算子&&,|| と bit演算子&,| は複数桁の2進数で計算する違いと思うかもしれないが、論理演算子&&,|| は若干挙動が違う。論理積&&演算子は、左辺の結果が false だと(結果がfalse確定なので) 右辺の計算式や呼び出されない。同じように論理和||演算子は、左辺の結果が true だと(結果がtrue確定なので) 右辺の計算式は呼び出されない。

import java.util.*;

public class Main {
    static boolean boolean_print( boolean yn ) {
        System.out.print( yn + " " ) ;
        return yn ;
    }
    static int int_print( int yn ) {
        System.out.print( yn + " " ) ;
        return yn ;
    }
    public static void main(String[] args) throws Exception {
        boolean ans ;
        int     x ;
        ans = boolean_print( true )  && boolean_print( true ) ;
        System.out.println() ;
        ans = boolean_print( false ) && boolean_print( true ) ;
        System.out.println() ;

        ans = boolean_print( true )  || boolean_print( true ) ;
        System.out.println() ;
        ans = boolean_print( false ) || boolean_print( true ) ;
        System.out.println() ;

        x = int_print( 0 ) & int_print( 1 ) ;
        System.out.println() ;
        x = int_print( 1 ) | int_print( 0 ) ;
        System.out.println() ;
    }
}

• 論理演算子とbit演算子の違い(Paiza.io)

2進数とビットフィールド

例えば、誕生日の年月日の情報を扱う際、20230726で、2023年7月26日を表現することも多い。

しかしこの方法は、この年月日の情報から年(4桁)、月(2桁)、日(2桁)を取り出す処理では、乗算除算が必要となる。通常のCPUであれば、簡単な乗除算は速度的にも問題はないが、組込み系では処理速度の低下も懸念される。

int ymd = 20230726 ;
int y , m , d ;
y = ymd / 10000 ;
m = ymd / 100 % 100 ;
d = ymd % 100 ;

y = 1965 ; m = 2 ; d = 7 ;
ymd = y * 10000 + m * 100 + d ;

こういった処理を扱う際には、2進数の考え方を使って扱う方法がある。
例えば、年は 0..2047 の範囲と考えれば 11 bit で表現でき、月は1..12の範囲であり 4bit で表現可能であり、日は1..31 で 5bit で表現できる。これを踏まえて、年月日を 11+4+5 = 20bit で表す(YYYY,YYYY,YYYM,MMMD,DDDD)なら、以下のプログラムのように書ける。

int ymd = (2024 << 9) + (7 << 5) + 26 ; // YYYY,YYYY,YYYM,MMMD,DDDD
int y , m , d ;                         // 1111,1101,0000,1111,1010
y = ymd >> 9 ;          // YYYYYYYYYYY
m = (ymd >> 5) & 0xF ;  // YYYYYYYYYYYMMMM & 000000000001111
d = (ymd & 0x1F) ;      // YYYYYYYYYYYMMMMDDDDD & 00000000000000011111

y = 1965 ; m = 2 ; d = 7 ;
ymd = (y << 9) + (m << 5) + d ;

C言語でのビットフィールド

しかし、上記のプログラムでは、いちいち2進数bit演算をイメージする必要があって、プログラムが分かりづらい。C言語では、こういった際にに使うのが ビットフィールドである。

// C言語の場合 (Javaではビットフィールドの構文がない)
struct YMD {
   unsigned int year  : 11 ; // ビットフィールドでは、
   unsigned int month :  4 ; // 構造体の要素を何ビットで保存するのか
   unsigned int day   :  5 ; // 指定することができる。
} ;
struct YMD ymd = { 2023 , 7 , 26 } ;
int y , m , d ;
y = ymd.year ;
m = ymd.month ;
d = ymd.day ;

ymd.year = 1965 ; ymd.month = 2 ; ymd.day = 7 ;

2進数を用いた集合計算

リストによる集合の前に、もっと簡単な集合処理を考える。

最も簡単な方法は、要素に含まれる=true か 含まれない=false を boolean型の配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に true を覚えるものとする。この方法で積集合などを記述した例を以下に示す。

import java.util.*;

public class Main {
    public static void boolarray_print( boolean[] a ) {
        for( int i = 0 ; i < a.length ; i++ )
            System.out.print( a[i] ? "T" : "F" ) ;
        System.out.println() ;
    }
    public static void boolarray_and( boolean[] ans , boolean[] a , boolean[] b ) {
        for( int i = 0 ; i < a.length ; i++ )
            ans[i] = a[i] && b[i] ;
    }
    public static void boolarray_or( boolean[] ans , boolean[] a , boolean[] b ) {
        for( int i = 0 ; i < a.length ; i++ )
            ans[i] = a[i] || b[i] ;
    }
    public static void main(String[] args) throws Exception {
        //               0      1      2      3      4      5      6      7      8      9
        boolean[] ba = { false, true,  true,  true,  false, false, false, false, false, false } ; // {1,2,3}
        boolean[] bb = { false, false, true,  false, true,  false, true,  false, false, false } ; // {2,4,6}
        boolean[] bc = { false, false, false, false, true,  false, true,  false, false, true  } ; // {4,6,9}
        boolean[] ans = new boolean[ 10 ] ;
        boolarray_print( ba ) ;
        boolarray_print( bb ) ;
        boolarray_and( ans , ba , bb ) ;
        boolarray_print( ans ) ;
        
        boolarray_print( bb ) ;
        boolarray_print( bc ) ;
        boolarray_or( ans , bb , bc ) ;
        boolarray_print( ans ) ;
    }
}
FTTTFFFFFF // ba
FFTFTFTFFF // bb
FFTFFFFFFF // ba & bb
FFTFTFTFFF // bb
FFFFTFTFFT // bc
FFTFTFTFFT // bb | bc

しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報をboolean型で保存しているが、実体は整数型で保存しているためメモリの無駄となる。

データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

2進数を用いた集合計算

扱うデータ件数が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∪ bc の計算を行う例である。

import java.util.*;

public class Main {
    static void bitfield_print( int x ) {
        for( int i = 0 ; i < 10 ; i++ )
            System.out.print( ((x & (1 << i)) != 0) ? "T" : "F" ) ;
        System.out.println() ;
    }
    public static void main(String[] args) throws Exception {
        int ba = (1 << 1) | (1 << 2) | (1 << 3) ; // {1,2,3}
        int bb = (1 << 2) | (1 << 4) | (1 << 6) ; // {2,4,6}
        int bc = (1 << 4) | (1 << 6) | (1 << 9) ; // {4,6,9}
        bitfield_print( ba ) ;
        bitfield_print( bb ) ;
        bitfield_print( ba & bb ) ;
        
        bitfield_print( bb ) ;
        bitfield_print( bc ) ;
        bitfield_print( bb | bc ) ;
    }
}

有名なものとして、エラトステネスのふるいによる素数計算を2進数を用いて記述してみる。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。

import java.util.*;

public class Main {
    static final int INT_BITS = 31 ;
    static int   prime = 0 ;
    public static void main(String[] args) throws Exception {
        // 倍数に非素数の目印をつける
        for( int i = 2 ; i <= INT_BITS ; i++ ) {
            if ( (prime & (1 << i)) == 0 ) {
                for( int j = 2 * i ; j <= INT_BITS ; j += i )
                    prime |= (1 << j) ;
            }
        }
        // 非素数の目印の無い値を出力
        for( int i = 2 ; i <= INT_BITS ; i++ ) {
            // 目印のついていない値は素数
            if ( (prime & (1 << i)) == 0 )
                System.out.println( i ) ;
        }
    }
}

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、int で 31要素、long int で 63 要素が上限となってしまう。

しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。また、今までの授業で説明してきた cons() などを使って表現すれば、簡単なプログラムでリストの処理が記述できる。

例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 両方に含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。

import java.util.*;

class ListNode {
   int      data ;
   ListNode next ;
   ListNode( int d , ListNode n ) {
       this.data = d ;
       this.next = n ;
   }
   static void print( ListNode p ) {
      for( ; p != null ; p = p.next )
         System.out.print( p.data + " " ) ;
      System.out.println() ;
   }
   static boolean find( ListNode p , int key ) {
      for( ; p != null ; p = p.next )
         if ( p.data == key )
            return true ;
      return false ;
   }
   static ListNode set_prod( ListNode a , ListNode b ) {
      ListNode ans = null ;
      for( ; a != null ; a = a.next ) {
         if ( find( b , a.data ) )
            ans = new ListNode( a.data , ans ) ;
      }
      return ans ;
   }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode b = new ListNode( 2 , new ListNode( 4 , new ListNode( 6 , null ) ) ) ;
        ListNode c = new ListNode( 4 , new ListNode( 6 , new ListNode( 9 , null ) ) ) ;
        ListNode b_and_c = ListNode.set_prod( b , c ) ;
        ListNode.print( b_and_c ) ;
    }
}

例題として、和集合、差集合などを考えてみよう。

理解確認

• 2進数を用いた集合処理は、どのように行うか？
• リスト構造を用いた集合処理は、どのように行うか？
• 積集合(A ∩ B)、和集合(A ∪ B)、差集合(A – B) の処理を記述せよ。

前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。

計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。

スタック

配列を用いたスタック

一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。

import java.util.*;

public class Main {
    static final int STACK_SIZE = 10 ;
    static int[] stack = new int[ STACK_SIZE ] ;
    static int   sp    = 0 ;
    static void push( int x ) {
        stack[ sp++ ] = x ;
    }
    static int pop() {
        return stack[ --sp ] ;
    }
    public static void main(String[] args) throws Exception {
        push( 11 ) ;
        push( 22 ) ;
        push( 33 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}

配列を使った Stack をオブジェクト指向で記述するなら、以下のように書ける。

import java.util.*;

class Stack {
    static final int STACK_SIZE = 10 ;
    int[] array ;
    int   sp ;
    Stack() {
        this.array = new int[ STACK_SIZE ] ;
        this.sp    = 0 ;
    }
    void push( int x ) {
        array[ sp++ ] = x ;
    }
    int pop() {
        return array[ --sp ] ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Stack stack = new Stack() ;
        stack.push( 11 ) ;
        stack.push( 22 ) ;
        stack.push( 33 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

C言語で書いた場合

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;

void push( int x ) { // データをスタックの一番上に積む
    stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
    return stack[ --sp ] ;
}
void main() {
    push( 1 ) ; push( 2 ) ; push( 3 ) ;
    printf( "%d\n" , pop() ) ; // 3
    printf( "%d\n" , pop() ) ; // 2
    printf( "%d\n" , pop() ) ; // 1
}

++,–の前置型と後置型の違い

// 後置インクリメント演算子
int i = 100 ;
printf( "%d" , i++ ) ;
// これは、
printf( "%d" , i ) ;
i++ ;
// と同じ。100が表示された後、101になる。

// 前置インクリメント演算子
int i = 100 ;
printf( "%d" , ++i ) ;
//   これは、
i++ ;
printf( "%d" , i ) ;
// と同じ。101になった後、101を表示。

リスト構造を用いたスタック

しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。

import java.util.*;

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

public class Main {
    static ListNode stack = null ;
    static void push( int x ) {
        stack = new ListNode( x , stack ) ;
    }
    static int pop() {
        int ans = stack.data ;
        stack = stack.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        push( 1 ) ;
        push( 2 ) ;
        push( 3 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}

struct List* stack = NULL ;

void push( int x ) { // リスト先頭に挿入
    stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
    int ans = stack->data ;
    struct List* d = stack ;
    stack = stack->next ;      // データ 0 件で pop() した場合のエラー対策は省略
    free( d ) ;
    return ans ;
}

オブジェクト指向っぽく書くならば、下記のようになるだろう。初期状態で stack = null にしておくと、stack.push() ができないので、stack の先頭には、ダミーデータを入れるようにプログラムを書くと以下のようになるだろう。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    ListNode() {   // stack初期化用のコンストラクタ
        this.data = -1 ;
        this.next = null ;
    }
    void push( int x ) {
        this.next = new ListNode( x , this.next ) ;
    }
    int pop() {
        int ans = this.next.data ;
        this.next = this.next.next ;
        return ans ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode stack = new ListNode() ; // stack初期化用のコンストラクタを使う
        stack.push( 1 ) ;
        stack.push( 2 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

キュー(QUEUE)

２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。

配列を用いたQUEUE / リングバッファ

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。

import java.util.*;

public class Main {
    static final int QUEUE_SIZE = 32 ;
    static int[] queue = new int[ QUEUE_SIZE ] ;
    static int wp = 0 ;
    static int rp = 0 ;
    static void put( int x ) {
        queue[ wp++ ] = x ;
        if ( wp >= QUEUE_SIZE ) // wp = wp % QUEUE_SIZE ; or wp = wp & (QUEUE_SIZE - 1) ;
            wp = 0 ;
    }
    static int get() {
        int ans = queue[ rp++ ] ;
        if ( rp >= QUEUE_SIZE ) // rp = rp % QUEUE_SIZE ; or rp = rp & (QUEUE_SIZE - 1) ;
            rp = 0 ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        // Your code here!
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}

#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read  pointer(読み出し用)

void put( int x ) { // 書き込んで後ろ(次)に移動
    queue[ wp++ ] = x ;
    if ( wp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
    int ans = queue[ rp++ ] ;
    if ( rp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        rp = 0 ;
    return ans ;
}
void main() {
    put( 1 ) ; put( 2 ) ; put( 3 ) ;
    printf( "%d\n" , get() ) ; // 1
    printf( "%d\n" , get() ) ; // 2
    printf( "%d\n" , get() ) ; // 3
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか？

リスト構造を用いたQUEUE

前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。

この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。

import java.util.*;

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

public class Main {
    static ListNode top = new ListNode( -1 , null ) ;
    static ListNode tail = top ;
    static void put( int x ) {
        tail.next = new ListNode( x , null ) ;
        tail = tail.next ;
    }
    static int get() {
        int ans = top.next.data ;
        top.next = top.next.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}

Javaで書かれた ListNode を用いた待ち行列のイメージ図は下記のように示される。

struct List* queue = NULL ;
struct List** tail = &queue ;

void put( int x ) { // リスト末尾に追加
    *tail = cons( x , NULL ) ;
    tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
    int ans = queue->data ;
    struct List* d = queue ;
    queue = queue->next ;
    free( d ) ;
    return ans ;
}

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。

理解確認

• 配列を用いたスタック・待ち行列は、どのような処理か？図などを用いて説明せよ。
• リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
• スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか？欠点があるか説明せよ。
• 配列を用いたリングバッファが用いられている身近な例にはどのようなものがあるか？
• 配列を用いたリングバッファを実装する場合配列サイズには 2ⁿ 個を用いることが多いのはなぜだろうか？