「みんなのデータ構造」学習メモ:6.2 BinarySearchTree 二分探索木
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ:2.1 ArrayStack
- 「みんなのデータ構造」学習メモ:2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ:2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ:3.1 SLList 単方向連結リスト
- 「みんなのデータ構造」学習メモ:3.2 DLList 双方向連結リスト
- 「みんなのデータ構造」学習メモ:5.1 ChainedHashTable, 5.2 LinearHashTable
- 「みんなのデータ構造」学習メモ:6.1 BinaryTree 二分木
二分木の続き。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/BinarySearchTree.ts
2020年1〜3月のふりかえり
本当は毎月ふりかえりたかったんですが、気がついたら最初の四半期が終わってました。
この3ヶ月の間にやっていたこととか勉強していたことのふりかえり。
ちなみに年末のふりかえりは 2019年のふりかえりと2020年の抱負 - dackdive's blog です。
2020年1〜3月にやったこと
コンピュータサイエンスを勉強する💪 → 「みんなのデータ構造」
2020年の個人的メインテーマである「コンピュータサイエンス系のことを勉強する」。
その第一歩として読み進めていた「みんなのデータ構造」、ざっくり3ヶ月以内を目標にしていたんですがまだ終わってません。。。
読み始めた当初、この本に書かれている内容は細かいところまですべて理解しようと意気込んでいたんですがあえなく挫折しました。
今は、「本書の読み方」に書いてあったように「わからないところは飛ばしてもよい」ものと割り切り、また特に重要な項目として取り上げられていたものだけとりあえず読むことにしました。
あとトピックとしては3つぐらいなので、4月中に読み終えてまとめもしたい。
ブラウザの Cookieについて学んだ
年明けにHTTP/Tokyoという勉強会に参加したのがきっかけで、1月後半〜2月頃はブラウザのCookieについて勉強してました。
アウトプットとして何も残せなかったのが残念。
こちらのブログ・スライドはとてもわかりやすくまとめられていて、定期的に読み返したくなります。
ECMAScript Proposal の Realms や SES について学んだ
今の職場のチームでは業務時間内に興味のある技術の調査・探究をする時間があるのですが、この時間を利用して前々から興味のあったRealmsとSESというECMAScript Proposalについて勉強してました。
Realmsは現在Stage 2、SESはStage 1です。
前提とされるJavaScriptの仕様の話が難しく、時間をかけた割に概要レベルでしか把握できてないのですが
それぞれがどんなことを実現しようとしているのか、雰囲気だけでも理解できてよかったです。
また、ECMAScriptの仕様の読み方、策定中のProposalの追っかけ方なども学びがありました。
(後者はまだコツがつかめてなくて、いつの間にかSESから分離したProposal Compartmentsなるものができてたことに気づきませんでしたが...)
ECMAScriptの仕様の読み方についての記事が2つ。 https://t.co/nE7KrGePPP https://t.co/WdIErZlGd1 さらにteppeisさんからオススメの勉強法としては、core-jsのソースを読む(割とECMAScript specのアルゴリズムに忠実な実装をしている)#サイボウズフロントエンドランチ
— Shingo Yamazaki (@zaki___yama) 2020年2月18日
この2つの記事はまだ積ん読状態なので読みたいなあ。
また、Realmsなどを理解する上でJavaScriptのPrototype Pollutionという攻撃についても学びました。
こちらの記事が非常にわかりやすかったです。
Node.jsにおけるプロトタイプ汚染攻撃とは何か - ぼちぼち日記
Chromium版Microsoft Edgeに興味を持った
チームでブラウザ情報とかウォッチするようにしてるんですが、年明けにリリースされたChromium版のMicrosoft Edgeに関する公式ブログを読んだおかげでEdgeに興味を持つようになりました。
Chromiumベースの新しいMicrosoft Edgeについて - dackdive's blog
また、実現はできませんでしたが、このブログ記事がきっかけで勉強会に登壇しないかと声をかけていただくこともありました。
(話そうかと思ってた内容の一部を資料にまとめたものは
Chromium版EdgeのTracking Prevention機能 / Tracking Prevention in Chromium-based Microsoft Edge - Speaker Deck
です)
あんまり日本語の情報も出回ってないので、しばらくは引き続きウォッチしてこうかなーという気持ちになりました。
また、Macでも使えるようになったし、Chromiumベースだから普通に使いやすいのでデフォルトのブラウザとしても使っていこうかと。
次の四半期(2020年4〜6月)のテーマ
最初の四半期をなんとなく過ごした結果、四半期ごとぐらいの大きめのテーマと、月ごとの小さなテーマの2種類を用意しておくと自分にはいいんじゃないかなという考えになりました。
データ構造とアルゴリズム勉強するぞ!みたいな目標だと1ヶ月はハードル高いし、かといって「この本読みたい」みたいな目標であれば◯月中に終わらせる!という目標設定にした方が間延びせず良さそうです。
毎月
というわけで
長期(四半期)
引き続きデータ構造とアルゴリズム系の勉強をするぞ!ということで、次の課題図書はこちらです。
すらすら読める本であってくれ頼む〜😇
あとは密かな裏テーマとして、Rust + WebAssembly 的なところにもぼちぼち手を出したい。
今は rustlings をちまちまやっています。
またこんな情報もある。
Rust by Exampleという、Rustで具体的にコードをどう書いていったらいいかの例がたくさん載ってるドキュメントが、日本語訳された!🎉 #rust_jp / Rust by Example 日本語版 https://t.co/VPway4jn8l
— yuki (@helloyuki_) 2020年4月6日
短期
4月中は「みんなのデータ構造」を読んでると思います。
5, 6月は設計の勉強をしたい。
年末に立てたTryの確認
- 英語ブログ、今年こそ書く!目標は3本
- →何もやってない
- 今年もどっかのカンファレンスにCfP出す
- →何も(略
- 「みんなのデータ構造」とあともう1冊、コンピュータサイエンスに関する本を読む
- →「みんなのデータ構造」は続いているぞ💪
- 本は年間で6冊読む
- →1冊め
新Microsoft Edgeにこれからリリースされる新機能("The top 10 reasons to switch to the new Microsoft Edge"より)
Edge公式ブログより。
Edgeにリリース済みorこれからリリースされる便利機能の紹介。
ざっと目を通したのでメモ。
gifは公式ブログより引用しています。
1. Collections機能 Organize your research with Collections
概要:高機能ブックマーク的なやつ。カテゴリ分けたり、記事から画像だけドラッグ&ドロップでCollectionに保存することもできる。 ステータス:Canaryにはリリース済み。Stableには間もなくリリース。モバイルにも今春後半にリリース予定
2. 垂直タブ機能 Work efficiently with vertical tabs
概要:1クリックでタブが垂直に。タブ名見やすくなりそう
ステータス:数ヶ月後にInsider (Beta?) チャネルにリリース予定
3. スマートコピー機能 Save time with smart copy
概要:Webページを雑にドラッグで選択→コピーすると、表などのフォーマットを保ったままコピーできる
ステータス:5月にInsiderチャネルでリリース予定
4. Tracking Prevention機能 Take back control with tracking prevention
概要:以前まとめたので見てください(宣伝)
ステータス:リリース済み
5. パスワードモニター機能 Know if your passwords have been compromised on the dark web with Password Monitor
概要:ブラウザのautofillに保存したユーザー名+パスワードがダークウェブに漏洩したと見られる場合に通知される
ステータス:数ヶ月後にInsider (Beta?) チャネルにリリース予定
6. InPrivateモード Maintain truly private browsing and search with enhancements to InPrivate mode
概要:Chromeのシークレットウィンドウ。これまでBing検索履歴は対象外(削除されない)だったが、今後はこの検索履歴もアカウントに関連付けられなくなる
ステータス:InPrivateモードはリリース済み。Bing検索はInsiderチャネルはリリース済み、Stableは間もなく。
7. イマーシブリーダー Immersive Reader enables everyone to learn and benefit from the web
概要:サイトの不要な部分を除外してコンテンツを読みやすくしたり、音声読み上げができる機能
→
ステータス:リリース済み。今後より機能を追加していく予定。
8. Netflix動画を4Kで Microsoft Edge delivers the best immersive viewing experience in 4K and Dolby Audio
概要:Netflixの動画が4K + Dolby Audio & Dolby Visionで観られる。Win10限定
ステータス:リリース済み
9. Bing検索時に獲得できるリワードを寄付できる Make a difference: Give with Bing
概要:Bing検索するとポイントが貯まるMicrosoft Rewardsというしくみがあるが、このポイントを特定の団体に寄付するよう設定できる
ステータス:リリース済み
10. Microsoft Edge is ready for you (and it’s easy to switch)
概要:新Edgeへの移行時はこれまでのお気に入りなどの設定情報を引き継ぐことができる(機能ではない)
「みんなのデータ構造」学習メモ:6.1 BinaryTree 二分木
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ:2.1 ArrayStack
- 「みんなのデータ構造」学習メモ:2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ:2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ:3.1 SLList 単方向連結リスト
- 「みんなのデータ構造」学習メモ:3.2 DLList 双方向連結リスト
- 「みんなのデータ構造」学習メモ:5.1 ChainedHashTable, 5.2 LinearHashTable
今回は第6章。ここから木構造の話。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/BinaryTree.ts
「みんなのデータ構造」学習メモ:5.1 ChainedHashTable, 5.2 LinearHashTable
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ:2.1 ArrayStack
- 「みんなのデータ構造」学習メモ:2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ:2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ:3.1 SLList 単方向連結リスト
- 「みんなのデータ構造」学習メモ:3.2 DLList 双方向連結リスト
今回は第5章にとんで
- [P91] 5.1 ChainedHashTable: チェイン法を使ったハッシュテーブル
- [P97] 5.2 LinearHashTable: 線形探索法
を読む。
始めに書いておくと、5.1.1 乗算ハッシュ法の数学的な証明部分をちゃんと理解するのを諦めた。
また、LinearHashTable は冒頭の概要説明しか読んでいない。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ChainedHashTable.ts
「みんなのデータ構造」学習メモ:3.2 DLList 双方向連結リスト
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート
これまでのメモ
- 「みんなのデータ構造」学習メモ:2.1 ArrayStack
- 「みんなのデータ構造」学習メモ:2.3 ArrayQueue
- 「みんなのデータ構造」学習メモ:2.4 ArrayDeque
- 「みんなのデータ構造」学習メモ:3.1 SLList 単方向連結リスト
今回は「[P58] 3.2 DLList: 双方向連結リスト」。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/DLList.ts