IPAの失態と情報処理技術者試験の今後 〜応用情報処理技術者試験 午後 問2のアルゴリズムの問題点〜

 

情報処理推進機構(IPA)主催、2009年秋期、情報処理技術者試験を解いてみた。
毎年、この時期は嫌いである。
今回はITパスポート、基本情報も含め、数多くの情報処理技術者試験を解かないといけないのだ。
とても面倒である。
そしてまた、年々受験者にゴマをするような出題をし、受験者数を稼ごうとするIPAの目論見が垣間見えるような問題が増える様子を見ることも耐え難い。

それで、応用情報技術者試験の午後問題を解いてみると、問2の問題で解きながらとても違和感を感じた。
効率的なアルゴリズムの紹介をしているのだが、どこをどう考えれば効率的なのかわからない。
最強のヒープソートを作ってまだ1年も経ってないのに関わらず、ボケてしまったのか???
IPAが効率的だというのだから効率的なのだろうと盲目的に信じて解いていくが、それでも効率的な部分をまるで見い出せない。
効率的と謳ってなければ、さほど難しい内容ではない。
けれど、解説されている文面からすると間違いのない答えと思えるのだが、効率的な要素が見当たらないため自分の導き出した答えは間違いであると判断する以外にない。
何度も繰り返し検証し、やはりIPAの求めている答えは「これ!」だろうと出した答えは、徹底的に非効率なアルゴリズムを作り上げた。
TACやiTecの速報とも同一の答えだったので、間違っているとは考えにくいが、TACやiTecでもこの非効率なアルゴリズムの指摘はなかった。

この1問の問題を解いた時点で1時間が過ぎていた。
応用情報技術者試験の午後問題は150分の中で6問を解かなければならない。
そう考えると、1問あたりに使える時間は25分である。
1問で1時間も使ってしまえば落ちるに決まっている。
つまり、今回私が受けていれば、間違いなく落ちていたはずである。

それでは、ここで、内容をしっかり検証してみよう。
当該問題はここ

方法1のアルゴリズムは発見までに12回のテキストとパターンの文字比較があり、代入処理は存在しない。

それに対し、方法2のアルゴリズムは「テキスト」と「パターン」の文字比較は8回だが、それ以前に「(1)表の作成」のための「パターン」と「チェック用パターン」の文字比較も行っている。
その処理を考えると P.length(P.length - 1)/2 回分のループ処理の中で、
 if C[k]とP[j]が等しい or C[k]と" "が等しい
という形で、2つの文字比較が存在するので、「パターン」の文字数をユニークな5文字とすると、実際の回数は最低10回、最大20回となる。
ただし、初期設定で、配列Cに" "が全て代入されていることを考えると、最低の10回というケースは存在しないので、多くの文字列比較の出現が予想され、さらに2つの代入処理という比較 以上に処理を遅くする要素も存在しているため、さらなる処理の遅延が予想される。

スキップ数の決定においても、図にもあるように、最低10回の「テキスト」と「チェック用パターン」との文字比較がここでも存在する。
さらにここでも、記載されたアルゴリズムにおいて、
 if C[k]とT[i+P.length-1]が等しい or C[k]と" "が等しい
という形で、2つの文字比較が存在するので、実際の回数は処理系にもよるが最低でも10回を必ず超える。

合計すると方法2は最低24回を超える文字比較が存在し、さらにP.lengthの2倍以上の回数の代入処理も存在することになり、効率的な照合方法とはいえない。

設問3の「テキスト」と「パターン」で実際の処理状況を検討してみる。
or演算において「最初の式が真の場合に次の式を評価しない」という演算が最小限となる処理系で考えると、
 まず、初期設定の段階で、6回の代入処理が発生する。
 次に、表の作成において、6回の文字比較と、4回の代入処理が発生する。
 文字の比較においては8回の文字比較が発生する。
 スキップ数の決定においては18回の文字比較と5回の代入処理が発生する。
合計で32回の文字比較と15回の代入処理が発生することになる。
ただし、無駄なループの制御変数への代入や演算を加えれば、それ以上の差となる。
効率的な照合どころか、とても非効率的な照合なのである。

 

それでは、実際にコードを書いてみよう。
gettime.hはここ

#include <stdio.h>
#include "gettime.h"

int p1(char *,int,char *,int);
int p2(char *,int,char *,int);

int p1(char *t,int tl,char *p,int pl){//方法1(単純な照合方法のアルゴリズム)
int i;
int j;
for(i=0;i<tl-pl+1;i++){
for(j=0;j<pl;j++){
if(t[i+j]==p[j]){
if(j==pl-1)return i+1;
}else{
break;
}
}
}
return -1;
}

int p2(char *t,int tl,char *p,int pl){//方法2(効率的な照合方法のアルゴリズム・・・らしい)
int x;
int i;
int j;
int k;
char c[30];
int d[30];
int dd;
int b=0;
int bb=0;
for(x=0;x<pl;x++){
c[x]=' ';
d[x]=pl;
}
//(1):表の作成
for(j=0;j<pl-1;j++){
for(k=0;k<=j;k++){
if(c[k]==p[j] || c[k]==' '){
c[k]=p[j];
d[k]=pl-j-1;
break;
}
}
}
//文字列を照合する
i=0;
while(i<tl-pl+1){
//(2):文字の比較
for(j=0;j<pl;j++){
if(t[i+j]==p[j]){
if(j==pl-1)return i+1;
}else{
break;
}
}
//(3):スキップ数の決定
for(k=0;k<pl;k++){
if(c[k]==t[i+pl-1] || c[k]==' '){
dd=d[k];
break;
}
}
i=i+dd;
}
return -1;
}

int main(void){
int i;
char t[]="PICKLED_PEPPER"; //テキスト
char p[]="PEP"; //パターン
int tl=strlen(t); //テキストの文字数
int pl=strlen(p); //パターンの文字数
double st; //開始時刻(Start Timeの略)
double pt; //処理時間(Processing Timeの略)

st=gettime(); //開始時刻の取得
for(i=0;i<10000000;i++){
p1(t,tl,p,pl); //プロセス1を実行
// p2(t,tl,p,pl); //プロセス2を実行
}
pt=(gettime()-st)*1000; //処理時間の計算
printf("処理時間: %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
mainのforループの中のp1が方法1で、p2が方法2のアルゴリズムを使った探索である。
試す場合はどちらかをコメントアウトして計測すればOKである。
100万回繰り返して、時間計測をした結果である。 Windows & BCCでしか検証していないが、方法1に比べ、方法2は約2倍の時間がかかる。
代入処理や比較処理は2倍以上の回数行っているので、当然の結果である。

この方法2を効率の良いアルゴリズムとして考えさせてしまったのである。
アルゴリズムがそれほど得意ではなく、違和感を感じずに解けたのなら問題はないが、アルゴリズムが得意な受験者の多くはきっと違和感を感じて時間を捨ててしまったことだろうと思われる。
アルゴリズムが得意な人ほど解けない問題なのだ。
中にはアルゴリズムが本当に苦手で解けなかった受験者もいるだろう。
その差をどう見るのだろう?
IPAはこの始末をどうつけるのだろう?
ITパスポートのように得点を水増しして合格者を増やすのか?

いずれにしても大問題である。
こんな試験を受けさせられる情報処理技術者の卵たちが可哀想である。
IPAが1日拘束するお金を支払って、アルゴリズムだけの再試験をやるくらいしか正当な再評価はできないだろう。
ただでさえ、午前を考えてもマネジメントとストラテジが40%近く入ってしまい、情報処理技術者試験というよりは経営管理・経営戦略試験というような悲惨 な状態になっているのに関わらず、肝心の情報技術の問題がこれでは失態もはなはだしい。
今後の情報処理技術者の育成をどうして行くつもりなのだろう?

応用情報技術者試験の合格発表や模範解答開示はまだ先だが、どのように対応するのか寂しく見守ることにする。

 

ここでの文章、画像、検証結果などは全てDreamHopeに著作権があります。リンクに関してはTopLink、DeepLinkともに構いませんが、全部・一部の「学術論文等許諾の不必要な引用」以外の引用に関しては禁止します。

Copyright (C) 2009 DreamHope All Rights Reserved .  Access: