見出し画像

プログラミング未経験者がRecursionで1年勉強して、OSS開発にチャレンジした話

Nori

こんにちは。Noriと申します。
2020年の半ばごろから「Recursion」でコンピューターサイエンスを勉強し始めて1年弱経ち、ある程度知識がついてきたので、木構造の1つである二分木を可視化するJavaScriptライブラリーの開発にチャレンジしました。

このライブラリー開発を通して、テーマの探し方、設計、コーディング、リリースまでを一通り経験できたので、情報を共有できればと思い記事を書きました。
5000字強と大変に長い記事となっておりますが、失敗したところなども含めて書いたので10分ほどお時間を頂けると幸いです。

はじめに

二分木を初めて聞く方もいらっしゃると思いますので、ざっくり説明します。用語集的には、

枝分かれが2つまでのツリー構造（枝分かれして広がっていく構造）のこと。
https://wa3.i-3-i.info/word14925.htmlより引用

です。

二分木のノードはJavaScriptで表すと、

class Node{
   constructor(data, left = null, right = null){
       this.data = data;
       this.left = left;
       this.right = right;
   }
}

です。ノードが左右のノードへのリンクを保持しています。このノードをつなげていくと、例えば以下のような構造になります。黄色い丸がノードです。

無題

親ノード⑥は、左側のノード④へのリンクと右側のノード⑨へのリンクを持っています。また、その左側のノード④も、左②、右⑤へのリンクを持っています。

これが何の約に立つのかと疑問に思うかもしれませんが、二分木はデータの探索に非常に大きな効果を発揮します。例えば、必ず左＜親＜右というルールで並んでいた木構造があったら、特定の数字を見つけるのに楽になると思いませんか？

このように、二分木を使えば効率的なデータ探索ができます。

ダウンロードのコピー

これが二分木です。

作成したライブラリー

前節で二分木がなんとなく理解できたかと思います。
今回作成したライブラリーは、その二分木を可視化するtree-visualizerです。製作期間は平日仕事をして約2ヶ月です。

自分が初めて二分木を勉強したときに欲しかった機能ということもあり、ライブラリーを作ることに決めました。

どういったライブラリーが少しご紹介します。

機能は木構造（二分木）の可視化です。簡易的に可視化できるように工夫しました。例えば、[1,-5,15,-9,-4,10,17,null,-6,null,0,null,14,16,19]とあらわされた二分木も、下記コードだけで可視化できます。ぜひコピペしてみてください。

<script type="text/javascript" src="https://unpkg.com/tree-visualizer/src/tree-visualizer.js"></script>
<script type="text/javascript" src="https://unpkg.com/animejs@3.2.1/lib/anime.min.js"></script>

<div id = "target"></div>
<script type="text/javascript">
   let target = treeVisualizer({target:"target"});
   target.drawData(
       [{
           data:"[1,-5,15,-9,-4,10,17,null,-6,null,0,null,14,16,19]",
       }]
   );
</script>

画像6​

他にもノードごとに色を変えたり、アニメーションにしたりと様々なオプションがあります。デモサイトもあるので見ていただけると幸いです。

この記事について

このライブラリーがどういった経緯で開発されたのか、どういったところで失敗したのか、を詳しく説明します。開発の期間は以下の通りです。

テーマの決定：1日
1回目の設計&コーディング：1か月
2回目の設計&コーディング：1か月
リリース：1週間

自分のレベル感は以下のとおりです。

大学、大学院：化学専攻（分析化学・無機化学・計算化学）
仕事：機械設計（産業機械・家電・医療機器）
プログラミング歴：約1年（2020年8月～）
学習言語：Python/JavaScript/PHP/C++/Java
Recursionでの学習内容：
  ・再帰やクラスなどの基本的な内容
  ・連結リスト、スタック、キューのようなデータ構造
  ・オブジェクト指向、デザインパターン
  ・Gitの基本的操作
  ・以下のようなポーカーゲーム等のソフトウェア開発の基礎

テーマの決定

所要期間：1日
『木構造の可視化』をライブラリーのテーマに決定

ライブラリーは使う目的があるから作るものです。自分の力試しのためだけに作ってしまうと、ただの自己満足の作品になってしまいがちだと考えました。需要があるところに聞くのが一番早く、使う目的があるので使用上の制約があり、より実践的に開発できるんじゃないかと思います。

今回私はRecursionの開発者に頼ることにしました。Recursionは少人数で開発を行っているため、付加したい機能がいろいろありながらも、なかなか開発の時間がさけないという話を聞いていました。その付加機能の一つが「木構造の可視化」です。

例えば、Recursionでは二分木に関する問題を解くことができます。しかし、入力値、出力値は以下のように配列でしか表せないので構造のイメージがすぐにはできません。

スクリーンショット 2021-04-13 21.32.09

この入力値が以下のように可視化できれば、正解の出力値[19,null,25]がどの部分を示しているのかすぐ把握することができます。

スクリーンショット 2021-04-13 21.35.27

以上のように、これが実現できれば他の学習者の助けにもなると思い、テーマを「木構造の可視化」に決定しました。


1回目の設計

所要期間：1ヶ月
木構造以外のデータ構造を可視化、ドラッグで直感的に操作できるように設計
ドラッグ操作までは実装できたが、ユーザーの操作を想定できずに断念

直感的にドラッグで操作できるようにしたいと考えました。完成イメージは、Whimsicalのような直観的な操作です。

画像3

他にも下図のような連結リストを可視化しようと考えました。

画像4

下記のようなデータの流れで実現しようとしました。

入力はJSON、Validatorで入力値をフィルタリング
↓
独自のデータ構造に変換
↑↓
変換したものをhtmlで表現／ドラッグ操作

そこで、まずはドラッグ操作を実装したことがなかったので試作しました。


限られた枠の中で広い描写領域を得るために、シフトキーで動かせる要素を変えられるようにもしました。

また、矢印の操作もできるようにしました。

ただ、この時点でこれから実装しなければいけない大きな壁に気がつきました。設計の段階では、ユーザーがドラッグ操作でデータ構造を操作する時、具体的にどういった操作をするのかまで想像していませんでした。例えば、以下のような基本操作です。

・Copy&Paste
・Delete
・Undo
・グループ化して移動

これらを実装しないと、中途半端な機能となってしまい逆に使い勝手が悪くなってしまいます。一方、実装するとしても全て初めて行うので、自分の技術力ではバグが大量発生しまうと考え、もう一度テーマを見直すことにしました。

2回目の設計

所要期間：1ヶ月
ライブラリーの使用状況を想像してからテーマを詳細まで見直す

テーマをちゃんと見直すことにしました。ここで下記のような製造業での経験が生かされました。

機械を設計するとき、特に産業機械の場合、性能の向上を図ることは当たり前ですが、意外と忘れがちなのがその機械の組み立てやすさと、メンテナンス性です。
例えば、作業者が30kgもある部品を手で持ち上げて取り付けるのは危険です。部品を分割したり、つり上げる部品をとりつけ、組み立てやすくします。また、故障時にメンテナンスしやすいようにメンテナンススペースを確保しなければ、ユーザーに長く使い続けてもらえません。

同じようにOSS(Open Source Software)も、組み立てやすさ、つまりそのライブラリーを使う人が使いやすいように、そして、メンテナンス性、つまりpull requestや、contributeしてもらえるようコードの可読性に気をつける必要があります。

そのために、使用する状況を詳しく考えてみることにしました。

Q. ライブラリー使用者がライブラリーを使う状況は？
・ライブラリーを読み込み、何かしらの入力をするだけですぐ木構造を表示できるようにする
・ライブラリー使用者のサイトテーマに合わせた色や、ダークモードなど、好みの色にあわせられるようにする。
・二分木に限るが、どんな操作でもアニメーションにする

Q. ライブラリーのエンドユーザーはどういう形で使う？
・木構造を初めて習う人が、コンテンツ内で画像を見るように、一瞬で構造がわかるようにする
・問題のデバッグで使えるようにする

以上を踏まえて、二分木の可視化に特化したライブラリーを目指すことにしました。特に、自分が理解するのに時間のかかった項目を理解しやすくすることを目標に、

・アニメーションをステップごとに分ける
・ステップ後のノードの座標、色を分析する
・ステップごとの差分をアニメーションにする


という方針にしました。

まずは、自分自身が走査の方向の理解に時間がかかったので、色を変えるアニメーションでどのノードに注目してるかわかるようにしました。


つぎに、前に作ったもののデバッグが難しかった、AVLのランダム構築をアニメーションにしました。左右のノード深さの調整に回転が含まれてるので、1次元配列と紙だけでデバッグするのは困難です。

入力は今までは以下のようにJSONで表していました。ノードごとにIDを設定して、左右のノードもIDで設定しました。作った時はJSONで木構造を設定できる良い方法だと思ったのですが、実際は1つ1つのノードの設定が必要なので非常に使い勝手が悪いです。

inputData = 
{
     "rootID":6,
     "nodes":
     [
         {"data":6, "ID":6, "leftID":4, "rightID":9},
         {"data":4, "ID":4, "leftID":2, "rightID":5},
         {"data":9, "ID":9, "leftID":null, "rightID":null},
         {"data":2, "ID":2, "leftID":null, "rightID":3},
         {"data":5, "ID":5, "leftID":null, "rightID":null}
     ]
 }

そこで、二分木を一次元的に表した文字列で入力できるようにしました。

inputData = "[6,4,9,2,5,null,null,null,3]"


その結果非常に楽に木構造を表現させることができました。

そして、最終的に実際の使用環境を想定してテストしたところ、同じページに複数の描写領域がある場合バグが生じることがわかりました。原因は単純で、HTMLのIDが重複していたからです。描写領域ごとにIDを設定することで解決しました。

完成したものが下記です。

リリース

所要期間：1週間
npmに登録し、ライブラリーはCDNリンクを使ってもらうことに決定。

ライブラリーとして使ってもらうには、JavaScriptの場合は、

・npm installでインストールする
・ソースコードをダウンロードする
・CDNリンクを挿入する

など色々方法はあります。

今回は、練習もかねてCDNリンクを使ってもらうことにしました。

理由は、

・npmにアップロードすれば自動的にCDNリンクが生成される
・Browser Clientで使え、特にソースコードをあらかじめダウンロードしなくても使える

からです。

下記コードのように依存するライブラリーも一緒に挿入してもらう必要がありますが、バージョンの指定もできるので使い勝手が良いと思います。

<script src="https://unpkg.com/tree-visualizer/src/tree-visualizer.js"></script>
<script src="https://unpkg.com/animejs@3.2.1/lib/anime.min.js"></script>

まとめ

プログラミングを始めて1年弱で開発ができたのは、Recursionで体系的にコンピューターサイエンスとソフトウェアの設計方法などを学んだからです。モチベーションが上がらない時でも、他のメンバーが頑張って学習しているのを見て自分も頑張ろうという気になりました。

そして、このライブラリーの開発後を通して自分の成長を感じました。他の人のソースコードを読んで構造を理解するだけでなく、こういう意図があるんじゃないかと思えるようになったのです。今回完成に至るまで何度もコードを描き直し、使わなかったコードもたくさんあります。しかし、それは無駄ではなく、結果として次につながる糧となりました。

皆さんもぜひ、最初失敗しても諦めずにOSS開発に挑戦して欲しいと思います。

ここまで読んでいただきありがとうございました。
以上となります。


この記事が気に入ったらサポートをしてみませんか？