国家試験終わりました！
どうも！わくばです！
随分長らく放置してしまいましたが、無事医師国家試験終了しました！
しばらく卒業旅行などいろいろあって記事を書くのが遅れてしまいました。
結果は必修92%, 一般臨床82%といった感じです！
合格ラインは必修80%, 一般臨床70%が通例ですので、確実に合格と言って差し支えないレベルです。
プログラミングにかまけてたせいで、去年の秋頃の段階だと成績かなりやばかったんですが、最後まで追い込んだ甲斐がありました。
今年はやはりコロナの蔓延もあって、受験の可否も気にしなきゃならずストレスでした_(:3」∠)_
また試験内容も、現場の医師不足を反映してるのかわかりませんが、かなり実臨床的な知識や判断を問う問題が多かったように感じます。
最終的な難易度は変わらなかったようですが、微妙な判断を問うてきたので、解いていて確信の持てる問題は少なかったですね。2日あったので最後まで不安がつきまといました。
まぁもう終わったことなので気にしないですけど！笑
これから引っ越しとか、医籍登録とか事務的なものがたくさんありますが、もう国試みたいな一大イベントはないので、またコソコソとプログラミングを再開したいと思います。笑
当面はまず今手掛けてるWebサイトのローンチを目標にします。ワンオペで実装してるのでぶっちゃけしんどいですが、コードを書くことを楽しみながらやってきたいと思います。
では。
【アルゴリズム(JS実装)】Boyer Moore Algorithm
どうも、わくばです！
最近は周りも国試を意識し始めて、少し焦りを感じてきました(笑)
Webサービスの開発もありますし、新入生も入ってきたし、なんか気持ち的にもかなり追い込まれてました（笑）
うまく両立していけるようにしないとです。
近況報告はこの辺にして、今回はBoyer Moore法を記事にしてみます。
まず言葉の整理をしておくと、テキストというのは検索対象の文字列、パターンは検索したい文字列を指します。例えばABCDEFGの中からDEFの文字列を検索する場合、ABCDEFGをテキスト、DEFをパターンと呼ぶことにします。
このアルゴリズムを理解する上でポイントとなるのは、ずらしテーブル(以下のコードにおいてはbadCharHeuristic関数が作成する配列のこと)の理解です。ずらしテーブルというのは簡単に言うと、テキストとパターンを比較していくなかでミスマッチが生じたとき、どのくらいシフトさせるかを定めた配列のことです。
ずらしテーブルの意味については以下の動画が非常にわかりやすいのでぜひ参考にしてみてください。
以下がずらしテーブルを作成するコードです。
const badCharHeuristic = string => { /* 今回はアルファベットしか使わないので 26文字ぶんの配列にしています。 */ const result = Array(26).fill(-1); const strArr = string.split('') for (let i = 0; i < strArr.length; i++) { /* -97はaの文字コードを0スタートにするため result配列のアルファベットの位置に、 pattern文字列におけるindexを入れる たとえばABGFというpattern文字列の場合は [0, 1, -1, -1, -1, 3 , 2, -1, -1, ...-1が続く] となる */ result[strArr[i].charCodeAt() - 97] = i } return result; } console.log('avdgksg', badCharHeuristic('avdgksg')) /* avdgksg [ 0, -1, -1, 2, -1, -1, 6, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, 5, -1, -1, 1, -1, -1, -1, -1 ] */
同じ文字が出てきた場合はあとに出現した文字の位置をもとにテーブルを作成しています。このavdgksgパターンのずらしテーブルが意味するところは、たとえば文字sでミスマッチが生じた場合はavdgksgのindex5の位置まで戻すということです。
次に実際に検索するコードです。
const boyerMooreSearch = (text, pattern) => { const result = []; const tl = text.length, pl = pattern.length; //ずらしテーブル作成 const badChar = badCharHeuristic(pattern, pl); let shift = 0; while (shift <= tl - pl) { //tailはpattern文字列の後ろから比較していくときのカーソル tail = pl - 1; /* textとpatternをpatternの末尾から比較していって ミスマッチが生じたらずらしターブルを参照してshiftを動かす 全部マッチしたらtailは0未満まで行く */ while ( tail >= 0 && pattern[tail] === text[shift + tail]) { tail --; } if (tail < 0) { /* tailが0未満までいってたら全部マッチなのでresultに追加して patternをまるごとずらす */ result.push(shift); shift += pl } else { //途中でミスマッチがでたらずらしテーブルに則してずらす。 shift += Math.max(1, tail - badChar[text[shift + tail].charCodeAt() - 97]); } } return result; } console.log(boyerMooreSearch('abcddaabcdbbdcavbcdddbaccabcdcbddc', 'abcd')) //[ 0, 6, 25 ]
最良のケースの時間計算量は\(O(テキストの長さ/パターンの長さ)\)になります。最良であればパターン文字列ぶんまるまるずらすからですね。
今回は以上です。誤植は質問等ありましたらお気軽にコメントください。では。
E資格合格！〜計120時間で合格した方法〜
どうも、わくばです。
E資格合格できました！
その結果と感想、僕がとった勉強方法をお話できればと思います
-
結果
得点は7割でした。笑 ギリギリ、、、
普通に難しかったです。僕の勉強が実装はほぼせず、JDLA認定講座とE資格黒本を一周した程度だったので、深いところに踏み込まれるとかなりしんどかったですね、、、
得点はかなり低いんですが、この間に6年生への進級試験やアプリ開発の勉強など並行していたりしていて、勉強時間などを加味するとかなり必要最低限でコスパ高く合格できたのではないかと思います。その点で参考にはなるかなと。
-
勉強方法と期間
勉強時間は合計120時間で、1日2時間勉強できると仮定するただいたい2ヶ月間勉強したことになります。スタプラで毎日必ず記録してるので正確な数字だと思います。
使った教材は以下です
- ゼロから作るDeepLearning①
- ゼロから作るDeepLearning②
- 徹底攻略ディープラーニングE資格エンジニア問題集
- AIジョブカレのJDLA認定講座(ディープラーニング講座のみ)
上の書籍3冊は1周ずつで、JDLA認定講座は2周しました。
数学などの勉強はE資格黒本に則って調べながら必要最低限勉強しました。
意識したことはあんまりいくつも書籍を使わないようにということです。時間がないのと、消化不良を起こすことがわかりきっているからです。
僕は手を動かしてコードを書くより、とりあえず読み進めて範囲を網羅していったほうが効率が良いと思い込んでいたので最低限しか手を動かしていませんでした。そのせいもあって本番かなり応用の効かない知識になっていたように感じました。
これからE試験の勉強する方はぜひ手を動かして勉強することをお勧めします。
またJDLA認定講座は絶対に何周もすることをお勧めします。市販のどの書籍よりも認定講座の方が出る確率が高いと感じました。
ただ、ぶっちゃけ合格するだけなら座学的な勉強でもいけるとは思います。
-
お金、、、
一番の問題は如何せん高い、、、笑
僕の受けたJDLA講座は学割ありで8万、最後の認定試験で15000円、E資格本番の受験料で22000円、合計で約12万です。これでも半年前の時点で最安だったと思います。
最近は色々一ヶ月3000円でチャレンジするキャンペーンなどもあったようですので、Twitterなどで情報を収集するのは非常に大事だと思います。
注意としては必ず講座の内容をしっかり見るようにしてください。試験を受けてみてJDLA講座の内容はかなり出ますし、特に最新の内容などは一人で書籍で勉強するのは骨が折れます。あんまり安い講座をとって質が低いと合否に関わってくる可能性があるのでぜひちゃんとした講座かどうか確認してください。
とはいえ、僕は貯金はたきましたし、お金がないと質を選ぶのも無理なんで人によってはどうしようもないんですが、、、笑
ちなみに掛けた金額の価値があったかどうかは正直わかりません。高額なぶん一生懸命勉強したというのはありますが、資格そのものがキャリアにおいてどれほど役立つかはなんともいえません。
内容は思ってたより高度なので勉強にはなりました。
-
感想
最新のトピックがよく出ていたので、書籍をやりこなすだけでは到底高得点は無理だと思います(書籍は時間のずれが大きいので最新のトピックについて行くのは厳しいです)。しかし、ただ合格するだけなら、ちまたでお勧めされている書籍をやり込めばギリいけるんじゃないかなと感じます。お金がある程度かけれる人、もしくは絶対に合格する保証が欲しい人は高めのJDLA講座を選んでもありだと思います。
【ご報告】エンジニアとしてプロジェクトに参加させていただくことになりました。
どうも、わくばです！
ずいぶん間があいてしまったんですが、実はタイトルにもある通り、フロントエンドエンジニアとしてプロジェクトに参加させていただける事になりまして、そちらのタスクで全然ブログが書けていませんでした。
就職とかインターンではなく、お金をもらえるものではありません。したがって仕事と呼べるものではないので「エンジニアとして」という表現が適切かはわかりませんが、やることは結構ガッツリエンジニアリングです。
大学をまたいで医学生のみで構成されているコミュニティがありまして、そこで医学生向けのWebサービスを立ち上げようということになり、そこにjoinさせてもらえたって感じです。
なのでまた更新頻度はグッと落ちると思います。もともと頻度低いですが(笑)
プロジェクトの進捗等も記事にしていければと思っています。
もう6年生で受験生になるので両立できるかかなり不安ですが、ここは正念場と思って本気で戦っていきたいと思います。
今日は報告だけとさせていただきます。ご質問やコメントいつでもお待ちしています。
【アルゴリズム(JS実装)】Rabin-Karp Algorithm
どうも、わくばです！
今回はRabin-Karp algorithmです。どんどん重たくなってきたので、日をまたがないとできなくなってきました(汗)。まだまだですね。。。
Rabin-Karp algorithmはハッシュ関数を用いたマッチングアルゴリズムです。ハッシュ関数というのは暗号化というか何らかの値を返す
たとえば探している文字列をaaabとし、検索対象の文字列をabaaaaabaaababaabなどとした場合、まずは探したいaaabという文字列をハッシュ関数に掛け数値化(出力Xが得られたとする)します。そして
- 検索対象のアルゴリズムから、最初の4文字をとってきてハッシュ関数にかける。
- その値が探したい文字列のハッシュ値Xと等しければ、 更にその部分の文字列と、位置文字ずつ照らして本当に等しいか確認する。
- ハッシュ値が違えば、一文字ずらして手順1からまた繰り返す。
ハッシュ関数として用いられる代表的なものは以下のようなものです。
\(f(aaab)=A*n^3+A*n^2+A*n^1+B*n^0\) (Aは文字aの文字コードを意味する)
n進数的な表現ですね。用いる文字の種類が10種類ならばn=10、26種類ならn=26とするなど、状況に応じて変更可能です。
このアルゴリズムはRolling Hash Algorithmと呼ばれることもあるのですが、これは検索対象の文字列をスキャンしてハッシュ値を出していくときに、前の値を使いながら計算していくためです。例えばabaaaaabaaababaabをスキャンしていくとき、二回目のbaaaを算出する時に一個前のabaaを用いて算出します。
より詳細の説明は以下の動画の16分くらいからが非常に参考になります。
式で言うとこんな感じです。
$$ f(baaa)=(f(abaa)-\color{red}{ A*n^3 })*10+\color{green}{A*n^0} $$
赤い部分は\(f(abaa)\)の一行目を削除していて、緑の部分で新しいものを足しています。
実際はこれだと桁が大きくなりオーバーフローを起こす場合があるのでコードではmodを用います。
コードは以下のようになります
const d = 256; const search = (pat, txt, q) => { const patL = pat.length; const txtL = txt.length; let pHash = 0; let tHash = 0; let h = 1; for (let i=0; i<patL-1; i++) { h = (h*d)%q; } //patternとtextのハッシュ値を算出 //textについては最初のやつのみ。後で漸化的に更新するため
//qで割ったあまりを使うバージョン for (let i=0; i<patL; i++) { pHash = (d*pHash + pat.charCodeAt(i))%q; tHash = (d*tHash + txt.charCodeAt(i))%q; } //一致するインデックスを最後に返すための配列 let result = []; //探索を開始 for (let i=0; i<txtL-patL+1; i++) { //最初のハッシュ値が一緒なら //それを確かめる。Naiveのやり方と同じ if (pHash===tHash) { let matchCount =0; for (let j=0; j<patL; j++) { if (txt[i+j] !== pat[j]) { break; } else { matchCount++; } } if (matchCount==patL) { result.push(i); } } //最後まで言っていなければtHashを更新して次のループへ if (i < txtL-patL) { //ここで一個前のtHashを用いて更新 tHash = (d*(tHash-txt.charCodeAt(i)*h) + txt.charCodeAt(i+patL))%q; if (tHash < 0) { tHash += q; } } } return result; }
いくつか補足をします。
まず以下の部分
for (let i=0; i<patL; i++) { pHash = (d*pHash + pat.charCodeAt(i))%q; tHash = (d*tHash + txt.charCodeAt(i))%q; }
は上で説明したmodバージョンでのことです。%qというのはqで割ったあまりです。こいつはわざわざforループを用いて何をやってるんだと思うかもしれませんが、aaabを例にすると結局\((A*d^3 + A*d^2+A*d^1+B*d^0)\%q\)と同じ値になります。この記述だと記述時に文字列の長さをわかってないと書けませんから、入力に応じて動的に算出できません。しかし上のコードのようにすればforループの回数を制御すればよいですから動的に変更できます。
なぜああ書けるのか説明します。Aをqで割った時の商をu、あまりをvとすると、A = uq + vとかけるので
pHash_1 = (d * pHash_0 + A) % q
= (d * pHash_0 + A) - uq
= A -uq (pHash_0はもともと0なので)
pHash_2 = (d * pHash_1 + A) % q
= {d * (A -uq) + A} % q
= {d * (A -uq) + A} - u'q
= d * A + A - q(du + u')
pHash_3 = (d * pHash_2 + A) % q
= {d *(d * A + A - q(ud + u') )+ A} % q
={ d^{2} A + dA + A - q(d^{2}u + u'd)} % q
= { d^{2} A + dA + A -q(d^{2}u + u'd)} - u''q
= d^{2} A + dA + A - q(d^{2}u + u'd + u'')
pHash_4 = (d * pHash_3 + B) % q
= {d * {d^{2} A + dA + A - q(d^{2}u + u'd + u'')} + B } % q
= { d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d ) } % q
したがって
\((A*d^3 + A*d^2+A*d^1+B*d^0)\%q\)と同じ結果になります。
次は以下の部分です。
tHash = (d*(tHash-txt.charCodeAt(i)*h) + txt.charCodeAt(i+patL))%q;
これはmodバージョンによる更新になります。
基本的には上の方で説明したとおり、ハッシュ値を出すとき一番くらいの大きい項を削除して新しい項を追加しますが、わかりにくいのは以下のhです
txt.charCodeAt(i)*h
これは例えば文字列aaabを考えると上のpHashの結果から
{ d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d ) } % q
= d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d + u''' )
ここから先頭を差し引くにはd^{3} Aを引かなければなりませんがtxt.charCodeAt(i)のみではAにしかなりませんからd^{3}の部分をhとして計算してあるわけです。以下のコードの部分ですね。
for (let i=0; i<patL-1; i++) { h = (h*d)%q; }
長々とした説明になりましたが、理解できましたでしょうか。疑問点や誤植などありましたらお気軽にコメント下さい。
最後に時間計算量ですが探したい文字列の長さをm、検索対象の文字列の長さをnとすると\(O(n+m)\)になります。ハッシュがマッチしたときだけ追加でm回ループが必要ってことですね。最悪の場合はいちいちハッシュがマッチするのでほぼNaive アルゴリズムみたいな感じになります。
では。
【アルゴリズム(JS実装)】Knuth Morris Pratt Algorithm
どうも、わくばです！
今回はKMP algorithmです。これは意味がわかるまでかなり時間かかってしまいました。なんとなく言いたいことはわかるんですけど、それをアルゴリズムに起こすときにハテナが大量に(笑)
KMPは前処理部分と探索部分に分かれていて、探索部分はすぐしっくりきたんですが、Longest Proper Prefix which is Suffix (LPS) arrayをつくる前処理部分が何をやってるのか全然わからなくて、、、(笑)。日本語の解説だとテーブルって呼んでるのも見かけますが、LPSと同じものです。
アルゴリズムそのものの解説はこの記事が非常にわかりやすいのでぜひ。
一週間で身につくアルゴリズムとデータ構造|応用編第2日目：文字列検索のアルゴリズム①(KMP法)
またLPS作成部分にピンとこない方は、次の記事にgifがあるので参考にすると良いと思います。
LPSの部分を理解するコツはforによるiと、先頭付近の配列を記憶するprefixという2つのカーソルが別々で動いていることを認識することです。特にiは最初から最後まで動く一方、prefixは先頭付近でしか動きません。
まずはLPSをつくる関数です。ぜひ、上記記事のgifをみながら確認してみてください。
const createLps= pattern => { const { length } = pattern; let lpsInit = new Array(length); let lps = lpsInit.fill(0); let prefix = 0; //パターンの開始点 for (let i=1; i<length; i++) { // ② // 異なるものがでてきた場合は、前にさかのぼり // さかのぼって一致した地点でループを while (prefix>0 && pattern[prefix] !== pattern[i]){ prefix = lps[prefix-1]; } // ①
// ifがないとprefix=0かつpattern[prefix] !== pattern[i]を取りこぼすので注意 // prefixとiの要素が等しい場合はprefixを増やします。 // prefixが増加している間は、先頭と同じパターンの配列が続いていることを意味します。 if (pattern[prefix] == pattern[i]) { prefix++; //このprefixをlpsに入れる lps[i] = prefix; } } return lps; } let str = "ACABACACD"; console.log(createLps(str))
>>>[
0, 0, 1, 0, 1,
2, 3, 2, 0
]
完成した配列の見方ですが、これは探索時に、その地点までパターンがマッチしていたときにどこまで戻すかを意味しています。ACABACACDというパターンを探すとすると、ACABACACDの赤の部分までパターンがマッチしていた場合は、Cのindex=5に該当するlps[5]=2まで戻るという意味になります。つまりpattarn[2]から比較を再開します。
そして探索部分です。
const KMPSearch = (pattern, text) => { const P = pattern.length; const T = text.length
const lps = createLps(pattern) let patIdx = 0; let txtIdx = 0;
const matches = []; while (txtIdx < T) { if (pattern[patIdx] === text[txtIdx]) { txtIdx ++; patIdx ++; } //全部マッチした場合 if (patIdx === P) { //マッチし始めたスタート地点をpush matches.push(txtIdx-patIdx); //次の比較開始地点へ飛ぶ patIdx = lps[patIdx-1]; } if (txtIdx < T && pattern[patIdx] !== text[txtIdx]) { if (patIdx !== 0) { //次の比較開始地点へ patIdx = lps[patIdx-1]; } else { txtIdx++; } } } return matches; }
txt = "ABABDABACDABABCABABDKGUSKAAABABCABAB" pat = "ABABCABAB" console.log(KMPSearch(pat, txt))
>>>[ 10, 27 ]
探索のコードはそんなに難しくないかなと思います。LPSを用いて、パターンの戻る位置を効率的にしていますね。
時間計算量はLPS配列作成部分で\(O(k)\)(\(k\)=pattern.length)、探索部分では\(O(n)\)(\(n\)=text.length)\)となるので合わせて\(O(k+n)\)と考えられます。
\(logn\)や\(n^2\)でなく線形時間で処理が終わるパターン検索はKMPアルゴリズムのみのようです。本体より前処理のLPSのほうが複雑なのがネックですが(笑)
今日は以上です。
では。
【アルゴリズム(JS実装)】Naive String Pattern Matching (Brute Force Approach)
どうも、わくばです！
今日からPattern Searchingに入りたいと思います。KMP AlgorithmやBoyer Moore Algorithmなどちょっと耳にしたことのある仰々しい名前のアルゴリズムが待っているジャンルなのでちょっと怖いです(小並感)。
まずはNaive String Pattern Matchingです。Naiveとってことは一番基本的ということなんでしょうか。確かにKMPなどもっと凝ったものがあるのでそれと比較してNaiveってことなんですかね。
シンプルな文字マッチのアルゴリズムです。
コードは以下のようになりました。
const naiveStrMatching = (pattern, text) => { const result = []; //textの中のi番目からpatternと比較を開始 for (let i=0; i <=text.length - pattern.length; i++) { //jはpatternのインデックス let j=0; while (j < pattern.length) { //textとpatternが一致しなかって時点で //i番目から始まる比較は終了する if (text[i + j] != pattern[j] ) { break; } //patternと一致する限りカウントしていく j++; } //ｊでカウントした値とpatternが一致すれば //patternがピッタリ一致したことになるので //そのスタートであるiを返す。 if (j===pattern.length) { result.push(i); } } return result; } ;
whileとif breakの使い方が独特だなと感じました。ループを抜ける条件をより細かく指定できます。
時間計算量はpatternのサイズをm、textのサイズをnとすると\(O(m\cdot (n-m))\)になります
以上になります。アルゴリズムって無限にあって、競プロerの方々は本当にすごいですね。時間制限あったら絶対ムリです笑
では。
