ホーム / JavaScript /

フロントエンド技術を学ぼう 2-20.JSを通じてコンピュータサイエンスについて学ぶ

2020年7月25日土曜日

Front-end Developer Handbook JavaScript

t f B! P L

Front-end Developer Handbook 2017を教科書にフロントエンド周りの技術を習得する連載。

第30回はPart II: Learning Front-End Devから、20項のLearn Computer Science via JSを紹介します。

JSを通じてコンピュータサイエンスについて学ぶの説明です。


JSを通じてコンピュータサイエンスについて学ぶ

計算機科学(computer science, コンピュータ科学)とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。


つまり、情報を効率的に扱うために、以下の様な分野の理解と応用を意味します。

  • 計算機としてのコンピュータそのものの仕組み
  • プログラミング言語に依らないデータの扱い方であるアルゴリズム
  • データの集まりを体系化したデータ構造

フロントエンドエンジニアとしてJavaScriptで学ぶべきコンピュータサイエンスとは、Webサイトやアプリケーション制作に活きる、データ構造とアルゴリズムです。

参照元 : 計算機科学(Wikipedia)


データ構造

バイナリツリー



バイナリツリー(binary tree)とは、二分木や二進木とも呼ばれ、ノードが持つ子の数が最大2つのデータ構造です。バイナリサーチや二分ヒープを実装するために使われます。

参照元 : 二分木


片方向リスト

片方向リスト(singly-linked list)とは、連結リストの種類のうち最も単純なものです。各ノードには次のノードへのリンク1つが存在し、最後尾のノードにはヌル値または空のリストへのリンクを挿入します。

参照元 : 連結リスト


双方向リスト

双方向リスト(doubly-linked list)とは、連結リストの種類のうちの一つ。各ノードには次のノードへのリンクと、後ろのノードへのリンクの2つが存在します。先頭/最後尾のノードには後方/前方リンクにヌル値または空のリストへのリンクを挿入します。

参照元 : 連結リスト


ハッシュテーブル

ハッシュテーブル(hash table)とは、キーと値の組(エントリ)を複数格納し、キーに対応する値をすばやく参照するためのデータ構造です。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つです。

参照元 : ハッシュテーブル


最大ヒープ

最大ヒープ(max heap)とは、二分木を使って作られる二分ヒープ(データ構造)の一つです。特徴は以下の2点です。

  • 各ノードは子よりも大きいか等しくなるように配置される(heap property)
  • 木は完全にバランスの取れた二分木(すべての葉が同じ高さ)、そうでない場合はノードを左から右へ順に埋める（shape property）

参照元 : 二分ヒープ


キュー


キュー(queue)とは、データを先入れ先出しのリスト構造で保持するものです。キューからデータを取り出すときには、先に入れられたデータから順に取り出されます。プリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられます。

参照元 : キュー (コンピュータ))


スタック


スタック(stack)とは、データを後入れ先出しのリスト構造で保持するものです。割込みやサブルーチンを支援するために用いられます。

参照元 : スタック


アルゴリズム

バイナリサーチ

バイナリサーチ(binary search)とは、二分探索や二分検索とも呼ばれ、ソート済み配列に対する探索アルゴリズムの一つです。ソート済みのリストや配列に入ったデータ(同一の値はないもの)に対し、検索したい値が中央の値の右にあるか、左にあるかを判断ながら検索していきます。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには用いることはできません。

参照元 : 二分探索


マージソート

マージソートとは、ソートのアルゴリズムです。既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というものです。ランダムなデータでは、クイックソートのほうが速くなります。

  1. データ列を分割する（通常、等分する）
  2. 各々をソートする
  3. 二つずつソートされたデータ列をマージする

参照元 : マージソート


クイックソート

クイックソート(quicksort)とは、ソートのアルゴリズムです。他のソート法と比べて最も高速だといわれていますが、対象のデータの並びやデータ数によっては必ずしも速いわけではなく、最悪の場合はとても遅くなります。

  1. 適当な数(ピボット)を選択する(データ総数の中央値が望ましい)
  2. ピボットより小さい数を前方、大きい数を後方に移動させる(分割)
  3. 二分割された各々のデータを、それぞれソートする

参照元 : クイックソート


JavaScriptでの表現

今まで見てきたデータ構造やアルゴリズムをJavaScriptで表現してあるのが以下の2つのGithubページです。それぞれの概念が実際にどの様にコードで実装されているかを読み解いておきましょう。


QooQ