ホーム » 2022 » 7月 » 25

日別アーカイブ: 2022年7月25日

2022年7月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最新の投稿(電子情報)

アーカイブ

カテゴリー

集合とリスト処理

リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。集合処理の記述には、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 は  と同じ
#include <stdio.h>

int main() {
   // bit演算子と論理演算子
   printf( "%d¥n" , 12 &  5 ) ;  // 1100 & 0101 = 0100 よって 4が表示される
   printf( "%d¥n" , 12 && 0 ) ;  // 0が表示 論理演算子とbit演算子の違い
   printf( "%d¥n" , 12 |  5 ) ;  // 1100 | 0101 = 1101 よって 13が表示される
   printf( "%d¥n" , 12 || 0 ) ;  // 1が表示 
   // シフト演算子
   printf( "%d¥n" ,  3 << 2 ) ;  // 12が表示
   printf( "%d¥n" , 12 >> 2 ) ;  // 3が表示
   // おまけ
   printf( "%d¥n" , ~(unsigned)12 + 1 ) ;  // 2の補数(NOT 12 + 1) = -12
   return 0 ;
}

2進数を用いた集合計算

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

最も簡単な方法は、要素に含まれる=1 か 含まれない=0 を配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に1を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、自分で考える練習として穴埋めを含むので注意。

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

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

2進数を用いた集合計算

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

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

// 符号なし整数を uint_t とする。
typedef unsigned int uint_t ;

// uint_tのbit数
#define UINT_BITS (sizeof( uint_t ) * 8)

// 集合の内容を表示
void bit_print( uint_t x ) {
   for( int i = 0 ; i < UINT_BITS ; i++ )
      if ( (x & (1 << i)) != 0 )
         printf( "%d " , i ) ;
   printf( "\n" ) ;
}
void main() {     // 98,7654,3210
   // ba = {1,2,3} = 00,0000,1110
   uint_t ba = (1<<1) | (1<<2) | (1<<3) ;
   // bb = {2,4,6} = 00,0101,0100
   uint_t bb = (1<<2) | (1<<4) | (1<<6) ;
   // bc = {4,6,9} = 10,0101,0000
   uint_t bc = (1<<4) | (1<<6) | (1<<9) ;

   // 集合積(bit AND)
   bit_print( ba & bb ) ; // ba ∩ bb = {2}                 
   bit_print( bb & bc ) ; // bb ∩ bc = {4,6}
   // 集合和(bit OR)
   bit_print( ba | bc ) ; // ba ∪ bc = {1,2,3,4,6,9}
}

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

uint_t prime = 0 ; // 初期値=すべての数は素数とする。

void filter() {
   // 倍数に非素数の目印をつける
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      if ( (prime & (1 << i)) == 0 ) {
         // iの倍数には、非素数の目印(1)をつける
         for( int j = 2*i ; j < UINT_BITS ; j += i )
            prime |= (1 << j) ;
      }
   }
   // 非素数の目印の無い値を出力
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      // 目印のついていない数は素数
      if ( (prime & (1 << i)) == 0 )
         printf( "%d\n" , i ) ;
   }
}

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)

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

// 先週までに説明してきたリスト構造と補助関数
struct List {
   int     data ;
   struct List* next ;
} ;
struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next ) {
      printf( "%d " , p->data ) ;
   }
   printf( "\n" ) ;
}
int find( struct List* p , int key ) {
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return 1 ;
   return 0 ;
}

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

// 集合積の計算
struct List* set_prod( struct List* a , struct List* b ) {
   struct List* ans = NULL ;
   for( ; a != NULL ; a = a->next ) {
      // aの要素がbにも含まれていたら、ansに加える
      if ( find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   }
   return ans ;
}
void main() {
   struct List* a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
   struct List* b = cons( 2, cons( 4, cons( 6, NULL ) ) ) ;
   struct List* c = cons( 4, cons( 6, cons( 9, NULL ) ) ) ;
   print( set_prod( a , b ) ) ;
   print( set_prod( b , c ) ) ;
}

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

リストの共有と削除の問題

リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。リストの全要素を捨てる処理であれば、以下のようになるであろう。

void list_free( struct List* p ) {
   while( p != NULL ) {
      struct List* d = p ;
      p = p->next ;
      free( d ) ; // 順序に注意
   }
}

一方、前説明の和集合(a ∪ b)のプログラムを以下のように作った場合、list_freeの処理は問題となる。

// 集合和
struct List* set_union( struct List*a, struct List*b ) {
   struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
void main() {
   struct List*a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
   struct List*b = cons( 2, cons( 3, cons( 4, NULL ) ) ) ;
   struct List*c = set_union( a , b ) ;
   // a,b,cを使った処理
   // 処理が終わったので、a,b,cを捨てる
   list_free( a ) ;
   list_free( b ) ;
   list_free( c ) ;
   // c = { 1 , (bのリスト) }
   // (b)の部分は先のlist_free(b)で解放済み
}

このような、リストb,リストcで共有されている部分があると、データの廃棄処理をどのように記述すべきなのか、問題となる。

これらの解決方法としては、(1) set_union() の最初で、ans=b となっている部分を別にコピーしておく、(2) 参照カウンタ法を用いる、(3) ガベージコレクタのある言語を用いる…などがある。(2),(3)は後期授業で改めて解説を行う。

// 同じ要素を含む、新しいリストを作る
struct List* copy( struct List*p ) {
   struct List*ans = NULL ;
   for( ; p != NULL ; p = p->next )
      ans = cons( p->data , ans ) ;
   return ans ;
}
struct List* set_union( struct List*a, struct List* b ) {
   struct List* ans = copy( b ) ;
   // この後は自分で考えよう。
}

理解確認

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

プログラムのバージョン管理とオープンソース

プログラムを複数人で開発する場合のバージョン管理と、オープンソースプログラムを使う場合の注意を説明する。

バージョン管理システム

プログラムを学校や自宅のパソコンで開発する場合、そのソースコードはどのように持ち運び管理修正すべきだろうか?

最も原始的な方法は、常に全部を持ち歩く方法かもしれない。

  • 同期方式 – 2つのディレクトリのファイルの古い日付のファイルを、新しい日付のファイルで上書きするようなディレクトリ同期ソフトを使って管理
  • 圧縮保管 – ファイル全体だと容量も多いため、複数のファイルを1つのファイルにまとめて圧縮を行う tar コマンドを使うことも多い。(tar ball管理)

diffとpatch

プログラムの修正を記録し、必要最小限で修正箇所の情報を共有する方式に patch がある。これには、2つのファイルの差異を表示する diff コマンドの出力結果(通称patch)を用る。diff コマンドでは、変更のある場所の前後数行の差異を !(入替) +(追加) -(削除) の目印をつけて出力する。patch コマンドに diff の出力を与えると、!,+,- の情報を元に修正を加えることができる。(通称「patchをあてる」)

((( helloworld-old.c )))
  #include <stdio.h>

  void main() {
        printf( "Hello World\n" ) ;
  }
 
((( helloworld.c )))
  #include <stdio.h>

  int main( void ) {
        printf( "Hello World\n" ) ;
        return 0 ;
  }
 
((( diff の実行 )))
$ diff -c helloworld-old.c helloworld.c
 
((( 生成された patch 情報 )))
*** helloworld-old.c    2022-07-25 10:09:10.694442400 +0900
--- helloworld.c        2022-07-25 10:09:26.136433100 +0900
***************
*** 1,5 ****
  #include <stdio.h>

! void main() {
        printf( "Hello World\n" ) ;
  }
--- 1,6 ----
  #include <stdio.h>

! int main( void ) {
        printf( "Hello World\n" ) ;
+       return 0 ;
  }

インターネットの初期の頃には、他の人のプログラムに対して間違いを見つけると、作者に対してこのpatch(diff出力)をメールなどで送付し、プログラムの修正が行われた。

広く世界で使われている Web サーバ apache は、オープンソースで開発されてきた。当初はプログラム公開後に間違いや機能追加の情報(patch)が世界中のボランティア開発者から送られてきながら改良が加えられていった。このため、”a too many patches”「つぎはぎだらけ」という皮肉を込めて apache と名付けられたと言われている。

初期のバージョン管理システム

バージョン管理システムは、複数人で少しづつテキストファイルに修正を加えながら改良を行うような際に、誰がどのような修正を行ったかという修正履歴を管理するためのツール。unix などのプログラム管理では rcs (revision control system) が使われていたがその改良版として cvs (concurrent version system) が使われていた。現在は後に紹介する Git などを使うようになった。

  • ci コマンド(check in) – ファイルをバージョン管理の対象として登録する。
  • co コマンド(check out) – ファイルを編集対象とする(必要に応じて書き込みロックなども可能)。co されたファイルは、編集した人が ci して戻すまで ci することができない。
  • 修正結果を ci する際には、新しい編集のバージョン番号などをつけて保存される。
  • co コマンドでは、バージョン番号を指定してファイルを取り出すことも可能。
                 [Bさんの修正]
                /check out \check in
ファイルver1.0-----→ver1.1------→ver1.2
     \check out  /check in
      [Aさんの修正]

集中管理型バージョン管理システム

rcs,cvs では、ファイルのバージョンは各ファイルを対象としているため、ファイルやディレクトリの移動や削除は管理が困難であった。これらの問題を解決するために、集中管理を行うサーバを基点として、対象ファイルのディレクトリ全体(ソースツリー)に対してバージョン番号を振って管理を行う。subversion はサーバに ssh などのネットワークコマンドを介して、保存・改変を行うことができる。

しかし、複数の人の修正のマージ作業の処理効率が悪く、処理速度が遅いため使われなくなっていった。同様のバージョン管理システムが企業により有償開発されていた(BitKeeperなど)が製品のライセンス問題が発生し、業を煮やした Linux 開発の Linus が Git のベースを開発・公開している。

分散型バージョン管理システム

Gitは、プログラムのソースコードなどの変更履歴を記録・追跡するための分散型バージョン管理システムである。Linus によって開発され、ほかの多くのプロジェクトで採用されている。(以下wikipedia記事を抜粋加筆)

Gitは分散型のソースコード管理システムであるため、リモートサーバ等にある中心リポジトリの完全なコピーを手元(ローカル環境)に作成して、そのローカルリポジトリを使って作業を行う。

一般的な開発スタイルでは、大雑把に言えば、以下のようなステップの繰り返しで作業が行なわれる:

  1. git clone – リモートサーバ等にある中心リポジトリをローカルに複製する。
  2. git commit – ローカルでコンテンツの修正・追加・削除を行い、ローカルリポジトリに変更履歴を記録する。
    • 必要に応じて過去の状態の閲覧や復元などを行う。場合によってはこのステップを何度か繰り返す。
  3. git push – ローカルの変更内容を中心リポジトリに反映させる。
  4. git merge – git push の段階で、作業者ごとの変更内容が衝突することもある。Gitが自動で解決できる場合もあれば、手動での解決する。
  5. git pull – 更新された中心リポジトリ(他者の作業内容も統合されている)をローカルの複製にも反映する。これによりローカル環境のコードも最新の内容になるので、改めてステップ2の作業を行う。
  ローカルリポジトリ(Aさん)
           ver1.0a1      ver1.0a2          ver1.1a1
       修正--(git commit)--修正--(git commit)      修正--(git commit)
      /git clone              \git pushgit pull Bさんの修正
中心リポジトリver1.0-----------------ver1.1       も含まれる
      \git clone              /git push
       修正--(git commit)--修正--(git commit)   編集の衝突が発生すると 
           ver1.0b1      ver1.0b2     git merge が必要かも
  ローカルリポジトリ(Bさん)

GitHub

Git での中心リポジトリを保存・管理(ホスティング)するためのソフトウェア開発のプラットフォーム。コードの管理には Git を利用し GitHub 社によって保守されている。2018年よりマイクロソフトの傘下企業となっている。

GitHub では単なるホスティングだけでなく、プルリクエストやWiki機能(ドキュメントの編集・閲覧機能)といった、開発をスムーズに行うための機能も豊富である。(個人的な例:github.com/tohrusaitoh/)

GitHub で管理されているリポジトリには、公開リポジトリ非公開リポジトリがあり、非公開リポジトリはその管理者からの招待をうけないとリポジトリ改変に参加できない。

企業でのプログラム開発で GitHub を内々で使っている事例なども多いが、間違って公開リポジトリと設定されていて企業の開発中のプログラムが漏洩してしまった…との事例もあるので、企業での利用では注意が必要。

オープンソースとライセンス

オープンソースプログラムは、プログラムのソースコードをインターネットで公開されたものである。しかし、元となったプログラムの開発者がその利用に対していくつかの制約を決めていることが多い。これらのオープンソースプログラムでのソフトウェア開発手法の概念として「伽藍とバザール」を紹介する。

伽藍とバザール

伽藍(がらん)とは、優美で壮大な寺院のことであり、その設計・開発は、優れた設計・優れた技術者により作られた完璧な実装を意味している。バザールは有象無象の人の集まりの中で作られていくものを意味している。

たとえば、伽藍方式の代表格である Microsoft の製品は、優秀なプロダクトだが、中身の設計情報などを普通の人は見ることはできない。このため潜在的なバグが見つかりにくいと言われている。

これに対しバザール方式では明確な方針が決められないまま、インターネットで公開されているプログラムをボランティアを中心とした開発者を中心に開発していく手法である。

代表格の Linux は、インターネット上にソースコードが公開され、誰もがソースコードに触れプログラムを改良してもいい(オープンソース)。その中で、新しい便利な機能を追加しインターネットに公開されれば、良いコードは生き残り、悪いコードは自然淘汰されていく。このオープンソースを支えているツールとしては、前に述べた git が有名。

オープンソース・ライセンス

ソースコードを公開している開発者の多くは、ソフトウェア開発が公開することで発展することを期待する一方で、乱用をふせぐために何らかの制約をつけていることが多い。最初の頃は、開発者に敬意を示す意味で、プログラムのソースコードに開発者の名前を残すこと、プログラムを起動した時に開発者の名前が参照できること…といった条件の場合もあったが、最近ではソフトウェアが広く普及・発展することを願って条件をつけることも多い。

こういったオープンライセンスの元となったのは、Emacs(エディタ),gcc(コンパイラ)の開発者のストールマンであり、「ユーザーが自由にソフトウェアを実行し、(コピーや配布により)共有し、研究し、そして修正するための権利に基づいたソフトウェアを開発し提供することにより、ユーザーにそのような自由な権利を与えた上でコンピュータやコンピューティングデバイスの制御をユーザーに与えること」を目標に掲げた GNU プロジェクトがある。linux を触る際のコマンドで、g で始まるプログラムの多くは GNU プロジェクトのソフトウェア。

GNU プロジェクトが掲げる GNU ライセンス(GPL)では、GPLが適用されていれば、改良したソフトウェアはインターネットに公開する義務を引き継ぐ。オープンソースライセンスとして公開の義務の範囲の違いにより、BSD ライセンスApacheライセンスなどがある。

コピーレフト型 GNU ライセンス(GPL) 改変したソースコードは公開義務,
組み合わせて利用では対応箇所の開示が必要。
準コピーレフト型 LGPL, Mozilla Public License 改変したソースコードは公開義務。
非コピーレフト型 BSDライセンス
Apacheライセンス
ソースコードを改変しても公開しなくてもいい。

GPLライセンス違反

GPLライセンスのソフトウェアを組み込んで製品を開発した場合に、ソースコード開示を行わないとGPL違反となる。大企業でこういったGPL違反が発生すると、大きな風評被害による損害をもたらす場合がある。

最近のライセンスが関連する話題を1つ紹介:GitHub を使った AI プログラミング機能「Copilot」というサービスが提供されている。Copilot のプラグインをインストールした vscode(エディタ) では、編集している関数名や変数名などの情報と GitHub で公開されているプログラムの 学習結果を使って、関数名を数文字タイプするだけで関数名・引数・処理内容などの候補を表示してくれる。しかし、Copilot を使うと非オープンライセンスで開発していたプログラムにオープンソースの処理が紛れ込む可能性があり、非オープンソースプロジェクトが GPL で訴えられる可能性を心配し「Copilot は使うべきでない」という意見の開発者も出ている。

理解度確認