アルゴリズムとデータ構造をJSで学ぶための下準備

1.はじめに

1.1.目的

アルゴリズムとデータ構造（以下、アルゴリズム）の学習をJavaScript(TypeScript)で行うにあたり、その下準備（環境構築）を行った。本記事ではその紹介を行う。

1.2.対象者

アルゴリズムの学習をJSを使って始める方。特に、Webフロント開発でしかJSを使ってこなかった方。

2.JSでアルゴリズムを学習するために行った準備

2.1. node, ts-node を使用してコマンドラインからファイルを実行する

　気軽にコードを実行できる環境を用意したかった。

　アルゴリズムの学習には、ウェブフロントエンド開発のような複雑な開発環境は必要ない。そのためChromeのようなブラウザは不要足モジュールバンドラの類も不要だ。必要な実行環境は、テキストエディタとNode.jsの２つだけ。コードを書くことに専念するため、必要なものは少ない方が望ましい。
　
　オンラインエディタについては、テスト（後述）ができない/手間を要するため、避ける。
　もしTypeScriptを使用するのであれば、ts-node をオススメする。これはjsファイルをNode.jsで実行するように、tsを実行してくれるnpmパッケージだ。以下のように使用する。ビルドファイルを生成することなく.tsファイルを走らせることができる。

1

$ npx ts-node xxx.ts

2.2.VSCode + Jest + JSDoc

　快適にコードを書きたかった。そのためにテストツールの導入(Jest)とタイプヒンティングのためのJSDocの導入を行った。
　
　LeetCodeなどの競技プログラミングサイトにはアルゴリズム学習コンテンツが併設されており、そこでは基礎的な学習を行うことができる。自分の書いたコードを提出すると、採点プログラムが実行され、自分のコードの正当性や速度・メモリ使用率といった結果が算出される。
　
　この採点時に、プログラムの正誤判定を行うために、数百〜数千のテストがサーバー上で実行されるのだが、この採点には少し時間がかかる。そのため自分の環境下で気楽にテストができることが望ましい。そのためのテストツールである。
　
　テストツールについては、現在のフロント開発のデファクトとであるJestを使用することで問題ないと考えている。 TSを使用する場合はts-jestを使用する必要がある。
　
　JestプラグインをVSCodeで使用することで、リアルタイムテストが可能となる。このプラグインはコードの変更を瞬時に観測し、テスト結果を表すシンボルをコード上に表示する。アルゴリズムの変更やリファクタリングを行う上で大変便利だ。

VSCode上でのJestオートラン。緑色のチェックマークがついているテストは成功を意味指定おり、赤色のバツ印は失敗を意味している。テストを書き換える度に自動で印が変化する。

　TSではなくJSを使用する場合は、手間ではあるがJSDocも記述するとよい。VSCode上で設定を行うことで、型エラーを検出してくれる。

VSCode上でのJSDocによるエラーヒント。本来stringをreturnすべき箇所でbooleanを返しているため、コード上に赤線が出現している。

2.3.ローカルでのベンチマーク計測はしなくてよい

　より優れたアルゴリズムを探求するために、Benchmark.jsをインストールして計測を行ってみた。
　しかしながら、結局断念した。機能が豊富でよいのだが、テストコードを書く手間がかかるためだ。

　LeetCodeのでは実行速度を出力してくれるので、それで十分だと判断した。Jestでユニットテスト用のコードも書いているため、これに加えてベンチマーク用のテストコードも用意するとなると、本末転倒になりかねない。

　またConsole.time()を使用してラッパー関数の作成も考えたがこれも手間であるわりに結果を得られる保証がない。ひとまず現在のところは、実装したコードに対してBig-O notationを考え、どの程度の処理量になるのか把握できていればそれだけで十分だと考えている。

LeetCodeのSubbmissionタブ。提出した時系列順にコードの情報が表示されている。

LeetCodeのSubmission Detail画面。全ユーザーのコードの実行結果が表示される。自分のコードがどれだけ優れているのか、他者と比較できて面白い。

2.4.Github上にパターンをまとめたリポジトリが存在する

　JSを使用して競プロやアルゴリズムの学習を行う人は多くないと思う。しかしわずかではあるが、自身が書いたJSのアルゴリズムコードを集約してGithubにあげているものが存在する。
　またJSでアルゴリズムを学習するための本（英語）が存在したり、LeetCode上では他者のコードを参照することができたりと、競プロ界隈ではマイナーなJSでもサンプルコードを確認することができる。

2.5. MDNやTS公式を参考にする

　アルゴリズムの知識とは別にJavaScriptの文法や関数といった知識が必要になることが多い。そのため信頼することのできるリファレンスを用意することは重要だと感じる。

　JavaScriptを使用するのであればMDNやJAVASCRIPT.INFOといったサイトがとても参考になる。

　TypeScriptを使用するのであれば定番ではあるがTypeScript公式か、もしくはTypeScriptDeepDiveが参考になる。

　リファレンスサイトを知っていなくても問題ないのだが、ふと調べ物をしたいときにGoogle検索を行うと、いわゆる「いかがでしたか記事」がとても多くヒットするため、精神衛生上の問題からこれらのサイトを意識しておくとよいかもしれない。

　そのほか、DiscordのJS, TSチャンネルの過去ログなども漁ってみると、いろいろなことがわかるかもしれない。

2.6. 専用リポジトリを用意して学習の足跡をつける

　どんなにやる気があったとしてもモチベーションの波をコントロールし続けることは難しいので、少しでも自分の成果を確認・肯定できるようにコードを一括管理しておくとよい。Githubであれば草が生えるので、進捗管理に最適だ。

　またLeetCodeでは提出した全コードが保管されるので、こういった競プロサイトを活用して管理するのもよいかもしれない。

LeetCodeのアカウントプロフィール画面より。提出した日別で草が生える。まだ四日目。

3.おわりに

jQueryの生みの親として著名なエンジニアJohn Resigは、自身のブログの中で以下のように語っています。

I realized that the feeling of making progress is just as important as making actual progress. This was an eye-opener. Once I started to make consistent progress every day the anxiety started to melt away.
John Resig - Write Code Every Day

手間ですが専用のリポジトリを作って足跡を残しておいた方が長続きするかもしれません。

以上です。

補足

補足1. Benchmark.js のサンプルコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


const Benchmark = require('benchmark')
const aryFuncs = require('./array')
const { twoSum, twoSum2 } = aryFuncs

const suite = new Benchmark.Suite()
suite.add('twoSum2', function(){
    twoSum2([3, 4, 9, 2], 11)
}).add('twoSum', function(){
    twoSum([3, 4, 9, 2], 11)
}).on('complete', function () {
    console.log(this.filter('fastest').map('name'))
}).run()

補足2.JSDocによる高階関数の定義

1
2
3
4
5
6


/**
 * To check a number in a range
 * @param {number} max 
 * @returns {(min: number) => (x: number) => boolean}
 */
const outOfRange = (max) => (min) => (x) => (x <= min) || (max <= x)

https://github.com/jsdoc/jsdoc/issues/1286

補足3.Jest使用時に発生した注意点

JestではundefinedがtoBeFalthy()にもマッチするため注意が必要
うっかり無限ループを書いてしまうとJestのオートランが延々と走り続けるので注意