Kohei Asai

Kohei Asai

2019/10/10に投稿
  • 日本語
  • Denoの始め方 / LeetCodeの解答数が100を超えました

    北米のIT企業ではコーディング面接があり、オンラインテストだったりホワイトボードを使って解かされたりとまちまちですがお決まりのようにアルゴリズムに関する問題で候補者のレベルの足切りをすることが多いようです。

    対策しないとなーとずっと思ってたので重い腰を上げてLeetCodeで問題を解いてGitHubのリポジトリに残す、ってことをしてたらいつの間にか100問を超えてました。楽しくなってきたのでこのまま200問、300問と続けていきたいです。

    axross/leetcode-typescript
    https://github.com/axross/leetcode-typescript

    🍣 deno test solutions/ --allow-net
    Found 200 matching test files.
    running 100 tests
    OK     1. Two Sum (0.00ms)
    OK     5. Longest Palindromic Substring (0.00ms)
    OK     7. Reverse Integer (0.00ms)
    OK     9. Palindrome Number (0.00ms)
    OK     10. Regular Expression Matching (0.00ms)
    OK     13. Roman to Integer (0.00ms)
    OK     14. Longest Common Prefix (0.00ms)
    OK     20. Valid Parentheses (0.00ms)
    OK     21. Merge Two Sorted Lists (0.00ms)
    OK     26. Remove Duplicates from Sorted Array (0.00ms)
    OK     28. Implement strStr() (0.00ms)
    OK     33. Search in Rotated Sorted Array (0.00ms)
    OK     34. Find First and Last Position of Element in Sorted Array (0.00ms)
    OK     35. Search Insert Position (0.00ms)
    OK     38. Count and Say (0.00ms)
    OK     53. Maximum Subarray (0.00ms)
    OK     62. Unique Paths (0.00ms)
    OK     66. Plus One (0.00ms)
    OK     67. Add Binary (0.00ms)
    OK     69. Sqrt(x) (0.00ms)
    OK     70. Climbing Stairs (0.00ms)
    OK     78. Subsets (0.00ms)
    OK     88. Merge Sorted Array (0.00ms)
    OK     94. Binary Tree Inorder Traversal (0.00ms)
    OK     98. Validate Binary Search Tree (0.00ms)
    OK     101. Symmetric Tree (2.00ms)
    OK     102. Binary Tree Level Order Traversal (0.00ms)
    OK     104. Maximum Depth of Binary Tree (0.00ms)
    OK     111. Minimum Depth of Binary Tree (0.00ms)
    OK     112. Path Sum (0.00ms)
    OK     121. Best Time to Buy and Sell Stock (0.00ms)
    OK     125. Valid Palindrome (0.00ms)
    OK     141. Linked List Cycle (0.00ms)
    OK     144. Binary Tree Preorder Traversal (0.00ms)
    OK     145. Binary Tree Postorder Traversal (2.00ms)
    OK     146. LRU Cache (0.00ms)
    OK     153. Find Minimum in Rotated Sorted Array (0.00ms)
    OK     155. Min Stack (0.00ms)
    OK     160. Intersection of Two Linked Lists (0.00ms)
    OK     162. Find Peak Element (0.00ms)
    OK     169. Majority Element (0.00ms)
    OK     198. House Robber (0.00ms)
    OK     200. Number of Islands (0.00ms)
    OK     202. Happy Number (0.00ms)
    OK     206. Reverse Linked List (0.00ms)
    OK     222. Count Complete Tree Nodes (0.00ms)
    OK     234. Palindrome Linked List (0.00ms)
    OK     240. Search a 2D Matrix II (0.00ms)
    OK     242. Valid Anagram (0.00ms)
    OK     246. Strobogrammatic Number (0.00ms)
    OK     250. Count Univalue Subtrees (0.00ms)
    OK     256. Paint House (0.00ms)
    OK     278. First Bad Version (0.00ms)
    OK     283. Move Zeroes (0.00ms)
    OK     299. Bulls and Cows (0.00ms)
    OK     303. Range Sum Query - Immutable (0.00ms)
    OK     344. Reverse String (2.00ms)
    OK     349. Intersection of Two Arrays (0.00ms)
    OK     350. Intersection of Two Arrays II (0.00ms)
    OK     359. Logger Rate Limiter (0.00ms)
    OK     387. First Unique Character in a String (0.00ms)
    OK     389. Find the Difference (0.00ms)
    OK     394. Decode String (0.00ms)
    OK     409. Longest Palindrome (0.00ms)
    OK     412. Fizz Buzz (0.00ms)
    OK     416. Partition Equal Subset Sum (0.00ms)
    OK     438. Find All Anagrams in a String (16.00ms)
    OK     482. License Key Formatting (0.00ms)
    OK     507. Perfect Number (0.00ms)
    OK     543. Diameter of Binary Tree (0.00ms)
    OK     547. Friend Circles (0.00ms)
    OK     557. Reverse Words in a String III (0.00ms)
    OK     572. Subtree of Another Tree (0.00ms)
    OK     594. Longest Harmonious Subsequence (0.00ms)
    OK     646. Maximum Length of Pair Chain (2.00ms)
    OK     658. Find K Closest Elements (0.00ms)
    OK     695. Max Area of Island (0.00ms)
    OK     704. Binary Search (0.00ms)
    OK     733. Flood Fill (0.00ms)
    OK     746. Min Cost Climbing Stairs (0.00ms)
    OK     771. Jewels and Stones (0.00ms)
    OK     819. Most Common Word (0.00ms)
    OK     832. Flipping an Image (0.00ms)
    OK     844. Backspace String Compare (0.00ms)
    OK     845. Longest Mountain in Array (2.00ms)
    OK     929. Unique Email Addresses (0.00ms)
    OK     937. Reorder Log Files (0.00ms)
    OK     938. Range Sum of BST (0.00ms)
    OK     953. Verifying an Alien Dictionary (0.00ms)
    OK     961. N-Repeated Element in Size 2N Array (0.00ms)
    OK     997. Find the Town Judge (0.00ms)
    OK     1118. Number of Days in a Month (2.00ms)
    OK     1119. Remove Vowels from a String (0.00ms)
    OK     1143. Longest Common Subsequence (2.00ms)
    OK     1184. Distance Between Bus Stops (0.00ms)
    OK     1200. Minimum Absolute Difference (0.00ms)
    OK     1217. Play with Chips (0.00ms)
    OK     1218. Longest Arithmetic Subsequence of Given Difference (0.00ms)
    OK     1219. Path with Maximum Gold (0.00ms)
    OK     1220. Count Vowels Permutation (8.00ms)
    
    test result: OK 100 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out (46.00ms)

    最初はTypeScriptで書いてJestとts-jestでテストするって形を取っていたのですが、Denoのtestingという標準ライブラリにベンチマークを取るAPIがあったので使ってみたくてDenoでのコードに移行しました。

    Denoとは

    DenoはNode.jsの作者であるRyan DahlがNode.jsでの反省を生かして作っているTypeScriptのランタイムで、以下のような違いがあります。

    • TypeScriptがそのまま動く。(実行時にコンパイルされて動作し、2回目キャッシュが使われるという形。将来的にはTypeScriptのコンパイラを利用して逐次的にコンパイルしながら動くようにしたいとのこと)
    • ブラウザ互換性を確保する。Denoで動くJavaScriptは変更なしにブラウザでも動く
    • CommonJSではなくES Modulesでのモジュール解決をする。index.jsのようなファイルはなく、npmモジュールの代わりにURLで *import* { test } *from* "https://deno.land/std/testing/mod.ts"; のように指定する
    • トップレベル await のサポート
    • Promiseのエラーの発生時にUncaught Errorのままプログラムが動くようにせず、普通のエラーと同様にきちんと異常終了するようにする

    初めて出てきたのは 10 Things I Regret About Node.js というJSConf EU 2018でのRyan Dahl自身の発表で、Node.jsでの反省点を振り返りながらDenoの紹介をするというものでした。

    エディタの支援を受けるには

    Denoで動かせるのはJavaScriptとTypeScriptですが、Nodeで動かすものと違ってモジュールのパスが異なります。Nodeで x というnpmパッケージを読み込むには import { foo } from 'x'; のように書きますが、Denoでは代わりに下記のように書きます。

    // 標準ライブラリもURLで指定するようになっている
    import { foo } from 'https://deno.land/std/x/mod.ts';

    from 節の後ろに書く文字列はURLであり、拡張子が必須です。 相対パスでの読み込みであっても下記のように拡張子が必ず付きます。

    // Denoではスネークケースでのファイル名が主流
    import { home } from './some_module.ts';

    ブラウザでのES Modulesと同じ形にしてブラウザ互換性を確保するのが理由でこうなっています。ですが、TypeScriptのコンパイラはURLでモジュールパスを扱えず、拡張子を付けることも許していません。これはエディタでの支援を受ける際などに問題になります。

    これを解決するにはTypeScript v2.2から導入されたコンパイラプラグインの仕組みを使って解決します。自分は下記のコンパイラプラグインを利用しています。このコンパイラプラグインを利用することでURLでのモジュールパスと拡張子を許可することができます。

    GitHub - justjavac/typescript-deno-plugin: Deno language service plugin for TypeScript

    Npm経由でインストールできて、 "compilerOptions": { … } の中で "plugin" として指定するだけで利用できます。以下は tsconfig.json のサンプルです。

    {
      "compilerOptions": {
        "lib": ["esnext"],
        "strict": true,
        "noUnusedLocals": true,
        "noUnusedParameters": true,
        "noImplicitReturns": true,
        "noFallthroughCasesInSwitch": true,
        "downlevelIteration": true,
        "plugins": [{ "name": "typescript-deno-plugin" }]
      }
    }

    URLでのモジュールパスは直接HTTPアクセスしているわけではなく、DenoによってキャッシュされたローカルのTypeScriptファイルに解決時に向き先を置き換える形なので、エディタの支援を受けるには一度Denoで実行するか、 deno fetch で依存しているモジュールをダウンロードする必要があります。