TypeScriptでMapとSetを書いてみた

ハッシュテーブル


最近個人ブログ的なものに回帰する人たちがちらほらと見られるので、自分も遊びがてらにサイトを作り直しつつ、ブログっぽいものを作ってみました。

データは GitHub に Markdown で置いておき、Next.js で配信するといった感じです。  
インフラは Vercel を使ってみています。
Next.js をちゃんと使ってみるのと、Web の勉強や実験の場所にするという目的もあります。

やりたいことはこんな感じです:

- OGP とか設定してみる
- サイトのパフォーマンスを測ったりそれをもとに改善したりしてみる
- Markdown を拡張して Scrapbox 的な記法を導入し、ページ間のつながりを表現してみる
  - タグ的な概念を導入せずにタグ的な機能を実現したい
  - 関連記事を表示したい
  - 要するに、Scrapbox の機能の一部を自分で実装してみたい

週に 1 回くらいは何か書いていきたいと思います。


個人サイト兼ブログのようなものを再始動させてみます


買い物自慢です。
順番は単に思い出した順です。

## AirPods Pro

AirPods は前から使っていたんだけど、電池が消耗してきたし Pro が良さそうだから買ってみたところ、めっちゃよかった。

外音取り込みモードを使うと、耳に深く差し込んでいるのに以前の AirPods や EarPods のような抜け感のある聞こえ方になるし、
ノイズキャンセリングを有効にするとしっかり遮音してくれてうるさい場所でも快適になる。  
飛行機とか新幹線とかに乗るときに耳栓がわりに使っても良いと思う。

つけ心地は、カナル型が苦手な自分でも割と快適だった。
前の AirPods の方が耳が疲れないけど、一方で Pro は耳から外れにくいという良さがある。  
ただし、耳が汚れていると(特にウェットな耳垢の人)耳から取れやすくなるので、いつもよりもこまめに耳とイヤーピースを掃除するようになったと思う。

肝心の音質だけど、僕はそれなりに満足だった。もちろんちゃんとしたスピーカーやヘッドフォンで聞くと「いいな〜」と思うけど、これで音楽を聴いていても特に不満はない。

ワイヤレス充電にも対応していて、後で言及するワイヤレス充電器を買ってからは、そこに置いて充電することが多くなった。

## LG の 4K ディスプレイ

27UK850-W

4K で 27 インチのディスプレイで、USB Type-C(Thunderbolt)でラップトップを接続して給電もできる。会社のオフィスにも同じものがあり、まるで会社から持って帰ってきたような気分に。  
というか、4K で 27 インチで USB Type-C で接続して給電もできて、それほど高くないものを探すと自動的にこれ(あるいはこれのより新しいモデル)になってしまう。

4K は、良いです。

仕事でもプライベートでも使っていて、2 台の MacBook Pro 間でケーブルを差し替えるだけで環境を切り替えることができる。  
ただし、今は部屋の都合で一旦休眠中。

## MacBook Pro

ここ数年の間に Windows を使ってみたり Ubuntu を使ってみたりしたけど、やっぱり Mac がいいなということで改めて買った。
普通に良い。

メモリを 32GB 摘んだのでかなり安心感が高いのと、ESC キーが物理キーになっているのが良い。(個人的には、タッチバーは嫌いではない。)

## Galaxy Note20 Ultra 5G

スマホが古くなってきたので奮発して良いのを買うかーと思ったのと、ペンがついていて画面が大きいので Kakeru を使ってみるかな？と思って買った。

とにかく大きいので、少し扱いに困る。具体的には、手やポケットから落ちやすいのと、ポケットが小さいと厳しい。  
その代わり、画面は大きくてきれいだし、カメラの性能が素晴らしい。防水なので風呂に持って行ったり洗ったりもできる。

画面のエッジが狭いのは、良いんだろうと思っていたが、微妙なところもあった。  
1 つは、手が端の方に当たって誤操作してしまうこと。これは画面の端がカーブしているのもある。画面の端は普通に角張っていた方が良いと思う。
もう 1 つは、スマホスタンドなどに載せたときに、端の方が少し隠れてしまいがちなこと。

あ、そういえばこの端末には、顔認証と指紋認証が両方ついているんだった。  
指紋認証は画面内にある。反応はあまり良くない(というか正確な位置に触れるのが難しい)けど、背面にセンサーがあるよりは良いと思う。  
顔認証も便利であるが、マスクをしていたりもするので両方ついているのはかなりよかった。

ワイヤレス充電にも対応していて、後述の充電器が役に立っている。とはいえ、ケーブルを刺した方が早く充電できるのと、ワイヤレス充電器に AirPods Pro や妻のスマホが置いてあることもあり、ケーブルで充電することが多い。

## iPad Pro

欲しいなとは思いつつ、iPad Air もいいしなーとか古い iPad Pro があるしなーとか思って買えなかったが、年末に思い切って買ってしまった。後悔はしていない。

USB Type-C で充電できる(これで僕の普段使いのデバイスはほとんど Type-C で充電できるようになった)し、Apple Pencil もくっつくし、画面は 120Hz だ。素晴らしい。  
Kakeru をしばらく使ってバグを見つけて直したりもした。

今回、iPad には SNS のアプリを一切入れないことにしてみた。おかげで、これで本を読んだり何かを描いたりする時は集中できることが多い気がする。

## MiBand 5

Fitbit Alta HR のバンドが切れて、その上もう純正バンドが売っていない(しかも製品自体も販売終了)のと、Fitbit のアプリと通信するのにやたらと時間がかかるので、Xiaomi のバンドに買い換えてみた。

概ねできることは Fitbit と同じで、大きな違いはディスプレイがカラーになって少し広くなったことくらい。睡眠トラッキングは Fitbit の方が少し精度が良いかも？という気がするくらい。

## Keychron K1

https://www.keychron.com/products/keychron-k1-wireless-mechanical-keyboard

2 台のラップトップをクラムシェルで使う都合上、ワイヤレスで複数デバイスに接続できるキーボードが必要じゃない？ということで買ったやつ。

薄型のメカニカルスイッチは程よい押し心地で良い感じ。デバイスの切り替えもかなり便利で、有線でも接続できるのが良い。  
ただ、チルト機能がついていないのと、Enter キーの右が長いのがちょっと不満。(トラックパッドまでが遠いため。)

チルト機能は、裏に段ボール貼ってそれっぽくしたけど...。

買って少ししてから、K3 が発表されたので、Kickstarter 経由で注文してみた。発送は始まっているみたいだが、まだ僕には届いていない。楽しみである。

ところで、2 台のラップトップ切り替え問題に関しては、最終的にはいろいろなデバイスを有線で接続するのが良いという結論に至ってしまった。  
そうなると、キーボードは Magic Keyboard で十分だったのではという心の声もある...。薄いメカニカルも良いですけどね...。

## ワイヤレス充電器

Galaxy Note に AirPods Pro に、ワイヤレスで充電できるデバイスが増えてきたので買ってみた。

これは良い。デバイスを置くだけでケーブルを刺さずに充電できる、ただそれだけです。

## Nintendo Switch

家で運動をするのに FitBoxing やリングフィットアドベンチャーをやってみたいと思っていた。  
ところが、スイッチの本体が品薄だったためメルカリで買うか悩み続けていたところ、年末になってようやく Amazon で定価で購入できるようになったのでポチってしまった。

まだリングフィットアドベンチャーはほとんどやっていないが、FitBoxing は週に数回やっている。なかなか楽しい。

## Logicool の Web カメラ

Logicool StreamCam (C980GR)  
https://www.logicool.co.jp/ja-jp/product/streamcam

MacBook Pro をクラムシェルにしてディスプレイに繋ぐようになったので、カメラが使えなくて困った！ということで買った。  
[r7kamura さんが紹介していた](https://r7kamura.com/articles/2020-09-23-web-camera)ので試してみた。
今年は Web カメラが品薄になりがちだったけど、これは買えた。

お値段がお高いだけあって画質はかなり良い。
付属のソフトウェアでいろいろ設定をいじれるので、配信とかする人は良いんだろうなーと思う。
今のところ、ビデオ会議で自分の顔を写すのにしか使ってないが。

## FontAwesome Pro

Kakeru で使うために買った。アイコンを自分で作ってみようかなーとも思ったけど、コード書く時間が減るのでお金で解決することにした。

といっても、今のところ Pro のアイコンは 1 つしか使っていない。
今後なんかアイコンが欲しくなったときに選択肢が増えるのでまあいいか。買い切りだし。

## Raspberry Pi

Pi 3 Model B

なんとなく、音楽を再生するやつにしてみようかと思って買った。  
AirPlay サーバーと Spotify connect のサーバーが動いているけど、最近は Spotify connect ばかり使っている。

AirPlay の方は shairport-sync、Spotify は spotifyd というソフトウェア。

Android から ChromeCast 的なやつで再生したいなーとか、Bluetooth 経由で再生できないかな？とかいろいろ試したけど、諦めた。(Bluetooth は頑張ればなんとかなりそうだが、かなり辛そう。USB のオーディオデバイスを扱うだけで精一杯...)  
また、shairport-sync と spotifyd でオーディオデバイスの奪い合いをしてしまうようで、切り替えながら使うのは少しストレスだった。それもあって Spotify しか使っていない。

spotifyd は最初は手でプロセス立ち上げていたけど、たまに落ちるので systemd のサービスにした。  
それでも調子が悪い時がたまにあり、Raspberry Pi の電源を切って再度入れるという荒技で対処している。

Spotify で音楽をかけるのが楽になったのでかなり快適。

## Wi-Fi ルーター

NEC Aterm PA-WG2600HP3

今まで使っていた Apple 製のルーター(モデルは忘れた)がかなり遅いような気がしたので、新しいのを買ってみた。  
かなり速くなったと思う。

買ってから分かったことだけど、周りに 2.4GHz の電波が飛びすぎていて、2.4GHz だと速く通信できないことが多いっぽい。なので、5GHz を積極的に使うことにした。
(Apple のルーターも 5GHz に対応していたはずなんだが、...)

IPv6 に対応しているので、IPoE の設定をしてさらに高速化するぞーと意気込んでいたが、どうやらうちのプロバイダーではいろいろと手続きが面倒臭そうで挫折した。  
いろいろ調べた結果、スマホの回線でもお世話になっている IIJ の光コラボに乗り換えると無料で IPv6 も使えるし、割引も効き、支払いもまとめられて良さそうというところまで分かった。  
今年はそれを進めたい...。

---

去年も無駄にたくさんものを買ってしまった。
今年はあまり大きな買い物はしないような気がするけど、1 つ挙げるとすれば良いスピーカーを買いたい。


2020年に買ったものハイライト


2020 年は、いろいろあった。今更だけど、雑に振り返ってみようと思う。  
(本当に雑に書いてます。途中から書く気力がなくなってさらに適当になってきました。)

## ざっくりまとめ

- 子が 1 歳になった
- COVID19 が流行して自宅勤務に
- 仕事への悩み
- 子育て辛い
- 保育園に入れた
- Kakeru の開発
- 家を買うことになった
- まだオープンにはできない何か
- よく寝ましょう

## 子育て+在宅勤務が大変

2019 年の秋くらいからすでに子育てはまあまあ大変だった気がする。  
朝のある程度決まった時間に起こされてご飯を用意して食べさせたり、遊んであげたりするのがしんどかった。

2020 年、徐々に歩けるようになって活動範囲が広くなってきた。  
最初は 1 つの部屋でしか遊んでいなかったが、途中からベビーゲートを外して好きな場所で遊ばせるようになった。  
あちこち動き回るし、棚や机の上にあるものに手を伸ばしてくる危険な存在になった。

しかもそのタイミングで在宅勤務が始まった。

朝、ご飯を食べた後にだらだらと子供と遊んでいると、仕事を始めるタイミングを見失う。  
仕事を始めてしばらくすると今度はお昼ご飯なので、様子を見て僕も用意を手伝ったり食べさせたりする。  
そんな感じでなかなか集中できずストレスがたまった記憶がある。

その当時は少し広めのリビングに机を置いてそこで作業していたのだが、僕の机を別の部屋に移動してみることにした。  
納戸というかいろいろ物を置いている部屋で、エアコンもないし狭いのだが、仕事中に子供と距離を距離を取れるなら良いだろうと思った。  
結果的に、それはまあまあ良かった。ミーティングをする時にも気を使う必要がないし、何よりノイズがないので集中しやすい。

## 妻が仕事を始めて、子を保育園に入れる

春くらいから妻が仕事を始めることになった。  
以前勤めていた会社の仕事を、自宅で、かつ作業量は少なめで。

ただ、その時はまだ子を保育園に入れていなかったので、かなり大変だった。  
作業時間は子供のお昼寝中とか、寝た後とかになる。
その上に家事もやってくれていたし...。

そんな感じだったので、保育園に入れることを検討し始めた。
近所の小規模保育園に 1 つ空きがあったので、申し込んだところ入ることができた。  
両親とも働いている状態で申し込めたので良かったが、まだ仕事を探している段階の人はかなり大変だと思う。

入る前は見学に行ったり(見学に行かないとその園に申し込めない)、書類を書いたりし、
入園が決まってからはタオルやビニール袋などを用意して、服に名前を書き、
入ってからは慣らし保育で少しずつ時間を伸ばしていき、となかなか大変だった。  
働いたり仕事探したりしつつこれやるのなかなかハードでしょ。

とにかく、いろいろもっと楽にならないかな？と思った。
保育園で使うものとか、適当に向こうで用意して洗ったり管理したりしておいて欲しい。(要は金で)

でも保育園に入れたのはいろいろな点で良かった。1 つは夫婦 2 人ともに心の余裕が生まれたこと。  
仕事や家事もできるし、昼ごはんをゆっくり食べたりもできる。

もう 1 つは、子供にとってのこと。
家ではしない遊びを保育園ではするし、他の子と一緒に遊ぶことで良い刺激にもなっていたと思う。  
プライベートでは他の子と会うことはあまりなかったし、自宅では同じような遊びばかりになりがち。

だいぶ楽になったとはいえ、それでもやっぱり時間はない。  
どれくらい時間がないかというと、朝 9 時に保育園に送り出して、17:30 くらいに保育園から帰ってくるまでの間に 8 時間半しかない。  
帰ってからは家族でご飯を食べ、遊んで、風呂に入って、寝るのが遅くて 21:00 くらい。  
ほとんどの日は一緒に寝て一緒に起きるので、びっくりするくらい時間がない。

保育園に行っている間は楽だけど、送り出すためにちゃんと起きないといけないのは少しだるいところもある。  
ただ、そのおかげで生活リズムは改善されたと思う。  
少々遅れても保育園に送り出せる時間にはなんとか起きるし、送っていくのは僕の担当なので、その途中で陽を浴びて散歩もできる。
これは非常に良い変化だった。

## 仕事がだるい

在宅勤務が始まったくらいから、仕事がだるいなーと思うようになった。

原因は多分いろいろとあって、一つは前述した子育てへのストレスとか、あとは睡眠不足もあったと思う。  
子育てのストレスは保育園に行くようになって少し減ったし、秋くらいからかなり寝るようになったのでだいぶ障害は取り除けたと思う。

ただ、ひとつ言えたのは、やっていた仕事に興味を失っていたところである。

なんかだるいので、転職やあるいは社内の別の仕事を探すといったことにもあまり積極的になれず...。

今までやっていたのと少し方向性の違うことをやってみたり、別のプロジェクトの仕事を手伝ってみたりもしたので、その辺はよかった。

転職に関しては、若干行動はした。

まず、ビデオ通話でカジュアル面談みたいなのをいくつか受けてみた。  
まあ悪くない会社だなーと思ったことは何度かあったが、強い興味を感じたところはなかった。  
精神状態がよくなかったというのもあると思うが、オンラインで少し話しただけだと会社のことって全然分からないなと思った。

やっぱり、オフィスに行ったり飲みに行ったり(飲まなくても、食事だけでもいいと思うけど)しないとダメなんだろうか。

あと、ネットで見つけたとある会社がお試し入社的に仕事をさせてくれるようだったので、1 日 1 時間くらいなら時間割けるかなと思ってやってみた。  
最初はうまく行っていたが、僕のやる気がなくなってきてしまったのと、単純に時間がなくて終わった。(経緯は省略)

ただ、こういう仕組み自体はすごく良いんじゃないかなーと思った。
仕事の様子とか、Slack のやりとりとか見ているだけでも会社の雰囲気がだいぶ分かるしね。

この件で懲りて、睡眠を削って無理やり時間を作り出すのはもうやめることにした。  
それまでは別に削ってる感じはそこまで無かったんだけど、よく考えると無理しているなと気づいた。

2 時間ぴったりだけ作業して寝よう、とかができればいいんだけど、僕の場合はそれができない。  
ついだらだらと作業を続けたり、作業後に眠い目を擦りながらインターネットを徘徊してしまったりする。

普通に生活していても、子供を寝かせる頃には意外と疲れているので、子供と一緒に寝てしまうのが一番良いことに気付いてしまった。  
そんな感じで最大 10 時間くらい寝ている。
途中で起きてしまったり、一緒に寝付けなかったりで、必ずしも毎日たっぷり寝ているわけではないけど、以前よりはかなり寝ていると思う。

## Kakeru の開発

Twitter ではたまに言及していたけど、[Kakeru](https://about.kakeru.app/ja)という、共同編集できる手書きのホワイトボードのような Web アプリを作っていた。

去年を通してちまちまと開発していて、僕のちょっとしたモチベーションになっていた。

ただ、最近、意外と需要はないのかもしれないなーと思っている。
なぜなら僕自身があまり頻繁には使っていないから。

あと、メインとなるユーザーは、iPad+Apple Pencil を使う人なんだけど、その時点でかなり絞られてしまう。  
テキストで付箋的なのも貼れるようにしたら、PC でも iPad でも使えて良い感じになるかな〜？

そもそも、スマホばっかり使ってしまい、iPad を使うシーンが限られてしまう。
今のデスク環境(デスクのある部屋が寒すぎるので、食卓で仕事してる)もあるかもしれないけど...。

今年はスマホよりも iPad を使っていきたいなーと思うんだけど、子供がいるとそもそも時間がないという問題があり、Twitter などの無駄なネットサーフィンをせずに時間を捻り出す必要があるよな。

## 家を買うことになった

年末、急に家を買うことになった。

というのも、近所で新築の戸建てが売られていて、良かったのですぐ買うことにした。  
もともと、かなり前から、主に家の断熱性能が悪すぎるという理由で引越しを考えており、猫を飼ってるしなかなか良い部屋ないなーという感じだったので、スッと決めた。

住宅ローンや家に関する知識なども全然なく、場所(今の家も駅のそばで良い場所だし、そのすぐそばなので)と、値段と、間取りや設備(100 点ではないけど、それなりに良い)で決めた。

詳しくはまた書こうと思うが、今はローンの手続きなどをやっている。

## まだ書けないサムシング

ずっとやろうと思っていたことではあるが、少し前から動き始めていたことがある。
そのうちオープンにできると思う。

## その他

飲みにいく頻度は以前よりは減ったけど、それなりに飲みに行ったと思う。
でも、新しい人にはあまり会えなかったかも。

子供を保育園に行かせてるので、ランチに妻と 2 人で時間を過ごせるようになったのはかなり良い変化だったな〜〜。
本当は夜にも出かけたいんだけど...。

今年もあまり新しい出会いはないかもしれないけど、程よい頻度で美味しいものやお酒を楽しみにいきたい。

あ、別の記事にも書いたけど、Nintendo Switch を買ったんだった。フィットボクシングが結構楽しい。  
散歩したりフィットボクシングしたり、以前よりは少し動くようになったかもしれない。もう少し頻度を上げていきたいけど。

## おわりに

COVID19 の影響も、そうでないものも合わせて、なにかと変化の年だった気がする。

去年得られた一番の教訓は、「よく寝ろ」かな。

補足しておくと、お酒を飲みすぎるとよく眠れなくなる。


いまさら2020年の話をする


[[SNS]]を控えてみることにした。

## [[Twitter]]

なんとなく気になるとすぐフォローしてしまうせいで、Twitter のフォロー数が増えてしまった。
そうすると、タイムラインがかなり賑やかになる。

"latest tweets"を表示していても、まあ色々な情報が流れてきて、飽きる事がない。
大半はくだらないことばかりだがそれなりに面白いので見てしまう。

なんか暇ができたり、目の前のことに向き合いたくなくなったりすると、つい Twitter を開いてしまう。

## [[Instagram]]

食べ物の写真を上げる人とか、モデルさんやポートレート写真を撮っている人とかをフォローしているので、こちらもタイムラインが別の意味で賑やかになっており、たまに見てしまう。

主に見ている SNS はその 2 つかな。Facebook はたまに見ると悪くはないが、個人的にはあまり刺激がないので見ようと思わない。

## どう対処したか

まず、Instagram はスマホからアプリを消してみた。
知り合いはいるけど、あまりやり取りはしていなかったので問題ないはず。

店の情報などを見る事もあるので、そのうち入れ直してフォローを減らしまくりたい。

Twitter は、一度アプリを消してみたが、たまに人間の存在を感じたくなって Web ブラウザで開いてしまった。

ちょっとやり過ぎたかなと思い、アプリを入れ直してサブ垢でログインしてみた。

こちらはフォローが少なくてタイムラインが静かなので、見ていても刺激が少ない。

Twitter の本垢の方もフォローを減らしまくりたいが、面倒だなぁ。

## 感想

人とのコミュニケーションをする場でもあるけど、情報を摂取する場にもなりうる SNS は、油断していると自分の中の情報ジャンキーさを育んでしまう気がする。
これは RSS とかでもそうだけど、リアルタイム性が高い SNS ではその傾向は特に強いと思う。

僕は中 3 の時に Twitter を始めて以来、自分は大して中身がないにもかかわらず、薄い情報を貪り続けてきたような気がする。
ここで一度立ち止まって、もう少し心穏やかに生きてみようと思う。(← 大げさ)

1、2 日やってみたけど、まあ良いものである。
その時間を有効に使えているわけではなく、他の人のブログ読んだりゲームしたりくだらない事をしている。


SNS断ち


## TL;DR

- [[TypeScript]]で、ハッシュ関数と等値性を指定できる[[Map]]と[[Set]]を書いた。
- APIは[[ECMAScript]]のそれらとほぼ同じになるようにした。
- 最初は[[Java]]のLinkedHashMapを移植しかけたけど、ライセンス的に問題があるかもしれないので少し違うものに置き換えた。
- <https://github.com/odiak/map-and-set>で公開した。

---

先日、[[JavaScriptのSetはオブジェクトを入れづらい]]という話を書いたんだけど、その勢いでMapとSetを自分で実装してみることにした。

改めて書くと、やりたいことは、等値性とハッシュ関数を指定できるMapとSetを作ること。
APIはできるだけ[[ECMAScript]]のものと同じにしたい。

クラスの定義はこんな感じ。(コンストラクターの型定義だけ。それ以外のメソッドの型はESと同じ。)

```typescript
class Map<Key, Value> {
  constructor(
    iterable: Iterable<[Key, Value]>,
    {
      hash: (key: Key) => number,
      equal: (key1: Key, key2: Key) => boolean)
    }
  )
}

class Set<Value> {
  constructor(
    iterable: Iterable<Value>,
    {
      hash: (val: Value) => number,
      equal: (val1: Value, val2: Value) => boolean)
    }
  )
}
```

なお、ECMAScriptのと同じく、MapもSetも挿入順が維持されるようにしたい。

## JavaのHashMap, LinkedHashMapを移植してみる→断念

僕が知っている範囲だと、オープンソースの実装を参考にするならJavaのHashMapやLinkedHashMapがいいんじゃないか、と思って探してみた。

- [jdk7u\-jdk/HashMap\.java at master · openjdk\-mirror/jdk7u\-jdk](https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/HashMap.java)
- [jdk7u\-jdk/LinkedHashMap\.java at master · openjdk\-mirror/jdk7u\-jdk](https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/LinkedHashMap.java)

最初にHashMapを見て大まかに理解したあと、LinkedHashMapを見ると理解がスムーズだった。

APIは多少違うけど、これを移植すればいいんじゃね〜と思ってTypeScriptで同じようなものを書いてみた。
その時の実装が[これ](https://github.com/odiak/map-and-set/blob/7fe53da455e7a31552785f8a74e49368b100bc3c/src/map.ts)。

そのことをTwitterに書いた。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">とりあえず、JavaのLinkedHashMapを移植してMapを作った</p>&mdash; かいどう🐵 (@odiak_) <a href="https://twitter.com/odiak_/status/1357293417689088001?ref_src=twsrc%5Etfw">February 4, 2021</a></blockquote>

すると、JavaのソースはGPLなので別ライセンスのプロジェクトに移植するのはまずそう、というのを指摘してもらった。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">JavaのGPLコードの移植だとGPLにしないといけない気がする</p>&mdash; きしだൠ(K8S(Kishidades)) (@kis) <a href="https://twitter.com/kis/status/1357296380289552389?ref_src=twsrc%5Etfw">February 4, 2021</a></blockquote>

## V8の実装を参考にしてみる

APIをかなり変えて移植する場合、ライセンス的にどうなのかな？というのは気になったけど、念のため違う実装で置き換えることにした。
そこで見つけてきたのがこの記事。

[\[V8 Deep Dives\] Understanding Map Internals \| by Andrey Pechkurov \| ITNEXT](https://itnext.io/v8-deep-dives-understanding-map-internals-45eb94a183df)

V8のMapがどう実装されているかという話で、JavaのLinkedHashMapにも近いけど、Entryの順番を保持するための方法が若干違っている。
これを参考にして実装してみることにした。

C++の実装だと、効率化のために予め長さを決めた配列の上にEntryを並べているようだけど、TSではArrayの後ろにpushで追加していくようにした。
もう少し改善の余地はある気がするけど、まあいいや。

出来上がったのがこれ。 <https://github.com/odiak/map-and-set>

npmでも公開した。 <https://www.npmjs.com/package/map-and-set>

標準のMap/Setで満足できない人は、よかったら使ってみてください。

---

## 脱線コーナー

### Jestのはなし

今回は、[[Jest]]というテストのツールを初めて使ってみた。以前にChai+Mochaを使った気がするけど、Jestの方が設定が楽かなぁ？
いや、TypeScriptを使わないなら楽だと思うけど、TSを使うとトータルの手間はあまり変わらないかも。
ツール自体はよくできていると思う。

### JavaのLinkedHashMapと、V8のMapの違い

どちらも、挿入順が維持されるマップの実装。
[[ハッシュテーブル]]にEntryオブジェクトを連ねていく点は共通だけど、挿入順を維持するための仕組みが少し違う。

イメージ:  
![](https://i.kakeru.app/7681efcb1643e2d8c86613caf3f9feb1.svg)

#### JavaのLinkedHashMap

LinkedHashMapは、名前の通り、双方向リストを使っている。
Entryオブジェクト自体がリストのノードにもなっていて、前後への参照を持っている。

LinkedHashMapはheadという特殊なEntryを保持していて、そこを起点にしてそのほかのEntryが連なり、最後のEntryの後ろがheadに繋がる。

Entryを追加するときは、まずハッシュ表から出ている単方向リストの先頭にEntryを追加し、次にheadから始まる双方向リストの最後にEntryを追加する。

削除するときは、まずハッシュ表から出ている単方向リストからEntryを削除し、次に双方向リストからEntryを削除する。

双方向リストを、headを使って頭とお尻をつなげて持っておくことで扱いやすくしているのがなるほど〜と思った。(よくある実装なのかもしれないけど。)

TypeScriptで書くときは、headの扱いが型的に面倒なので、循環させずにheadとtailを持つことになるかな。

#### V8 Map

こちらは、dataTableというEntryの配列を持っており、長さはハッシュテーブルのサイズの2倍。
つまり、それより多くのEntryを入れたい場合はリハッシュせざるを得ない。

また、dataTableに実際に詰まっているEntryの数をnextSlotという変数に入れている。
ここまで聞くとArrayListっぽいなという気もするけど、Entryを削除する時の挙動が面白い。

Entryを追加するときは、まずハッシュテーブルから出ている単方向リストの先頭にEntryを追加して、dataTableのnextSlot番目にEntryを入れてnextSlotをインクリメントする。

Entryを削除するときは、単にEntryのkey,valueをnullで埋めてしまうだけ。
空になったEntryは、ハッシュテーブルを見るときやEntryを列挙するときには無視すればいいだけ。

挿入や削除を何回か行うと、dataTableがいっぱいになってしまう。
削除が行われた場合は、空のEntryもできる。
いっぱいになってしまった場合は、前述したようにリハッシュする。

この実装もなかなか面白いな〜と思った。

TypeScriptでこれを実装するにあたって、キーにnullも入れられるようにしたかったので、ひと工夫が必要だった。
といっても、EntryとEntryContainerという2つのオブジェクトを作り、EntryContainerがEntryを持ち、dataTableはEntryContainerの配列にする。
削除の時には、EntryContainerからEntryを取り除く(nullを入れる)というふうにした。


ECMAScript

JavaScriptのSetはオブジェクトを入れづらい


タイトル通り。
まあほとんど読まれていないと思うので単なる自己満足かもしれないが。

JavaScriptの[feed](https://github.com/jpmonette/feed)というパッケージを使ってフィードのXMLを作っている。
このライブラリは割と使いやすくて、`Feed`オブジェクトに適当に情報を追加するだけで、AtomなりRSS1/2なり好きなフォーマットで出力できる。

ライブラリがやってくれるので特に必須ではないけど、Atomフィードがどんなものか知るために、[Introduction to Atom](https://validator.w3.org/feed/docs/atom.html) というW3Cのドキュメントを覗いてみたりした。
これは[W3C Feed Validation Service](https://validator.w3.org/feed/)に付属するもので、自分でXMLを作る場合はこれで確認しながらやると良いかもしれない。

このサイトは、[以前にも書いた](/2021-01-04_starting)ように、Next.jsで書いてVercelでホストしている。
最初は1つのページとしてフィードを吐こうと思ったが、Next.jsでXMLをサーブする方法がよく分からなかったので、ビルド時に静的ファイルとして出力してみた。

最近使っているInoreaderでフィードを購読してみたら、日付が全部同じになってしまった。
これはInoreaderの問題なのか、フィード自体に問題があるのかよく分からない。

サイトにAtomフィードを付けてみた


最近LeetCodeの問題を解いてみている。

アプリ作ったりするのに比べて純粋に正解を目指せばいいのである意味で気が楽だし、コードがそこまで長くないので短い時間でもやった感が出るのが良い。


LeetCodeを始めてみた



[37\. Sudoku Solver](https://leetcode.com/problems/sudoku-solver/)

数独を解いてくださいという問題。

## 最初にやってみたけどダメだった解き方

1. 縦の並び、横の並び、3×3の領域にある数字から、入る数字が一意に定まるマスを探す
2. あればそのマスを埋める
3. 空いているますがあれば1.に戻る

これは非常にバカな間違いで、数独においては必ずしもそうして数字が決められるわけではないのだった。

## 次に試した解き方

`fill`という関数を定義して、`fill(board, 0, 0)`を呼び出して全てのマスを埋める。
で、その`fill`は次のようになる。(TypeScript)

```typescript
function fill(board: string[][], x: number, y: number): boolean {
  // yが9ということは領域外===全てのマスを埋めることができたので成功
  if (y === 9) return true
  
  const nextX = x === 9 ? 0 : x
  const nextY = x === 9 ? y + 1 : y
  
  // 数字がすでに入っている場合
  if (board[y][x] !== '.') {
    // 次のマスに進む
    return fill(board, nextX, nextY)
  }
  
  // その場所に入れることができる全ての数字を列挙する
  for (const char of possibleChars(board, x, y)) {
    // 数字をそのマスに入れてみて次のマスに進み、そのまま最後のマスまで到達できたら成功
    board[y][x] = char
    if (fill(board, nextX, nextY)) return true
  }
  
  // どの数字もダメだった場合は、マスを空にして終了する
  board[y][x] = '.'
  return false
}

function possibleChars(board: string[][], x: number, y: number): Iterable<string> {
  // 省略
}
```

まあ要するにおける数字を手当たり次第に試していくというごく簡単なやり方であるが、
ダメな手を打つとその先で打つ手が無くなってしまうはずなので、意外とステップ数は爆発しないと思う。

だが、これを提出してみると再帰が深すぎてエラーになってしまった。
処理系がちょっと弱すぎないか...。
別の言語使えって話かもしれないが。

今のところLeetCodeは解ける問題は全部TypeScriptで解いているが、再帰が全然使えないので困っている。
(再帰を使わずにどうやって解くかというのを考えるのも楽しいけど。)

というわけで、基本的にはこのアルゴリズムで、再起を使わずにスタックを使って実装したものを提出したら合格した。

スタックのオブジェクトにIteratorを持たせておくことでループの状態をいい感じに保持できることに気づいた時は気持ちよかった。


LeetCode #37 Sudoku Solver

プログラミングを始めてから今に至るまでを振り返る


岩本海童(いわもとかいどう)です。
福岡に住んでいるソフトウェアエンジニアです。

## 作ったものとか

- [Kakeru](https://about.kakeru.app/ja): 共同編集可能なホワイトボード的な Web アプリ
- [Reversi](https://reversi.odiak.net): JavaScript で書かれたリバーシのゲーム

## リンク

- Twitter: [@odiak\_](https://twitter.com/odiak_)
- GitHub: [odiak](https://github.com/odiak)


自己紹介


[[JavaScript]]にはSetというクラス(?)があり、一意な値を含んだコレクションを表現できる。
もちろん、プリミティブな値もオブジェクトも入れる事ができる。

プリミティブな値は話が簡単だが、オブジェクトの場合はちと面倒くさい。
オブジェクトの同値関係を自分で定義する事ができないのである。

具体的には、Setに追加される値は`Object.is`で比較するのとほぼ同じ方法(もっと具体的にはsame-value-zero equality)で既存の値と比較される。
なので、例えば`[number, string]`のような型のタプルのSetを作っても、同じような値(例えば`[2, "bar"]`)を何度も追加する事ができてしまう。

どうするか。

## 自分でSetクラスを作る

これは一番確実かもしれない。

ただ、ちゃんと効率的に作るのはそれなりに大変だと思う。
面白そうなのでそのうちやってみたい。

というか、npmにそういうのないのかな？

パフォーマンスが悪くても良ければ、内部を配列にして、挿入するたびに同じ値が入っていないかを確かめるという雑な実装もありかもしれない。

## Mapを使う

これはかなり手抜き。
しかも前提条件があって、オブジェクト同士の比較が1つのプリミティブ値の比較になっていること。

例えば、`type Obj = {id: string, name: string, count: number}`というような型のオブジェクトを、
`id`さえ同じなら同値とみなすような場合。

この例を使うと、`const map = Map<string, Obj>()`を用意して、`map.set(obj.id, obj)`てな感じで値を挿入することで、
`id`が一意な`Obj`オブジェクトのコレクションが作れる。

## まとめ？

JavaScriptのSetオブジェクトが微妙に使いづらいので、なんとかする方法を考えてみた。

Setに関する[[ECMAScript]]の仕様も読んでみたいな〜。

あと、MDNの[JavaScriptの等価性に関するページ](https://developer.mozilla.org/ja/docs/Web/JavaScript/Equality_comparisons_and_sameness)が面白かった。(軽く眺めた程度だけど。)  
same-value-zero equalityについても今回そのページを見て初めて知った。
