プログラミングにおいて、値（データ）の扱いはとても重要です。今度は、値をどう管理すべきか、値をどう処理すべきかについて学んでみましょう。
連載目次
今回学ぶ内容
プログラミングというのものは、極端なことを言うと、値の操作の集まりです。なので、値をどう上手に扱うか、という一点が重要になってきます。値の扱いが上手ければ、処理が高速に終わるかもしれません。また、少ないメモリ消費で動くかもしれません。
今回はそういった「処理効率」に焦点を当てていきます。そして高い処理効率を実現するには、データ構造とアルゴリズムの知識は必要不可欠です。
値を保持するデータ構造は様々存在します。データ構造が違うと何が違うのか、それぞれどんなメリットがあるのか、どんなデメリットがあるのか、いくつか実例とともに紹介していきたいと思います。
またアルゴリズムという言葉も聞いたことがあるでしょう。アルゴリズムとは何か、どうやって使うのかについて学んでいただきます。
データ構造と計算量
データ構造という言葉を聞いたことがあるでしょうか。聞きなれないとは思いますが、読んで字のごとく、データを保持する構造のことをデータ構造と言います。
「データをどういう形式で保持するか」によって、処理効率は大きく変わってきます。
ですが、いきなり小難しい話をしても混乱するだけなので、まずは第3回の記事で触れた配列を題材に、データ構造の観点から見ていきましょう。
配列
配列は代表的なデータ構造です。複数の値をひとまとめにし、効率的な処理を実現します。
'use strict';
const array = [1, 2, 3];
console.log(array[0]); // 1配列は連続したデータを扱うのに長けてます。例えば数学におけるベクトルを表現するのに、配列は適しています。
インデックス（添え字）がわかっていればデータに一瞬でアクセスできるのも特徴のひとつです。
一方で中から値を探し出すのは苦手です。例えば「この配列の中に123という数値は存在するか？」ということを調べるためには、最悪の場合は配列のすべての要素を調べなければならないからです。
計算量（オーダー）
今まで、あるデータ構造が得意な処理を「一瞬で」、苦手な処理を「時間がかかる」などと表現してきました。これはこれでわかりやすくていいのですが、もっと定量的な表し方が欲しくなります。
そこで、計算量（オーダー）という考え方が登場しました。計算量は、その処理がどれぐらい時間がかかるのかを表したものになります。計算量の表記では、「オーダー」の頭文字であるOを使い、データ数をnとしたとき、O(1)やO(n)のような表し方をします。かっこの中が大きければ大きいほど処理が遅いということになります。
O(1)は定数オーダーとも呼ばれ、どんなにデータが巨大でも、処理速度が一切変わらないことを示します。例えば配列で言えば「ある添え字に対する数値を取り出す」がO(1)となります。配列の長さが50でも100万でも、array[5]の速度は変わりませんから。
O(n)はデータ数nに比例して時間がかかる処理を表します。例えば「配列に数値123が含まれるか？」は最悪の場合の計算量がO(n)になります（n個のデータを調べないといけないため）。
他にもO(nlogn)や、O(n^2)といったものも存在します。
オーダーは余計な値を排除して、支配的なもののみを残します。例えばO(5n)のようなオーダーになった時、定数倍は無視して単にO(n)とだけ表記します。他にも、O(n^2 + n)の場合は、一番影響の大きいn^2だけを残してO(n^2)と表記します。
いろんなデータ構造
連結リスト
値の集合を表現する方法は配列だけではありません。連結リスト（Linked List）というものもあります。
配列はまとまった領域に値を詰めていくイメージでしたが、連結リストは要素ひとつひとつは独立していて、それらの要素を線でつないでいくイメージです。
このとき、各要素が「次の要素」の情報だけを持っているときは片方向連結リストと呼び、「前の要素」「次の要素」の両方の情報を持っているときは双方向連結リストと呼びます。
連結リストは、リンクをつなぎ変えるだけで構造を変えることができるため、先頭への値の追加が容易であるという特徴を持ちます。新しい値を先頭に追加するときは、新しい値A’からAへのリンクをはるだけなので、O(1)で済みます。
その一方で、特定の番号の要素にアクセスするのは苦手です。先頭となる要素から順番に辿っていかないといけないからです。途中の要素にアクセスする操作は、O(n)のオーダーになります。
つまり、連結リストは配列と似た構造を持ちながら、配列とは真逆の性質を持ちます。配列はn番目の要素にアクセスするのにはO(1)ですが、連結リストではO(n)です。先頭に値を追加する操作は、配列ではO(n)になりますが、連結リストではO(1)です。
JavaScriptにおいては配列も容易に値を追加できる（他の言語の配列はそうではありません！）ので、連結リストのメリットは薄く感じますが、例えばどんどん先頭に値を追加していく場合などは、JavaScriptにおいても連結リストが有効です。先頭に値を追加する場合、配列はほかのすべての要素をひとつずつ番号をずらさないといけませんが、連結リストでは先頭に付け加えるだけだからです。
連結リストはJavaScriptの標準では用意されていませんが、簡単に作ることができます。例えば以下のようにします：
'use strict';
// 連結リストの要素
class LinkedListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
// 連結リスト
class LinkedList {
constructor() {
this.head = null;
}
// 末尾に要素を追加する
push(value) {
const node = new LinkedListNode(value);
if(!this.head) {
this.head = node;
return;
}
let current = this.head;
while(current.next) {
current = current.next;
}
current.next = node;
}
// 先頭に要素を追加する
unshift(value) {
const node = new LinkedListNode(value);
node.next = this.head;
this.head = node;
}
// 文字列化
toString() {
const array = [];
let current = this.head;
while(current) {
array.push(current.value);
current = current.next;
}
return array.toString();
}
}
const list = new LinkedList();
list.push(1);
list.push(2);
list.push(3);
list.push(4);
console.log(list.toString());これを使って、実際に配列との比較をしてみましょう。以下の4つを比較します：
- 配列のpush（末尾へのデータ追加）
- 配列のunshift（先頭へのデータ追加）
- 連結リストのpush（末尾へのデータ追加）
- 連結リストのunshift（先頭へのデータ追加）
以下のような計測コードを書きます：
'use strict';
// 連結リストの要素
class LinkedListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
// 連結リスト
class LinkedList {
constructor() {
this.head = null;
}
// 末尾に要素を追加する
push(value) {
const node = new LinkedListNode(value);
if(!this.head) {
this.head = node;
return;
}
let current = this.head;
while(current.next) {
current = current.next;
}
current.next = node;
}
// 先頭に要素を追加する
unshift(value) {
const node = new LinkedListNode(value);
node.next = this.head;
this.head = node;
}
// 文字列化
toString() {
const array = [];
let current = this.head;
while(current) {
array.push(current.value);
current = current.next;
}
return array.toString();
}
}
// 関数funcを100回実行した時にかかる時間を計測する関数
function measureTime(func) {
const startTime = performance.now(); // 開始時間
for(let i = 0; i < 100; i++) {
func();
}
const endTime = performance.now(); // 終了時間
const elapsedTime = endTime - startTime; // 経過時間
return elapsedTime;
}
// 配列の末尾に値を追加する
function arrayPush() {
const array = [];
for(let i = 0; i < 1000; i++) {
array.push(i);
}
}
// 配列の先頭に値を追加する
function arrayUnshift() {
const array = [];
for(let i = 0; i < 1000; i++) {
array.unshift(i);
}
}
// 連結リストの末尾に値を追加する
function linkedListPush() {
const list = new LinkedList();
for(let i = 0; i < 1000; i++) {
list.push(i);
}
}
// 連結リストの先頭に値を追加する
function linkedListUnshift() {
const list = new LinkedList();
for(let i = 0; i < 1000; i++) {
list.unshift(i);
}
}
// それぞれ計測する
const arrayPushTime = measureTime(arrayPush);
const arrayUnshiftTime = measureTime(arrayUnshift);
const linkedListPushTime = measureTime(linkedListPush);
const linkedListUnshiftTime = measureTime(linkedListUnshift);
// 結果を表示する
console.log(`Array.push ${arrayPushTime.toFixed(2).padStart(10)}`);
console.log(`Array.unshift ${arrayUnshiftTime.toFixed(2).padStart(10)}`);
console.log(`LinkedList.push ${linkedListPushTime.toFixed(2).padStart(10)}`);
console.log(`LinkedList.unshift ${linkedListUnshiftTime.toFixed(2).padStart(10)}`);これを実行すると、それぞれの処理の計測結果が表示されます。簡易的なものなので厳密な速度差は出ませんが、おおまかな傾向はつかめるはずです。
だいたい以下のような結果になります：
配列への末尾へのデータ追加と、連結リストへの先頭へのデータ追加がほぼ同じぐらいですね。また、配列への先頭へのデータ追加は、末尾への追加に比べて数倍遅いことがわかります。そして連結リストの末尾への追加は飛び抜けて遅いです。
このように、データ構造を少し変えるだけで、処理の速度というのは大きく変わってしまいます。
二分木と二分探索木
配列や連結リストは要素を横に並べるだけでしたが、もう少し複雑なデータ構造も存在します。
木（Tree）と呼ばれるデータ構造は、各データが複数の子データを持ちます。以下の図を見てください：
この図の場合、データAがBとCという子を持ち、さらにBがDとEという子を持っています。こういった構造のことを木（Tree）と呼びます。
特にこの場合、各データが2つまでの子を持つので、二分木（Binary Tree）と呼びます。なお、4分岐していれば「四分木」、8分岐していれば「八分木」です。
木では、各データのことをノードと呼びます。ノードはいくつかの子を持ち、二分木の場合は2つまでの子ノードを持ちます。
JavaScriptにおいて木は標準では使えませんが、簡単に自作することができます。たとえば二分木を作る場合は以下のようにします：
'use strict';
// 二分木のノード
class BinaryTreeNode {
constructor(value) {
// そのノードの値
this.value = value;
// 左の子ノードと右の子ノード
this.left = null;
this.right = null;
}
}
// ノードを作る
const a = new BinaryTreeNode('A');
const b = new BinaryTreeNode('B');
const c = new BinaryTreeNode('C');
const d = new BinaryTreeNode('D');
const e = new BinaryTreeNode('E');
// 各ノードをつなぐ
a.left = b;
a.right = c;
b.left = d;
b.right = e;
// ノードAから左->右と辿ったところの値を表示する。
console.log(a.left.right.value); // 'E'二分木はこのままでは大した意味は持たないのですが、うまく工夫すると面白いことができます。
自分の値以下のものを左に、自分の値以上のものを右に置くというルールを決めて二分木を作ります。例えば以下の図のようにです：
このときの二分木のことを二分探索木(Binary Search Tree)と呼びます。
二分探索技は特定の値を高速に探すことができます。たとえば「30」を探すとき、最初のノードから探索を始めて「30は50より小さいから左」「30は10より大きいから右」「30は30と同じ」と3ステップで終わります。これが例えば木ではなく配列[50, 5, 10, 80, 30]から30を探し出す処理だったら、5ステップかかります。
木の高さ（階層数のこと）は、理想的に左右のバランスがとれている場合はデータ数nの対数をとってlognなので、logn回ノードをたどれば探索が終わります。よってオーダーはO(logn)となります。O(logn)はO(n)より小さいオーダーになります。実際先ほど配列で5ステップかかっていた探索が3ステップで終わっていますね。
ただし、左右にバランスよく配置しないと、極端な話、木がまったくの一直線になってしまい、最悪計算量は配列での探索と同じだけのO(n)になってしまいます。
ちなみに左右のバランスがいい二分木のことを平衡二分木と言います。
また、配列への値の追加はJavaScriptの場合O(1)で済みますが、二分探索木への値の追加は、木をどんどんたどって適切な場所を見つけないといけないため、平衡状態では木の高さ（logn）分だけかかるのでO(logn)、一直線に偏った最悪の状態でO(n)かかります。
配列と比べ、探索コストは圧倒的に安いですが、値の追加コストは高め、という特徴を持つのが二分探索木になります。
二分探索木をJavaScriptのコードで書くと以下のようになります：
'use strict';
// 二分木のノード
class BinaryTreeNode {
constructor(value) {
// そのノードの値
this.value = value;
// 左の子ノードと右の子ノード
this.left = null;
this.right = null;
}
}
// 二分探索木
class BinarySearchTree {
constructor() {
this.root = null; // 一番上のノード
}
// ノードの追加
addNode(node) {
// まだrootノードがなければそれを一番上のノードとする
if(!this.root) {
this.root = node;
return;
}
// rootノードがあれば、rootからどんどんたどっていく
// nullにあたったら終わり
let current = this.root;
let direction = node.value < current.value ? 'left' : 'right';
while(current[direction]) {
current = current[direction];
direction = node.value < current.value ? 'left' : 'right';
}
// 空いてる部分にノードを追加する
current[direction] = node;
}
}例題
例題：Math.random()でランダムな数値を100万個作り、配列と二分探索木に数値を追加せよ。次に、配列と二分探索木それぞれから値「2」を探し、探索にかかったステップ数をカウントして表示せよ。
この問題は、実際にデータを追加して動かしてみるだけです。Math.random()は0.0から1.0未満の数値を生成しますが、「2」を探索するため見つからず、途中では終わらないので時間のかかる処理になるはずです。
例えば以下のようなコードになります：
'use strict';
// 二分木のノード
class BinaryTreeNode {
constructor(value) {
// そのノードの値
this.value = value;
// 左の子ノードと右の子ノード
this.left = null;
this.right = null;
}
}
// 二分探索木
class BinarySearchTree {
constructor() {
this.root = null; // 一番上のノード
}
// ノードの追加
addNode(node) {
// まだrootノードがなければそれを一番上のノードとする
if(!this.root) {
this.root = node;
return;
}
// rootノードがあれば、rootからどんどんたどっていく
// nullにあたったら終わり
let current = this.root;
let direction = node.value < current.value ? 'left' : 'right';
while(current[direction]) {
current = current[direction];
direction = node.value < current.value ? 'left' : 'right';
}
// 空いてる部分にノードを追加する
current[direction] = node;
}
}
// 100万個のデータを作って配列と二分探索木に追加する
const dataNum = 100 * 10000;
const array = [];
const tree = new BinarySearchTree();
const searchTargetValue = 2;
for(let i = 0; i < dataNum; i++) {
const value = Math.random();
array.push(value);
tree.addNode(new BinaryTreeNode(value));
}
// 配列の探索と、二分探索木の探索のステップ数をそれぞれ数える
let arraySteps = 0;
let treeSteps = 0;
// 配列
for(let i = 0; i < dataNum; i++) {
arraySteps++;
if(array[i] === searchTargetValue) {
break; // もし値が見つかったら抜ける
}
}
// 二分探索木
let current = tree.root;
while(current) {
treeSteps++;
if(current.value === searchTargetValue) {
break; // もし値が見つかったら抜ける
}
current = searchTargetValue < current.value ? current.left : current.right;
}
console.log(`配列の探索には ${arraySteps} ステップかかりました`);
console.log(`二分探索木の探索には ${treeSteps} ステップかかりました`);これを実際に実行してみると、配列の探索には100万ステップ、二分探索木の探索には10から50ステップ程度かかるはずです。二分探索木からデータを探す方が圧倒的に早いですね。
配列は最悪の場合は最初から最後まで全部の値を見てみないとその値が含まれているかどうかわからないですが、二分探索木なら木の高さ分だけ見ればいいので、高速に終わります。
しかし、ランダムな値でやっている上に、平衡を意識していない二分探索木になるので、悪い値が出る場合もあります。何度か繰り返し実行してみて、結果を確認してください。
アルゴリズム
「アルゴリズム」という言葉は、プログラマでない人でも聞いたことがあるのではないでしょうか。アルゴリズムとは計算の手順・問題の解き方のことであり、プログラミングの根幹に深く関わってきます。
データ構造の選択が処理速度に多大な影響を与えたように、アルゴリズムの選択も性能面で大きなインパクトを与えます。良いアルゴリズムを選択すれば処理は高速に終わりますし、悪いアルゴリズムを選択してしまうといつまでたっても処理が終わりません。
アルゴリズムは世の様々な問題に対して考案されていますが、今回は配列のソートに絞って紹介します。
配列のソート
配列のソート（並び替え）は様々なアルゴリズムが考案されています。小さな値を先頭に、大きな値を末尾に（あるいはその逆）。ただそれだけのことですが、多くのアプローチが存在します。
最も素朴なソートアルゴリズムは、前から順番に見ていって、大きな値を後ろに持ってくる、バブルソートと呼ばれるアルゴリズムです。泡が水の底から浮かび上がってくるように、値がどんどん上がってくることからこの名前がつけられました。
バブルソートでは、小さい順にソートする場合は以下のような手順を踏みます：
- 1番目の要素と2番目の要素を比較し、小さい方を1番目に、大きい方を2番目に入れ替える
- 2番目の要素と3番目の要素を比較し、小さい方を2番目に、大きい方を3番目に入れ替える
- …
- n-1番目の要素とn番目の要素を比較し、小さい方をn-1番目に、大きい方をn番目に入れ替える
- n番目（末尾）が最大であることが確定するので固定する
- 1番目からn-1番目について同じことを行う（入れ替えを繰り返して最後の値を固定）
- 1番目からn-2番目について同じことを行う
- …
- 1番目から2番目について同じことを行う
- 全ての値が固定されたので終了
これをJavaScriptで実装すると以下のようになります：
'use strict';
// 配列をバブルソートする関数
function bubbleSort(array) {
const n = array.length - 1;
// end = n, n-1, n-2, n-3, ..., 3, 2, 1
for(let end = n; end > 0; end--) {
// i = 1, 2, 3, ..., end-2, end-1
for(let i = 0; i < end; i++) {
// 交換する
if(array[i] > array[i+1]) {
[array[i], array[i+1]] = [array[i+1], array[i]];
}
}
}
}
const array = [7, 5, 10, 3, 4];
bubbleSort(array);
console.log(array); // [3, 4, 5, 7, 10]実にシンプルですね。比較して、交換するだけです。バブルソートはその単純さが特徴です。
ただし計算量は悪く、O(n^2)となります。配列がn個の要素を持つ場合、最後の値を確定するのにn-1回の比較が必要になります。次に最後から2番目の値を確定するのにn-2回の比較、というのを繰り返します。すると等差数列の和より：
(n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 = n(n-1)/2
という風になり、中にn^2が出てくるのでO(n^2)です。
クイックソート
クイックソートは、名前の通り高速なソートアルゴリズムです。
クイックソートの基本的なアイデアは以下のようなものです：
- 基準となる値を一つ決める。これを「ピボット」と呼ぶ。
- 配列の前半に「ピボットより小さな値」を集め、配列の後半に「ピボットより大きな値」を集める。
- 配列の前半と後半について、それぞれ”クイックソート”を行う。
クイックソートの面白いところは、クイックソートの定義の中にクイックソートが出てくることです。いわゆる再帰処理になります。
これをJavaScriptで実装すると以下のようになります：
'use strict';
// 配列をクイックソートする関数
function quickSort(array, start, end) {
// startとendが逆転していたら終わり
if(end <= start) {
return;
}
// ピボットは先頭のものにする
// ※本来はもう少し注意深くピボットを選ぶ
const pivot = array[start];
// 配列の前半と後半に振り分ける
let left = start;
let right = end;
while(true) {
while(array[left] < pivot) { left++; } // pivot以上の値を左から探す
while(array[right] > pivot) { right--; } // pivot以下の値を右から探す
if(left >= right) { break; } // leftとrightが逆転したらwhileを抜ける
[array[left], array[right]] = [array[right], array[left]]; // 値の入れ替え
left++;
right--;
}
// 配列の前半と後半をそれぞれクイックソート
quickSort(array, start, left - 1);
quickSort(array, right + 1, end);
}
const array = [10, 7, 1, 6, 12, 10, 8, 9];
quickSort(array, 0, array.length - 1);
console.log(array); // [1, 6, 7, 8, 9, 10, 10, 12]クイックソートは、データの並びやピボットの選び方によっては非常に高速に動作します。ピボットを中心に綺麗に分かれてくれると、分割の深さはlogn、データ数はnなので、O(nlogn)で済みます。
一方でピボットの選び方が悪かったり、データの並びがクイックソート向けではない（例えばすでにソート済みの配列など）と、分割が偏って、logn部分がnまで膨れ上がり、O(n^2)となります。ただし一般的なデータにおいてO(n^2)かかることは、まずありません。
いろいろなソート
ソートアルゴリズムは他にも多数存在します。例えば、最悪計算量O(nlogn)で使いやすいマージソート、ヒープというデータ構造を使ったヒープソート、比較を使わずソートするバケットソート、など様々です。
ちなみに、JavaScriptには配列にsortメソッドが存在しますが、sortメソッドはブラウザに依存し、内部的にはマージソートや、ティムソートと呼ばれるものを使用しています。
例題
例題：大量のランダムな要素（1万個以上）を持つ配列を用意し、バブルソートとクイックソートの実行時間を比較せよ。
これは上で書いたアルゴリズムの時間を計測するだけです。
'use strict';
function bubbleSort(array) {
const n = array.length - 1;
for(let end = n; end > 0; end--) {
for(let i = 0; i < end; i++) {
if(array[i] > array[i+1]) {
[array[i], array[i+1]] = [array[i+1], array[i]];
}
}
}
}
function quickSort(array, start, end) {
if(end <= start) {
return;
}
const pivot = array[start];
let left = start;
let right = end;
while(true) {
while(array[left] < pivot) { left++; }
while(array[right] > pivot) { right--; }
if(left >= right) { break; }
[array[left], array[right]] = [array[right], array[left]];
left++;
right--;
}
quickSort(array, start, left - 1);
quickSort(array, right + 1, end);
}
const array1 = [];
const array2 = [];
for(let i = 0; i < 10000; i++) {
const value = Math.random();
array1.push(value);
array2.push(value);
}
const bubbleStart = performance.now();
bubbleSort(array1);
const bubbleEnd = performance.now();
const bubbleTime = bubbleEnd - bubbleStart;
const quickStart = performance.now();
quickSort(array2, 0, array2.length - 1);
const quickEnd = performance.now();
const quickTime = quickEnd - quickStart;
console.log(`Bubble Sort: ${bubbleTime}`);
console.log(`Quick Sort : ${quickTime}`);データの偏り方にもよりますが、一般的にクイックソートのほうが高速なはずです。
今回のまとめ
今回はデータ構造とアルゴリズムという、すこし専門的なお話をしました。
データ構造はその名の通りデータの構造です。構造を少し変えるだけで処理のオーダーが変わり、何十倍も速くなったりしました。やりたいことによって適切なデータ構造を選ぶことができれば、効率の良いプログラムが書けそうです。
アルゴリズムは処理の手順です。やり方が良ければすぐに処理は終わりますし、やり方が悪ければ処理はなかなか終わりません。この記事ではソートアルゴリズムしか紹介しませんでしたが、古今東西で様々なアルゴリズムが考案されているので、一度調べてみるのもいいかもしれませんね。
例題
例題1
例題：スタックというデータ構造がある。スタックは配列のようにデータを蓄積するが、積み上げ（push）と、一番最後にpushされたデータの積み下ろし（pop）の2種類しか操作が存在しない。Stackクラスを実装せよ。また、Stackクラスを実際に使用してみよ。
スタックはシンプルなデータ構造です。積み上げと積み下ろししか存在しません。JavaScriptでは配列にpushメソッドとpopメソッドがあるので、そのまま使いましょう。
'use strict';
class Stack {
constructor() {
this._data = [];
}
push(data) {
this._data.push(data);
}
pop() {
return this._data.pop();
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());例題2
例題：ソート済みの配列があるとする。このとき、配列の中からある値を探しだす方法として、二分探索（バイナリサーチ）という手法が使える。
- 配列の真ん中の値を見て、同じならtrueを返し終了する。真ん中より小さければ左半分を二分探索し、真ん中より大きければ右半分を二分探索する。
- 最後まで見つからなければfalseを返す
これを実装し、動作を確かめよ。
クイックソートでも出てきた再帰ですね。そのまま愚直に実装します：
'use strict';
function binarySearch(array, target, start, end) {
// startとendが逆転したら終わる
if(start > end) {
return false;
}
// 真ん中のインデックスを計算する
const center = Math.floor((start + end) / 2);
// 半分ずつ探す
if(array[center] > target) {
return binarySearch(array, target, start, center - 1);
} else if(array[center] < target) {
return binarySearch(array, target, center + 1, end);
} else {
return true;
}
}
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arrayIncludes2 = binarySearch(sortedArray, 2, 0, sortedArray.length - 1);
console.log(arrayIncludes2);課題
課題1（homework5-1.js）
課題：キュー（Queue）というデータ構造がある。キューは値を追加するenqueueと、一番古い値を取り出すdequeueの操作を持つ、一方通行のデータ構造である。Queueクラスを作成し、実際に使用してみよ。
- ヒント1:：キューは「待ち行列」とも呼ばれる。早く並んだものほど早く出ることができる。
- ヒント2：JavaScriptの配列には、先頭に値を追加するunshiftメソッド、最後の要素を取り出すpopメソッドがある。
課題2（homework5-2.js）
課題：配列の値を大きい順（例えば[5, 4, 3, 2, 1]）にソートする関数を作成し、適当な配列で動作を確認せよ。使用するアルゴリズムは任意とする。
- ヒント：ソート時の比較を逆にすると……？
応用課題
応用課題1（homework5-3.js）
課題：一般的に、数式を書くときは「1 + 2」のように演算子（記号）を中央に置くが、「1 2 +」のように数字のあとに演算子を置く記法も存在する。これを逆ポーランド記法という。例えば「1 + 2*3 + 4*5」は逆ポーランド記法では「123*+45*+」になる。逆ポーランド記法の文字列から結果を計算する関数を作成し、実際に動作するか確かめよ。ただし、数字は0から9までの1桁のみで、演算子は+と*のみとする。
ヒント：逆ポーランド記法はスタックを使えば、以下の手順で簡単に計算ができる。
- 文字列を先頭から順に見ていく
- 数字ならスタックにpushする
- 演算子（+や*）ならスタックから2回popし、2つの数値の演算の結果をpushする
- 最後に計算結果がスタックに残る
例えば以下のようになる：
'use strict';
// 逆ポーランド記法（Reverse Polish Notation）の文字列から
// 結果を計算する関数
// ただし数値は1桁（0〜9）のみで、演算子は+と*とする
function calcRpn(rpnStr) {
// スタックを用意する（配列にスタックのメソッドがあるので、ただの配列で良い）
const stack = [];
// 各文字について
for(const character of rpnStr) {
//
// ここを完成させる
//
}
// 最後にスタックの中に結果だけが残るので、それを返す
return stack.pop();
}
const rpn1 = '12+3+4+5+'; // 1+2+3+4+5
const rpn2 = '12+34+*5+'; // (1+2)*(3+4)+5
const rpn3 = '123*+45*+'; // 1+2*3+4*5
console.log(calcRpn(rpn1)); // 15
console.log(calcRpn(rpn2)); // 26
console.log(calcRpn(rpn3)); // 27応用課題2（homework5-4.js）
課題：いくつかの頂点（ノード）を辺（エッジ）で結んだもののことをグラフという。地図（交差点が頂点、道が辺）や、SNSでのフォロー/フォロワー関係（アカウントが頂点、フォロー関係が辺）など、現実世界にもグラフは多く存在する。また、データ構造の木もグラフの一種である。辺にはコスト（距離）を付加することができ、地理的な距離などを表すことができる。
プログラム上でのグラフの表し方は様々であるが、最もシンプルなのはコストをテーブルで表現した隣接行列である。例えば以下のグラフを隣接行列で表現する。
すると以下のようになる：
const graph = [
[0, 2, 1], // 頂点0から[頂点0, 頂点1, 頂点2]へのコスト
[2, 0, 3], // 頂点1から[頂点0, 頂点1, 頂点2]へのコスト
[1, 3, 0] // 頂点2から[頂点0, 頂点1, 頂点2]へのコスト
];なお、辺が存在しない場合はコスト「-1」として扱う。ただしマイナスのコストを扱う場面では別の表現方法を考える（※今回はマイナスコストは扱わない）。
このとき、以下のプログラムを参考に、ダイクストラ（Dijkstra）法で最短経路を求めるプログラムを作成せよ：
'use strict';
// ダイクストラ法により最短経路を算出する
// graphは隣接行列、startIndexとgoalIndexは頂点番号
function dijkstra(graph, startIndex, goalIndex) {
//
// 前準備
//
const nodeNum = graph.length; // 配列に入っている配列の数が頂点数
const distance = new Array(nodeNum); // スタート地点からの距離表を作成する
distance.fill(Infinity); // 距離を無限大で埋める
distance[startIndex] = 0; // ただしスタート地点からスタート地点への距離のみゼロ
const nodeIndexList = []; // 頂点番号リスト
for(let i = 0; i < nodeNum; i++) {
nodeIndexList.push(i); // 各頂点番号をリストに入れる
}
const previousNode = new Array(nodeNum); // 前の頂点
previousNode.fill(-1); // -1（無効）で埋める
//
// 計算
//
// 頂点番号リストが空でないあいだ
while(nodeIndexList.length > 0) {
// 頂点番号リストから、スタート地点からの距離が最小の頂点を選ぶ
// スタート地点からの総距離はdistance[nodeIndexList[i]]で取得できる
// distance[i]がdistance[minDistanceIndex]より小さい番号iを
// どんどんminDistanceIndexに入れていけば、最終的に距離が最小のiが得られる
let minDistanceIndex = 0;
for(let i = 0; i < nodeIndexList.length; i++) {
//
// 課題：ここを埋める
//
}
const nodeIndex = nodeIndexList[minDistanceIndex];
nodeIndexList.splice(minDistanceIndex, 1); // 選んだノードを削除
// 選んだ頂点（nodeIndex）から繋がっているノードの一覧を作る
// 頂点fromから頂点toへの距離はgraph[from][to]で取得できる
// 距離が0より大きければ繋がっている
// 繋がっていたら番号iをneighbourIndexListに入れる
const neighbourIndexList = [];
for(let i = 0; i < nodeNum; i++) {
//
// 課題：ここを埋める
//
}
// スタート地点からnIndexまでの現在の総距離（これをAとする）と、
// 「スタート地点からnodeIndexまでの総距離」と「nodeIndexからnIndexまでの距離」
// を足したもの（これをBとする）を比較して、
// Bが小さい場合はdistance[nIndex]をBで更新し、
// previousNode[nIndex]にnodeIndexを入れる
for(const nIndex of neighbourIndexList) {
//
// 課題：ここを埋める
//
}
}
// 答えは出たが人間が読みやすい形式ではないので
// ゴールから逆順に辿って最短経路として出す
const shortestPath = [goalIndex];
for(let prev = previousNode[goalIndex]; prev >= 0; prev = previousNode[prev]) {
shortestPath.unshift(prev);
}
return shortestPath;
}また、以下のグラフの頂点0から頂点5への最短経路を求めて表示してみよ：
その6：HTMLとDOMへ続く
次の記事 → その6：HTMLとDOM（予定）
わからないときは
この連載記事を読んで、わからないところ、不思議なところ、納得のいかないところ等出てくると思います。そのときはTwitterで@kfurumiyaまでご連絡ください。できる範囲で回答いたします。
また、Twitterを使えない、Twitterでは短すぎるという場合はメールアドレス：kotofurumiya@gmail.comまでご連絡ください。
私を信用できないという場合は、以下のプログラミング質問サイトを活用してください：