【プログラミング】アルゴリズムの考え方を実際の例題付きで解説するよ！

こんにちはカレイドです。

今回はバックエンドを勉強するにあたって必ず当たる壁のアルゴリズムについて考えてみたいと思います。

 

例題を使用しながら自分の解決方法とともに見ていこうと思います。

あくまで解き方の一例になりますのでもっといい解き方がある場合はむしろ教えてもらえるとありがたいです。

解き方は千差万別ですのでまずはそこを抑えましょう。

 

 

問題を確認

 

まずはどのようなものを実際に作りたいのかを確認しましょう。

 

こちらのウェブアプリは私が実際に作成したものになるのですが、

 

実際の問題を確認

 

アプリにグラフが描写されているのがわかると思います。

 

このグラフを作るためのデータが欲しいってのが今回の問題です。

 

 

欲しいデータを確認する。

では実際にグラフを描写するのにどんなデータが必要なのかチェックしましょう。

 

グラフのタイトル、

横軸、縦軸のタイトル

 

横軸、縦軸それぞれのデータ。

 

こんなもんですかね。

 

タイトル系は特に問題にならないので今回は横軸、縦軸のデータに着目していきます。

 

データは全部で何個必要か、考えましょう。

 

私のアプリの場合は、切り替えがついていて過去7日間、28日間、90日間の全3パターン選べるようになっています。

 

つまり可変が出来るようになっている必要があります。

 

また、実際のデータはデータベースに挿入されていてそれを引っ張り出してきてそこから整形します。

 

イメージ図ではこんな感じです。

 

 

問題になるところを確認する。

 

ではなぜデータ処理をする必要があるか考えると、

 

 

ユーザーは習慣を記録していきますが、毎日やる人もいればそうでない人もいます。

 

 

毎日やる人しかいなければデータベースから取り出したものをすべてそのまま表示すればよいのですが、間が空く人がいます。

 

その場合はデータベースには更新分のデータしかないので表示するデータが欠けてしまいます。

 

このデータをうまく成型してどのユーザの場合にも対応できるようにするのが今回の問題です。

 

では実際のデータセットを見てみましょう。

 

[
    {
      date: "1559192530152"
      habitId: "5cf74caf61ba7500171f74be"
      today: 2500
      total: 2500
      __typename: "HabitRecord"
      _id: "5cf74cd261ba7500171f74bf"
    },
    {
      date: "1559451782191"
      habitId: "5cf74caf61ba7500171f74be"
      today: 1200
      total: 3700
      __typename: "HabitRecord"
      _id: "5cf74d0661ba7500171f74c3"
    },
    {
      date: "1559624588045"
      habitId: "5cf74caf61ba7500171f74be"
      today: 1200
      total: 4900
      __typename: "HabitRecord"
      _id: "5cf74d0c61ba7500171f74c7"
    }
  ]

 

 

 

これだけではわからない方もいると思いますので簡単に用語の説明をします。

dateは日付で通常のjavaScriptのDate形式です。問題では日付に直せるので気にしなくて大丈夫です。

habitIdはこのレコードがどのhabitの物かを見分けるＩｄになります。

 

todayは今日の積み上げた分になります。整数型で30とか50とか

totalは前日までの合計にtodayを足したもの例の通り初日はその分を加え、以降は前回の物に+todayをしたものです。

 

_id はもともとのレコードが持つ一意のId。

 

以上が問題で与えられるデータになります。

 

問題文

今回はデータ不足ケースを考えるため7日分に変換するので3日分の配列データを7日分に変換してください。

 

ただしデータ構成はdate,today,beforeTotalの3種類のオブジェクト型になります。

 

つまり 

data={
date:[],
firstData:[],
secondData:[]
}

 

簡単に説明すると

 

dateは指定された日付分のデータ例えばその日から7日前までの日付が入っているということです。

firstDataはその日にユーザが積み上げた分ですね30分とか1000文字とか

beforeTotalはその日に積み上げたぶんを足す前の合計になります。

実際にグラフを見てみるとわかるかと思います。！

 

ではしばらく自分の頭で考えてどのようなアプローチで問題を解決するか考えてみましょう。

申し訳ないですが今回はJsでの解答のみになりますが、思考過程はどの言語でも同じなので参考になると思います。

 

問題を解くときに意識しておきたいこと

 

これはぜひ声を大にして伝えたいことですが、どんなロジックでも基本的なパターンはfor文とif文の組み合わせでしかないことです。

 

細部まで問題を切り分けて一個ずつ解決していけば泥臭くても必ず解けます。

 

あくまで関数やライブラリはその過程を短くして見やすくしてくれるだけのものだと僕は思っています。

 

問題を大きく見ずに小さく見ていくことが成功のカギだと考えています！

 

 

 

解決策①　データベース側で対策を取る

 

誰もが疑問に思ったと思いますがそもそもデータベースに入れるときにい何とかしておけパターンですね。

 

まずは自分はこれを考えました。

 

ただしユーザがいつデータを入力してくるのかわからない、かつ、その日を過ぎたら勝手にデータベースがデータ挿入させる方式は難しそう。。。

 

ユーザがデータ挿入時に日付を確認、間が抜けている場合は自動でデータ挿入をする方法ならいけそうな気もします。

 

今回は後処理にしようとしたのでやめました。

 

 

解決策②データ表示する日数分だけループさせる。

 

実際に配列を作成して足りない分を補っていく方法。

 

まあこれが一番王道だと思います。

 

どの言語でもforループを使って攻めていこうかなと考えると思います。

 

JavaScriptなら

const data = {};
	if (habitRecords.length === 0) {
		return data;
	}
	const categories = [];
	const firstData = [];
	const secondData = [];

	data.yTitle = unit;

	let count = 0;

	for (let j = 0; j < maxDays; j++) {
		let recordDay;
		let today;
		let total;
		if (count === habitRecords.length) {
			const lastIndex = habitRecords.length - 1;
			recordDay = moment(+habitRecords[lastIndex].date).format("YYYY-MM-DD");
			today = habitRecords[lastIndex].today;
			total = habitRecords[lastIndex].total + today;
		} else {
			recordDay = moment(+habitRecords[count].date).format("YYYY-MM-DD");
			today = habitRecords[count].today;
			total = habitRecords[count].total;
		}

		const day = moment()
			.add(-maxDays + j + 1, "days")
			.format("YYYY-MM-DD");
		categories.push(day);
		if (String(recordDay) === String(day)) {
			firstData.push(today);
			secondData.push(total - today);
			count++;
		} else {
			firstData.push(0);
			secondData.push(total - today);
		}
	}

	data.categories = categories;
	data.firstData = firstData;
	data.secondData = secondData;

順を追って解説していきますね。   まずは日付の比較方法ですがJavaScriptではmomentというライブラリを使うともともとJavascriptが持っているDate型をお気に入りの形に変換してくれます。

recordDay = moment(+habitRecords[lastIndex].date).format("YYYY-MM-DD");

例えばこの一文ならmomentにDateオブジェクトをmoment関数に入れてからformat関数で形を指定すると2019-05-21のようなobjectに変換してくれます。

データベースにはString型で入れているのですがmomentにはInt型で入れるので前に+をつけています。

 

 

私は最初7日分のデータを埋めるので7日分ループさせようと考えました。

そして、中でもらったデータをループさせることを考えたのですが、

中でfor文使ってループを回すとcontinueでもbreak文を使ってもかなり複雑になる気がして難しそうでした。

 

というわけで中でループさせる考えは捨てて7日分ループの外でcountという定数をセットしておきます。

 

これはもしもループで回っている日付と持ってきたデータのcount番目の日付が等しい場合とそうでない場合を考える定数になります。

 

if (String(recordDay) === String(day)) {
			firstData.push(today);
			secondData.push(total - today);
			count++;
		} else {
			firstData.push(0);
			secondData.push(total - today);
		}

 

 

 

この部分になります。ここでは同じだった場合には最初のデータにその日の積み上げ分を記録して、二番目の部分にtotalからその日のtodayを引いたものを格納します。

そしてcountを1増やして次のデータの値を引っ張り出します。

違かった場合にはその日の積み上げ分は0、totalは上記と変わらないです。

これによって指定された日付分をループして足りない分を補っていく形になります。

 

 

if (count === habitRecords.length) {
			const lastIndex = habitRecords.length - 1;
			recordDay = moment(+habitRecords[lastIndex].date).format("YYYY-MM-DD");
			today = habitRecords[lastIndex].today;
			total = habitRecords[lastIndex].total + today;
		} else {
			recordDay = moment(+habitRecords[count].date).format("YYYY-MM-DD");
			today = habitRecords[count].today;
			total = habitRecords[count].total;
		}

次は最初のif文の説明になりますが、

 

気を付けるのはcount++をする場合にまだループの途中だった場合には参照する配列が無くなってしまいはみ出してしまいエラーを吐きます。

 

さらに残りの日数は今までtotalにはtotal-todayを入れていたものをその日以降はtodayが0かつtotalには通常通りtotal（現在までのtotal)の値が入ることになるので最初のループで場合分けをする必要が出てきます。

 

この場合分けが数学っぽくて難しい部分になります。

 

解決策としてはcount++をした後のループで長さと等しくなった場合にはループを切り分けます。

そしてlastIndexという変数に配列の最後の値を格納して以降はすべて最後の配列の中身を使います。

 

私自身も何度もパターンを考えてロジック組みなおしてます...

 

もっとスマートなやり方があるならば教えていただきたいです。初心者の頭ではこれが精いっぱいでした。笑

 

ですので、まだループの途中の場合にはカウントを減らせるようにループの最初に長さを超えていないかをチェックします。

 

以上が解法になります。

 

 

解決策③データベースからとってきたデータ分だけループを回す。

 

これは後で思いついた解法ですがそもそものデータベースだけループを回す方法を考えたのがこちらです。

まぁ結局日付が欲しいデータ分までwhileで回さないといけないのでほぼ同じです。

 

どんなやり方でもできますのでもれなくデータをかき集めるだけですね！

 

habitRecords.forEach(record => {
		const recordDay = moment(+habitRecords[count].date).format("YYYY-MM-DD");
		const { today, total } = record;
		let day = moment()
			.add(-maxDays + count + 1, "days")
			.format("YYYY-MM-DD");

		while (String(recordDay) !== String(day)) {
			console.log(count);
			categories.push(day);
			firstData.push(0);
			secondData.push(total - today);
			count++;
			day = moment()
				.add(-maxDays + count + 1, "days")
				.format("YYYY-MM-DD");
		}

		categories.push(day);
		firstData.push(total);
		secondData.push(total - today);
	});

	while (count !== maxDays - 1) {
		const { total } = habitRecords[habitRecords.length - 1];
		const day = moment()
			.add(-maxDays + count + 1, "days")
			.format("YYYY-MM-DD");
		categories.push(day);
		firstData.push(0);
		secondData.push(total);
		count++;
	}

	data.categories = categories;
	data.firstData = firstData;
	data.secondData = secondData;

 

解説としてはデータ分だけまずループさせる。

 

そしてその内部でwhile分を作って日付が一致するまではtodayには0を入れるようなロジックを組む。

 

そして一致した場合にはその日付はユーザーが習慣を更新したということを意味するのでループを抜けてtodayにはユーザーがいれたtodayを入れる。

 

このループ内では結局データ分しかループしないことに気を付けると次にcountが欲しい日付分まで到達していない場合にはcountが欲しいデータ分に等しくなるまでwhile分を組む必要があります。

 

つまりこの段階ではユーザの更新した日が表示するデータの最終日ならいいですが、そうでない場合にはそこでデータは終わっていて残りの日数はまだデータが入っていない状態だからですね。

 

どうしたらいいかというと、もともとデータベースから持ってきた データ配列の最後の値を利用して、todayは0　totalはそのまま使えます。

 

いろいろな解決策を経て....思ったこと.

 

 

いかがでしたでしょうか私がアプリを作る中で一番苦労した部分になります。

 

結局バックエンドの構築は

 

CRUDの組み合わせ＋データをどう処理して表示するかだけの問題になります。

 

そしてなぜデータ処理のロジックが難しいかというとネットで調べても解決しないからですね。

 

その部分はアプリ固有の問題になるのですぐに解決することが難しいです。

 

解決策としては直接知恵袋などで質問したり、出来る友人に聞くことが一番の近道です。

 

ただこういうロジック部分は必ず通る道なので初めは頭を悩ませてがっつり立ち向かうことを個人的におすすめします。

 

まとめ

 

今回は自作アプリの中で自分が頑張った点でかつ、多くの人が躓くだろうなと思ったロジック部分の解説をしてみました。

 

おそらくベストな解法ではないと思いますので

 

もっと簡潔な方法がある場合にはTwitterのDMやコメント欄で送っていただけるとめちゃくちゃうれしいです！

 

ではまた次回の記事でお会いしましょう。