マージソート

ひとまずメモ.
分割(Divide)を行い,mergeにて統治(Conquer)を行っていることが分かれば問題なさそう.(正確には違う)

  • merge

 - 要素を二つに叩き切る(intの小数点切り捨てによって偶奇の場合分けが必要ない)
 - 要素数が1になるまで継続
 - 分割した左右の配列の最後尾の要素をINFにすることで,片方のソートする要素が消えた後の参照でバグることを防ぐ

  • mergeSort

 - 要素数が二つ以上の場合に処理を行う
 - ソートされた左右の配列を呼び出し,それらをmergeにてソートを行う.
 - これは再帰的に処理されている.

上記内容さえ押さえておけば問題なさそう.
早くクイックソートを実装したいです笑.

#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	for(int i=0;i<n1;i++)L[i] = A[left + i];
	for(int i=0;i<n2;i++)R[i] = A[mid + i];
	L[n1] = R[n2] = SENTINEL;
	int i = 0, j = 0;
	for(int k=left;k<right;k++){
		cnt++;
		if(L[i] <=R[j]){
			A[k] = L[i++];
		}else{
			A[k] = R[j++];
		}
	}
}

void mergeSort(int A[], int n, int left, int right){
	if(left + 1 < right){
		int mid = (left + right) /2;
		mergeSort(A,n,left,mid);
		mergeSort(A,n,mid,right);
		merge(A,n, left, mid, right);
	}	
}

int main(){
	int A[MAX], n, i;
	cnt = 0;

	cin >>n;
	for(i=0;i<n;i++)cin >> A[i];

	mergeSort(A,n,0,n);

	for(i=0;i<n;i++){
		if(i)cout<<" ";
		cout << A[i];
	}
	cout << endl;
	cout<<cnt<< endl;

	return 0;
}

二分探索

Courseraは完全放置中.研究と就活のせいでやる気すら起きないです...

就活のコードスプリントに生まれて初めて参加したところ爆死しました笑
情報系ではないので計算量という概念が無くTLEしまくりで諦める羽目に...
でも楽しかったので,少しずつメモしていこうかなと考えております.
TLE解決のため最も必要であった二分探索を今更ながら実装しようとポチポチやっていたところツモってしまったのでメモ.

エラーは以下.

error: could not convert ‘(int*)(& a)’ from ‘int*’ to ‘std::vector<int>’

原因は単純で,読み込んだaが配列になっており,binary_Searchの引数のベクトル型へと変更できていないからでした.
エラーを読んでも原因はさっぱりだったので,一度std周りは丁寧に勉強したほうが良いのかもしれない….
何となく調べていたところ下のページに遭遇し,解決.
[vector] 配列をベクトルに変換する最も単純な方法は何ですか? [arrays] [c++] | サンプルコード [日本語]

vector <int> v(a, a + sizeof a / sizeof a[0])

とすることにより配列aをベクトルvへと変換できているらしい.
上のサイト曰く”x + sizeof x / sizeof x[0]は、最後の要素を超えて1つの要素を指すことに注意してください。”とのこと.

書いたソースは以下の通り.自分で書くとカスタマイズできそうなので少し嬉しい.
これからもちょこちょこ書いて大切に使っていきたいところ.
適当なチェックとしては,
6
0 2 3 6 8 9
6
を入れて
3が出てくればOKです.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int binary_Search(vector <int> A, int key){
	int left = 0;
	int right = A.size();

	while(left < right){
		int mid = (left + right)/2;
		if(A[mid] == key){
			return mid;
		}
		else if(key < A[mid]){
			right = mid;
		}
		else{
			left = mid+1;
		}
	}
}

int main(){
	int n,b;
	cin>>n;

	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	vector <int> v(a, a + sizeof a / sizeof a[0]);
	cin>>b;

	int c =binary_Search(v,b);
	cout << c << endl;
}

CourseraのMachine Learning修了

はじめに



初めての記事なので修正・追記しまくるかもしれません.悪しからず.

CourseraのMachine Learning



3/5に開始したCourseraのMachine Learningを3/23に終了したので,何か書いてみようかなと.
元々は,各週のまとめを記事にしようと考えていたのですが,WEEK3で面倒になり,まさに三日坊主で中断…下書き状態で放置されております.
この記事では,

  1. ハードル
  2. 要求される知識水準
  3. ( 受講ペースの一つの目安)←学生向け
  4. 修了証について

を書くことでこの講座に対する敷居を下げる一助になればと願っております.

1.ハードル



 全体概要に関してはこのブログが非常に明るいです.私も受講を開始するときには参考にさせて頂きました.正直リンク先の記事を読めば十分です
数学の苦手なバイオの学生がCourseraの機械学習コースを修了して気づいたこと - Qiita

この手の「どの程度の知識を持っていれば良いのか」,「どの経歴を持っている人であれば十分なのか」という情報に関しては多すぎて困ることはないと思うので,追加の意味も込めて,私の専攻と照らしつつグダグダと書いていけたらと考えております.

まず私は機械工学(宇宙工学)を専攻していたのですが,大学でのプログラミングといえば一年時にこなしたC言語のみです.
その上,プログラミングの担当教員の課題がしんどかったので,敢えて単位を落として別の先生で単位を取得する程度には苦手でした.

そしてこの度無事逃げ切りに失敗し、「音声信号処理」を専攻することになりました.
そう,機械学習・深層学習が必要になってしまったのです……

ということで機械学習の勉強を行おうと本を読んでいたのですが,次元削減などを「あーはいはいそんな感じね」と適当に読んでいた結果,「分かっているようで全く分かっていないアホ」になってしまい,一から丁寧に勉強し直すことに.
困り果てて聡明な友人諸兄に相談したところCourseraのMachine Learningをオススメされた次第です.

オススメされたので調べてみると

  • Octaveを用いる
  • 英語
  • 社会人の受講生が多い
  • 課題がある
  • 締め切りがある

とのことで,ハードルがみるみる内に上がっていくのを感じました.
他の分野を専攻していた大学生が受講しても大丈夫なものなのだろうかと.

しかし無料だったため気にせず登録して様子を見ることに.
結果,上記のハードルはそこそこ杞憂であることが判明しました.

プログラミングがメインではないためデバッグ量の少ない高級言語を用いているというだけなので,受講目的には最適です.どうしてもPythonでやりたいという方も,この講義ではひとまず耐えて,後に控えているdeep learningの講座でスキルを存分に発揮すればいいと思います.deep learningの方ではPythonになるらしいです.

  • 英語

日本語字幕のある箇所はさておき,TOEIC720程度しかない人間でもかなり読みやすい文体になっておりました.この講義,分かりやすさに関しては抜群の工夫が凝らされており,英語の表現に関してもそれは例外ではありませんでした.より多くの人が講義についてこられるように平易に・丁寧に作られておりました!
多分TOEIC500点台でもいけます.それでも困ったらGoogle翻訳にぶち込みましょう.

  • 社会人の受講生が多い

社会人ほど現場に近い感覚での消化はできないかもしれないですが,コースを修了するだけなら学生でも余裕です.膨大な時間を注ぎ込みましょう.それでもしんどかったら人格を捨てましょう.しんどいポイントをあらかじめ把握しておけば攻略も容易です.具体的にはWEEK3とWEEK7だったはず.

  • 課題がある

相当丁寧な講義があるので,ゆったりと消化することができれば作業自体はデバッグのみになります.というか本講座においては、課題が一番面白かったです.デバッグに4時間とか食ってましたが(笑)
WEEK10あたりのクイズを間違えまくると「ペナルティー無しやで」的なメールが来ます

  • 締め切りがある

無視して良いらしいので自分のペースでやりましょう.たまにペースについてのコメントがされたメールが来ます.


以上の内容を通じて
「あれ…いけるのでは…?「
と感じて頂きたい.

始めるのにハードルを感じている人がいたとしたら,それは杞憂です.しかも無料です.ついでに本より面白いです.

2.要求される知識水準



数学の要求水準は低いです.事前に「線形代数が必要」と言われていたのですが,
「え…?どの学部の線形代数?数学科?」
とか考えて無闇に怯えていたのですが,正直なところ高校生でも行列を習っていれば解けます.←高校の学習指導要領改訂が変更していたんですね…
メインになるのは基本計算と転置行列,逆行列ぐらいです.基本演算のみです.

プログラミングに関しては,大学の講義を一度でも取ったことがあれば苦はないと思われます.
とはいえ経験値が0だと流石にしんどいかもしれません.簡単な本を一冊サクッと終えてみてください.

3.( 受講ペースの一つの目安)←学生向け



学生としてのペースについてコメントします.社会人の方々はせいぜい健康に気を遣って体を壊さないペースでのびのびと勉強していてください.

ペースを決めるにあたって,私は「有名なブログの全てを上回るペースでやったろ」という軽いノリで一日1WEEK分を目標にしていました.
が,3日目にして気持ちが切れました. 
旅行などもあり結果的に20日弱かかったのですが,暇な学生であれば,この程度のペースが速習の目安かなと思います.計70~80時間程度です. 
一ヶ月以内には一周目を終わらせたほうがいいです。あまり間延びしたペースでやると、前の講義内容を忘れて復習することになり,その面倒さ故に受講を辞めてしまうと言うこともあり得るからです.パッと一周してしまえば,あとは寝そべりながら何周もするだけです.頑張ってください!

4.修了証について



ネットの話だと「途中から修了証を発行しようとすると問題を一から解き直す羽目になる」とのことでしたが,修了当日に欲が出て本人確認したらその日に貰えました.

何故…?

基本的にスマホではなくパソコンで受講していたのですが,その関係だったりするのでしょうか.
もしくは本人認証の要求が下がったのか.
まあ何はともあれ,無料で受講した後に修了証を発行できるのであれば気にせず無料で受講することができますね.

発行できればの話ですけど(正直よくわかっておりません)

ともあれ



私は機械学習のエキスパートではないため大きなコメントはできませんが,サッと登録して確認してみる価値はあると思います.
登録すら面倒という方はYou Tubeで確認してみましょう.あるかもしれないし,ないかもしれない.

私個人は,受講した結果Courseraのdeep learningの講座とUdacityのNVIDIAの自動運転の講義に申し込むことにしました.あれ、音声認識は?というのも、日本語で勉強していたのに英語で勉強できる気がしてきてしまったせいです.こういった根拠の弱い自身と行動力も手に入りますし,行動しないのは心に悪いです.
受講しようか悩んでいる方々が本記事を読んで,頭を空っぽにし無心でCourseraに登録し気が付いたら受講を開始できておりますよう,心から願っております.
ついでに修了してくださいまし.