組み合わせ問題の解き方(予備実験)
プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。また、課題部門や自由部門であっても、複数の条件の組み合わせの中から最良のものを選ぶといった処理も求められる。最近の学生さんは複雑な組み合わせ問題がでてくると、すぐに訳も分からず「機械学習!」とか言い出す人も多いけど、基本中の基本をきちんと理解しましょう。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。
組み合わせ問題の基礎
簡単な問題として「100未満の整数の値を3つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。
一番簡単な方法は、以下となるであろう。
#include <stdio.h> #include <math.h> #include <time.h> // 整数比の直角三角形の一覧を求める。 void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // 一番ダサい方法 for( int c = 1 ; c < n ; c++ ) { if ( a*a + b*b == c*c ) { printf( "%d %d %d\n" , a , b , c ) ; } } } } } int main() { integer_triangle( 100 ) ; return 0 ; }
import java.util.*; public class Main { static void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // 一番ダサい方法 for( int c = 1 ; c < n ; c++ ) { if ( a*a + b*b == c*c ) { System.out.println( "a="+a+",b="+b+",c="+c ) ; } } } } } public static void main(String[] args) throws Exception { // 整数比の直角三角形の一覧を求める。 integer_triangle( 100 ) ; } }
しかしこのプログラムの欠点としては、100×100×100回のループで無駄な処理が多い。
4EIの情報構造論で説明するネタだけど、こういうアルゴリズムは、O(N3) のアルゴリズムという。
ループ回数を減らすだけなら、最も内側の処理を、計算で整数値か確認すればいい。
O(N2) のアルゴリズム
void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // ココも改良できるよね? int d = a*a + b*b ; int c = (int)sqrt( d ) ; // 斜辺Cの整数値を求め、改めて確認する。 if ( c*c == d ) { printf( "%d %d %d\n" , a , b , c ) ; } } } }
static void integer_triangle( int n ) { for( int a = 1 ; a < n ; a++ ) { for( int b = 1 ; b < n ; b++ ) { // ココも改良できるよね? int d = a*a + b*b ; int c = (int)Math.sqrt( d ) ; // 斜辺Cの整数値を求め、改めて確認する。 if ( c*c == d ) { System.out.println( "a="+a+",b="+b+",c="+c ) ; } } } }
(1) 計算誤差の問題を考えてみよう。
たとえば、3:4:5の直角三角形で、3*3+4*4 = 25 だが、sqrt(25)は実数で計算するから、 計算誤差で4.99999で求まったらどうなるだろうか?
1~100までの数値で、”int c = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか? 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。
(2) 無駄な答えについて考えてみよう。
このプログラムの答えでは、簡単な整数比の答えの「整数倍の答え」も表示されてしまう。 たとえば、(3:4:5)の答えのほかに、(6:8:10)も表示される。 こういった答えを表示しないようにするにはどうすればよいか?
また、この2つのプログラムの処理時間を実際に比べてみる。
#include <stdio.h> #include <time.h> int main() { time_t start , end ; // time() 関数は、秒数しか求まらないので、 // あえて処理を1000回繰り返し、数秒かかる処理にする。 start = time( NULL ) ; for( int i = 0 ; i < 1000 ; i++ ) { // ただし、関数内のprintfをコメントアウトしておくこと integer_triangle( 100 ) ; } end = time( NULL ) ; printf( "%lf\n" , difftime( end , start ) ) ; return 0 ; }
import java.util.* ; import java.lang.System ; public class Main { static void integer_triangle( int n ) { : // System.out.println( "a="+a+",b="+b+",c="+c ) ; // 関数内のprintfをコメントアウトしておくこと : } public static void main(String[] args) throws Exception { // 整数比の直角三角形の一覧を求める。 long start = System.currentTimeMillis() ; for( int i = 0 ; i < 1000 ; i++ ) { integer_triangle( 100 ) ; } long end = System.currentTimeMillis() ; System.out.println( "time = " + end - start ) ; } }
再帰プログラミング
組み合わせ問題では、forループの多重の入れ子で問題を解けない場合が多い。 (書けないことはないけど無駄なループで処理が遅くなるか、入れ子段数が可変にできない。)
こういった場合には、再帰プログラミングがよく利用される。 もっとも簡単な再帰の例として、階乗のプログラムを考える。 通常であれば、以下のような for ループで記述することになるだろう。
// 階乗の計算 int fact( int x ) { // ループ int f = 1 ; for( int i = 2 ; i <= x ; i++ ) f = f * i ; return f ; }
再帰呼び出しでは、関数の処理の中に、自分自身の関数呼び出しが含まれる。 また、無限に自分自身を呼び出したら処理が止まらないので、 問題を一つ小さくして、これ以上小さくできないときは処理を止めるように記述する。
int fact( int x ) { // 再帰呼び出し if ( x <= 1 ) return 1 ; else return x * fact( x - 1 ) ; }
ここ以降は、指定長さを指定辺の組み合わせで作る課題と、後に述べるFlood-fill 課題の選択とする。
指定長を指定辺の組み合わせで作る(テーマ1)
再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。
配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
(例) 辺の長さ10を作るには、(5,4,1)とか(7,3)などが考えられる。
これは、ナップサック問題の基本問題で、容量の決まったナップサックに最大量入れる組合せを求めるのと同じである。
このプログラムを解くには…
10 を [4,5,2,1,3,7] で作るには... (0) 6=10-4 を [4|5,2,1,3,7]で作る。 (1) 5=10-5 を [5|4,2,1,3,7]で作る。 (2) 8=10-2 を [2|5,4,1,3,7]で作る。 (3) 9=10-1 を [1|5,2,4,3,7]で作る。 (4) 7=10-3 を [3|5,2,1,4,7]で作る。 (5) 3=10-7 を [7|5,2,1,3,4]で作る。
そこで、ここまでの考えを、以下のようなプログラムで記述してみる。
# まだ再起呼び出しにはしていない。
// 指定されたデータを入れ替える。 void swap( int*a , int*b ) { int x = *a ; *a = *b ; *b = x ; } // 配列のn番目以降を使って len の長さを作る再帰関数 void check( int array[] , int size , int len , int n ) { // array[] 配列 // size 配列サイズ // len 作りたい長さ // n 使った個数 for( int i = n ; i < size ; i++ ) { // i番目を先頭に... swap( &array[ n ] , &array[ i ] ) ; printf( "check( array , %d , %d , %d )\n" , size , len - array[ n ] , n+1 ) ; // 最初のswapでの変更を元に戻す。 swap( &array[ i ] , &array[ n ] ) ; } } int main() { int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ; check( a , 6 , 10 , 0 ) ; }
import java.util.*; public class Main { // 配列のa番目とb番目を入れ替え static void swap( int array[] , int a , int b ) { int tmp = array[ a ] ; array[ a ] = array[ b ] ; array[ b ] = tmp ; } // 配列のn番目以降を使ってlenの長さを作る再帰関数 static void check( int array[] , int len , int n ) { for( int i = n ; i < array.length ; i++ ) { swap( array , n , i ) ; for( int j = 0 ; j < array.length ; j++ ) System.out.print( array[ j ] + "," ) ; System.out.println() ; System.out.println( "check( array , " + (len - array[ n ]) + " , " + (n+1) + " ) ;" ) ; // check( array , len - array[ n ] , n + 1 ) ; swap( array , n , i ) ; } } public static void main(String[] args) throws Exception { // 指定した長さを配列の組み合わせで作る。 int array[] = { 4 , 5 , 2 , 1 , 3 , 7 } ; check( array , 10 , 0 ) ; } }
(1) これを再帰呼び出しにしてみよう。どう書けばいい?
// C言語版
void check( int array[] , int size , int len , int n )
{
// array[] 配列
// size 配列サイズ
// len 作りたい長さ
// n 使った個数
if ( len < 0 ) {
// 指定した丁度の長さを作れなかった。
;
} else if ( len == 0 ) {
// 指定した長さを作れたので答えを表示。
for( int i = 0 ; i < n ; i++ ) {
printf( "%d " , array[ i ] ) ;
}
printf( "\n" ) ;
} else {
// 問題を一つ小さくして再帰。
for( int i = n ; i < size ; i++ ) {
swap( &array[ n ] , &array[ i ] ) ;
printf( "check( array , %d , %d , %d )\n" ,
size , len - array[ n ] , n+1 ) ;
check( array , size , len - array[ n ] , n + 1 ) ;
swap( &array[ i ] , &array[ n ] ) ;
}
}
}
// Java版
static void check( int array[] , int len , int n ) {
if ( len < 0 ) {
// 指定した長さは作れなかった
;
} else if ( len == 0 ) {
for( int i = 0 ; i < n ; i++ )
System.out.print( array[ i ] + "," ) ;
System.out.println() ;
} else {
for( int i = n ; i < array.length ; i++ ) {
swap( array , n , i ) ;
//for( int j = 0 ; j < array.length ; j++ )
// System.out.print( array[ j ] + "," ) ;
// System.out.println() ;
// System.out.println( "check( array , " + (len - array[ n ]) + " , " + (n+1) + " ) ;" ) ;
check( array , len - array[ n ] , n + 1 ) ;
swap( array , n , i ) ;
}
}
}
(2) 少ない組み合わせの方がポイントが高い場合には、プログラムをどう変更する?
(3) 答えが1つだけで良い場合は、プログラムをどう変更する?
(4) このプログラムでは、冗長な答えがあるか?ないか?検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。
# レポートでは、(2),(3),(4)を検討した結果を実験すること。(5)までチャレンジした人は(2),(3),(4)の説明は簡単に記載するだけで良い。
別解
この問題の解き方には、もっとシンプルな書き方がある。2進数の各bitを、j番目の長さを使うか使わないかを表すこととする。
例えば、j=1番目,3番目を使うというのを、000101)2=5で表すこととする。すべての長さを使うのであれば、111111)2=63 で表す。この2進数を1から63まで変化させれば、すべての組み合わせを試すことになる。
#include <stdio.h> #define sizeofarray(A) (sizeof(A)/sizeof(A[0])) int obj_len = 10 ; int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ; int main() { int l_max = 1 << sizeofarray( a ) ; for( int i = 1 ; i < l_max ; i++ ) { // i は a[j]を使うか使わないかを表す2進数 // i = 5 の場合 // 5 = 0,0,0,1,0,1 // a[] 7,3,1,2,5,4 // ^ ^ = 長さは6 int sum = 0 ; for( int j = 0 ; j < sizeofarray( a ) ; j++ ) { // iの2進数の各bitに対応する長さを加算 if ( (i & (1 << j)) != 0 ) sum += a[ j ] ; } // 目的の長さを作れたので答えを表示 if ( sum == obj_len ) { printf( "0x%x : " , i ) ; for( int j = 0 ; j < sizeofarray( a ) ; j++ ) { if ( (i & (1 << j)) != 0 ) { printf( "%d " , a[ j ] ) ; } } printf( "\n" ) ; } } return 0 ; }
import java.util.*; public class Main { public static void main(String[] args) throws Exception { // 整数比の直角三角形の一覧を求める。 int array[] = { 4 , 5 , 2 , 1 , 3 , 7 } ; int obj_len = 10 ; int l_max = 1 << array.length ; for( int i = 1 ; i < l_max ; i++ ) { int sum = 0 ; for( int j = 0 ; j < array.length ; j++ ) { if ( (i & (1 << j)) != 0 ) sum += array[ j ] ; } if ( sum == obj_len ) { System.out.println( Integer.toBinaryString( i ) ) ; for( int j = 0 ; j < array.length ; j++ ) { if ( (i & (1 << j)) != 0 ) { System.out.print( array[ j ] + "," ) ; } } System.out.println() ; } } } }
このプログラムは再帰呼び出しを含まないので、プログラムの挙動も解りやすい。しかし、j番目を使うか使わないのか…という2つの状態しかない組み合わせ問題でしか使えない。R3年度の競技部門のパズルように、絵のピースの↑,→,↓,←,回転右,回転左という6状態の場合は、使えない。
Flood fill アルゴリズム
再帰を使う他の事例として、図形の塗りつぶし問題で示す。(Wikipedia Flood-fill参照)
以下の image のような2次元配列が与えられたら、指定座標(x,y)を中心に周囲を塗りつぶす処理を作成せよ。
include <stdio.h> // *は壁 SPCは白 この領域の指定位置を#で塗りつぶす。 char image1[10][10] = { // (4,4)始点で塗りつぶし後 "*********" , // ********* "* * *" , // * *###* "* * *" , // * *###* "* * *" , // * *####* "*** ***" , // ***###*** "* * *" , // *####* * "* * *" , // *###* * "* * *" , // *###* * "*********" , // ********* } ; char image2[10][10] = { // 応用問題用の画像例 "*********" , // * のような隙間は通り抜けられる "* * *" , // * ようにするにはどうすればいい? "* ** *" , // ** "* ** *" , // ** これは通り抜けられない "*** ***" , // ** "* * *" , "* * *" , "* * *" , "*********" , } ; // 盤面を表示 void print_image( char image[10][10] ) { for( int y = 0 ; y < 9 ; y++ ) { for( int x = 0 ; x < 9 ; x++ ) { printf( "%c" , image[y][x] ) ; } printf( "\n" ) ; } } // 再帰呼び出しを使った flud_fill アルゴリズム void flood_fill( char image[10][10] , int x , int y , char fill ) { // image: 塗りつぶす画像 // x,y: 塗りつぶす場所 // fill: 書き込む文字 // 指定座標が空白なら if ( image[y][x] == ' ' ) { // その座標を埋める image[y][x] = fill ; ////////////////////////////////////// // ここに周囲をflud_fillする処理を書く // ////////////////////////////////////// } } int main() { print_image( image1 ) ; flood_fill( image1 , 4 , 4 , '#' ) ; print_image( image1 ) ; return 0 ; }
import java.util.*; public class Main { // 文字列の要素を2次元配列に格納 static void set_char2_string( char dest[][] , String src[] ) { for( int i = 0 ; i < src.length ; i++ ) { dest[ i ] = new char[ src[ i ].length() ] ; for( int j = 0 ; j < src[ i ].length() ; j++ ) dest[ i ][ j ] = src[ i ].charAt( j ) ; } } // 2次元配列を出力 static void print_image( char image[][] ) { for( int i = 0 ; i < image.length ; i++ ) { for( int j = 0 ; j < image[ i ].length ; j++ ) System.out.print( image[ i ][ j ] ) ; System.out.println() ; } } // flood_fill static void flood_fill( char image[][] , int x , int y , char fill ) { if ( image[y][x] == ' ' ) { image[y][x] = fill ; // ここを考える } } public static void main(String[] args) throws Exception { // Your code here! String imageS1[] = { "*********" , "* * *" , "* * *" , "* * *" , "*** ***" , "* * *" , "* * *" , "* * *" , "*********" , } ; char[][] image1 = new char[ imageS1.length ][] ; set_char2_string( image1 , imageS1 ) ; String imageS2[] = { "*********" , "* * *" , "* ** *" , "* ** *" , "*** ***" , "* * *" , "* * *" , "* * *" , "*********" , } ; char[][] image2 = new char[ imageS2.length ][] ; set_char2_string( image2 , imageS2 ) ; // flood_fill 実行 print_image( image1 ) ; flood_fill( image1 , 4 , 4 , '#' ) ; print_image( image1 ) ; } }
応用問題
Wikipediaのflood-fill のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。
そこで、斜めに並んだブロックは通り抜けられるルールとした場合のプログラムを記述せよ。
レポート提出
レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。
-
- レポートの説明(自分の選んだテーマと自分なりの説明)
- プログラムリスト
- 動作確認の結果
情報メディア工学・ガイダンス/2024
情報メディア工学では、前期では情報を扱うためのOSの仕組みなどを、実践を交えながら演習を中心に行う。後期は5年の人工知能の授業につながる内容として、情報の中のデータをどう処理するのかを議論する。
OSの役割と仕組み
組込み系システム
組込み系のシステムで、OSが無い場合(例えば Arduino でデバイスを制御する場合)には、ユーザプログラムはデバイスを操作するライブラリやI/Oポートを直接制御しながら、ハードウェアを制御する。ユーザプログラムは、デバイスを操作するライブラリを含むため、異なるシステムでは機械語をそのまま使うことはできない。(共通化が不十分)
組込み系システムでは、ハードウェアを操作する命令をすべてユーザプログラムが面倒を見る必要があるため、システムが複雑化するとプログラム開発が大変になってくる。また、ユーザプログラムが間違った制御方法を取れば、ハードウェアを壊すような処理を実行してしまうかもしれない。(資源保護ができない)
オペレーティングシステム経由でハード操作
コンピュータのハードウェアの違いは OS がすべて包み隠し、OSが管理する。OSは 特権モード で動作し、ハードウェアを直接制御する。ユーザプログラムはユーザモードで動作し、OSの機能を呼び出すシステムコールを経由し、デバイス毎のデバイスドライバを経由して、ハードウェアを操作する。ユーザモードのプログラムは、ハードウェアを直接操作するような命令を実行しようとすると、OSが命令を強制停止させる。(資源保護)
ユーザプログラムには、ハードウェアを直接操作する機械語が含まれていないので、ユーザプログラムの機械語を同じOSが動く他のコンピュータにコピーして動かすことができる。(資源の扱いを共通化)
(例) helloworld のプログラムがコンソールに出力
簡単な例として、helloworld.c のような簡単なコンソール出力プログラムが動いて、画面に文字が表示されるのは以下の図のようにOSを経由して文字を表示している。
古いコンピュータで、プログラムが動作するだけならば、仕組みはすごく簡単にみえる。ユーザプログラムはすべて特権モードで動くOS(狭義のOSとかカーネルと呼ぶことが多い)を経由してハードウェアを操作する。
GUI が使えるグラフィカルな OS の場合
GUI が使えるグラフィカルなOSの場合、GUI の操作を支援するプログラム(ウィンドウマネージャ)などを利用しながら、ユーザはOSを操作する。コンピュータを操作する場合は、こういうウィンドウマネージャなどがないと不便であり、カーネルとユーザ支援のウィンドウマネージャなどをまとめて広義のOSと呼ぶ場合も多い。
ユーザプログラムは、GUIを操作するためのライブラリを経由し、さらにカーネルを経由してディスプレィに結果が表示される。
ユーザモードのプログラムの実行単位プロセスでは、処理を実行するためのメモリなどは他の処理と分離されており、他のプロセスのメモリ領域などを間違ってアクセスすると「メモリエラー」といった例外などが発生し、処理が強制的に停止させられる。このように、プロセスが他に悪影響を及ぼさないように、OS はメモリを管理する。(OSの保護機能)
(例) helloworld の結果を端末ソフトで表示
以下のように、コンソールアプリの実行結果を表示するような、cmd.exe は、helloworld.exe と OS を経由しながら連動して動いている。
helloworld.exe の出力は、OS を経由しながら cmd.exe に伝わり、cmd.exe はその表示内容に応じて、テキストの文字やフォントに合わせてグラフィカルな画面に文字を表示しようとする。グラフィカルな出力は GUI のライブラリを経由しながら OS に送られ、グラフィックドライバが画面に文字を表示する。
インターネットとプログラム
次に、インターネットの仕組みを踏まえ、インターネットで使われるプログラム言語やデータについて3~4週をかけて演習を中心にしながら、今まで習ってきたことを総括する。
理解確認
情報構造論ガイダンス2024
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか? ※1
- ここまでの段階で3つの要点を考えメモしてください。
具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。
- プログラムの速度
- プログラムのわかり易さ
- メモリの使用量
プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。
メモリの使用量の影響
メモリを大量に使用すると、どういった影響がでるのか? OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)
しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)
int 型のメモリ使用量は?
int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。
32bit の0/1情報の組み合わせで、232通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-231~0~231-1 の範囲を扱うことができる。231 = 2×210×210×210 ≒ 2×10003
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が決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ?ゲームがバグですぐに変な動きしたらキレるでしょ!(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
サーバ移行作業で2015年以前のテスト問題が消えた
サーバの移行作業を行ったけど、その際に自分のホームディレクトリ配下に置いてあった、過去のテスト問題のデータが消えた。エビデンス用に学校で保管してあるデータからコピーして、2015年以降は復活できたけど。
hilite=nslookup/// って何?
なにげなく、WordPress な Web の accesslog を見ていたら、下記のようなログが大量(8000件/日越え)に残ってる。
3.224.220.101 - - [07/Mar/2024:09:17:32 +0900] "GET /2019/09/27/hoge-meta/?hilite=nslookup//////////...(略)...//// HTTP/1.1" 200 19136 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_1) AppleWebKit/600.2.5 (KHTML, like Gecko) Version/8.0.2 Safari/600.2.5 (Amazonbot/0.1; +https://developer.amazon.com/support/amazonbot)"
hilite=… は、WordPress の検索プラグインが使うパラメータ WordPressで記事の特定部分を目立たせる際のパラメータ。大量の////が並ぶので、プラグインへのバッファオーバーフロー攻撃かと思うけど、ググってもそういった類の報告は見つからない。
amazonbot というのがユーザエージェントに残ってるし、確認するとどのユーザエージェントも amazonbot 。IPアドレスも散らばっているけど、逆引きすると amazonbot のアドレス。クローラーが暴走してるのかな。意味不明で不気味。
(追記)
確認を続けると、数日前の LOG だと、/// の長さがちょっと短い。さらにさかのぼっていくと次第に短くなっている。hilite=nslookup が出てきた最初は、下記の通り。この段階では “/” はナシだな。
xx.xx.xx.xx - - [29/Feb/2024:07:00:01 +0900] "GET /2023/11/16/network-layer-ip-address-2023/?hilite=nslookup HTTP/1.1" 200 19165 "-" "Mozilla/5.0 (compatible; AhrefsBot/7.0; +http://ahrefs.com/robot/)" xx.xx.xx.xx - - [29/Feb/2024:12:42:46 +0900] "GET /2023/11/16/network-layer-ip-address-2023/?hilite=nslookup HTTP/1.1" 200 70965 "-" "ICC-Crawler/2.0 (Mozilla-compatible; ; http://ucri.nict.go.jp/en/icccrawler.html)"
該当記事をみると、講義録の nslookup を目立たせるために、?hilite=nslookup で自分の記事にリンク張ってる。こんなもんで、変なアクセスが増えてるの?どっちにしろ、クローラーのバグっぽいな。
となると、amazonbot のクローラー禁止するか。
((( robots.txt ))) User-agent: Amazonbot Disallow: /
2023年度 情報構造論 講義録
- 情報構造論ガイダンス2023
- 繰り返し処理と処理時間の見積もり
- 再帰呼び出しと処理時間の見積もり
- ポインタ処理
- ポインタとメモリの使用効率
- malloc()とfree()
- 様々なデータの覚え方のレポート課題
- fgetsではみ出たら
- リスト構造の導入
- リスト処理
- リストへの追加処理
- スタックと待ち行列
- 集合とリスト処理
- ランダムアクセス・シーケンシャルアクセスから双方向リスト
- 双方向リストとdeque
- 2分探索木
- AVL木と2分ヒープ
- 意思決定木と演算子
- 2分木による構文木とデータベースとB木
- コンパイラと正規表現とBNF記法
- ハッシュ法
- チェイン法と共有のあるデータの問題
- 参照カウンタの問題とガベージコレクタ
- 関数ポインタ