LeetCode: Binary Tree-1
概要
LeetCodeを始めたのでその学習記録です。
Binary Tree
まえがき
『ツリー』とは、階層木構造を表すデータ構造である。 ツリーの各ノードは、ルート（根）と、子ノードと呼ばれる他のノードへの参照リストを持つ。 グラフ理論でいえば、ツリーは連結されていて閉路を持たないグラフであり、N個のノードとN-1個のエッジ（枝）を持つ。
バイナリツリーは、ツリーのもっとも典型的なものである。各ノードは多くて二個の子ノード（左と右）を持つ。
Traverse a Tree - Introduction
Pre-order Traversal ルートを訪問済みとして、左の子ノードを訪問していく。末端のノードにたどり着いたらそのルートノードに戻り、右から始まるサブツリーを、同じルールで探索する。根、左、右、の順。
In-order Traversal ルートを出発点にして、左のサブツリーから末端の左ノードを探索する。末端のノードにたどり着いたらそれを訪問済みとして、そのルートノードも訪問済みにし、次に右から始まるサブツリーを同じルールで探索する。左、根、右の順。 In-order Traversalを使うと、バイナリツリー内のソートされたデータを順序通り取得できる。
Post-order Traversal ルートを出発点にして、左のサブツリーから末端の左ノードを探索する。末端のノードにたどり着いたらそれを訪問済みとして、次にその同階層の右ノードから始まるサブツリーを同じルールで探索する。すべての子ノードが訪問済になったらルートも訪問済みにする。左、右、根の順。
例えば、ノードとその子ノードをツリーから削除しようとしたとき、対象ノードの子孫ノードは対象ノードの削除より前に削除されていなければならない。Post-order Traversalは、子孫ノードを先に訪問済みにできるので、このような処理に適している。 また、Post-order Traversalは、計算式を表現するのにも適している。
Coursera Service-Oriented Architecture Week3 REST Service
REST API設計の注意点
URIには名詞のみを使う 例えば、大学用のAPIを作るとしたら、/students/や/students/SID/coursesのように、名詞をURIに使う。 （ただしこれは厳密にRESTfulであるとはいえない。よいURIは、リソースを示し、クライアントがそれに容易にアクセスできるようにする）
GETメソッドはリソースの状態を変えない GETメソッドは、リソースを参照するためだけに使う。リソースの状態に影響を与える操作は、POST、PUT、DELETEメソッドで行う
URIには複数形を使う x student -> o students
リソースとリソースの関係を表すためには、サブリソースを使う 例えば、生徒がコースをとっているということを表すために、/students/SID/coursesというようにサブリソースを使用する。
入力/出力フォーマットを指定するためにHTTPヘッダーを使う Content-Typeでリクエストメッセージのフォーマット、Acceptで期待するレスポンスメッセージのフォーマットを指定する。
クエリパラメーターでフィルターやオフセットの指定ができるようにする /students?name=hogeのように
APIをバージョンづけする 既存のAPIを変えずに、新しいバージョンをリリースできるよう、URIにバージョン番号を含めるとよい
適切なHTTPステータスコードを使用する
マイクロサービス
巨大なチームで作られる一枚岩（同じコードベース）のシステムには、 - メンテナンスしづらい - スケールしづらい - 開発期間が長くなる - パフォーマンスが悪い 等の問題が出てくる。 これに対応するために、Service Oriented Architectureは、巨大なシステムを小さい機能ごとにサービスとして分割し、それぞれのサービスは疎結合でカプセル化されているようにすることを提案する。
マイクロサービスは、Service Oriented Architectureのバリエーションの一つである。 マイクロサービスのアーキテクチャスタイルは、マイクロサービスを組み合わせて一つのアプリケーションを作り上げるためのものである。 マイクロサービスは、一つの独立したタスクに対して責務を持つ。例えば、あるアプリケーションの中で、一つのマイクロサービスは検索機能の責務をもち、また一つのマイクロサービスはレコメンド機能の責務を持つなどである。 マイクロサービスはそれぞれ独立して開発される。マイクロサービスはしばしばレイヤードアーキテクチャーのすべての層を実装しない。なぜなら、マイクロサービスは他のマイクロサービスと連携することを意図しており、例えばエンドユーザー向けのプレゼンテーション層を持たない場合があるからである。
マイクロサービス同士のやりとりでは、HTTPがよく使われる。RESTインターフェースは、マイクロサービス同士のステートレスなコミュニケーションによく用いられる。
マイクロサービスには、次のような利点がある。 - マイクロサービスは、そのサービスに適した言語、フレームワーク、アーキテクチャを使うことができる。そのため、実装したい機能に一番適した組み合わせで開発を行うことができ、開発者も新しいテクノロジーを使うことができる。 - 疎結合なので、スケールやメンテナンスがしやすい。 - 一つのサービスは一つの小さなチームによって独立に開発されるので、素早く開発できる - コードのメンテナンス性が高くなる
しかし、次のような欠点もある。 - それぞれのサービスは分散し、非同期に動作するため、すべてのサービスを管理する中央システムが必要になる - それぞれのサービスが独自にデータベースを持っているため、トランザクション範囲が複数のサービスに及ぶ - 複数のサービスに渡ったテストが難しい - すべてのサービスは、他のサービスが処理に失敗したときのことを考えて実装されなければいけない - サービス同士のコミュニケーションにコストがかかる
Coursera Service-Oriented Architecture Week1 Service-Oriented Architecture
Service-Oriented Architecture
ソフトウェアは、外部のサービスを利用することができる。天気の情報がほしいときには、観測基地を建てるのではなく天気情報APIを使うなどである。
サービスとは、コンポーネントとは違い、外部（たいていは外部の会社のサーバーやインターネット上）に存在する。 サービスについて話すとき、サービスのリクエスタとプロバイダ、両方の役割について言及することになる。
Service-Oriented Architectureは、サービスを構築する・利用する・組み合わせるやり方についてのアーキテクチャである。
Service-Oriented Architectureでは、非機能要件がたいへん重要になってくる。なぜなら、外部のサービスについては開発者が制御できないからである。 レスポンスタイム、サポート、可用性などである。サービスの利用には利益もあるが、トレードオフとのバランスを考える必要がある。
Service Principle
使いやすいサービスの提供のためには、サービスとService-Oriented Architectureのためのベストプラクティスがある。
- モジュールになっていること：サービスはモジュール性があり、疎結合である必要がある。これによって、サービスは可搬性があり再利用可能になる。
- 組立可能であること：例えば、Javaで書かれたサービスをRubyで書かれたシステムから利用できるといったように、サービスは外部のシステムに組み込まれることを前提とし、外部とは決まったプロトコルでコミュニケーションできるようになっている必要がある。
- 自己記述方式：サービスは自分自身をどう使ったらよいか説明することができる必要がある。(WSDL等を使う）
Web-System Architecture
Webシステムは、 - プレゼンテーション層（ブラウザ、Webサーバ） - アプリケーション層（アプリケーションサーバ） - データ層（データベース） の層に分かれることが多い。 静的Webページを表示する場合は、 - プレゼンテーション層（ブラウザ、Webサーバ） - データ層（HTML） の二つの層だけでも事足りることがある。
このように、レイヤードアーキテクチャーを使うことは、関心の分離やコードの再利用に役立つ。
Remote Procedure Call(RPC)
現代のシステムは、ネットワーク越しにコミュニケーションできるようになっていることが多い。 個々のシステム、例えばクライアントとサーバーは、それぞれの用途に特化した構成となっていて、お互いの詳細な実装については知らない。その二つがコミュニケーションするためには、ミドルウェアを間に挟む。ミドルウェアがコミュニケーション用のインターフェースを提供することにより、やりとりが可能になる。これはデザインパターンのMediatorパターンに似ている。
RPCは、あるマシンが別のマシン上のプログラムを実行することができるようにする仕組みである。 - 呼び出し元 - 呼び出される側 - インターフェイス定義言語 の３つの主要なコンポーネントから構成されている。
Object Brokers
Object Brokerは、分散システム上でのそれぞれのコンポーネントを接続し、オブジェクト指向のアプローチによって使用することができるようにするものである。
Coursera Software Architecture Week3 Analyzing and Evaluating an Architecture
システムアーキテクチャのデザインが、すべてのステークホルダーの関心を考慮したものかどうかをどう判断すればいいのか？ デザインの標準ルール・ガイドラインに従うことで、アーキテクチャが基準を満たしたものになることを期待できる。 このレッスンでは、個々の品質特性をどのように評価するのかと、デザイン全体をどのように評価するのかを学ぶ。
品質特性は、機能要件や非機能要件の測定に使用される。しかし、測定とはどのように行えばよいのか？ それには品質特性シナリオを使用する。 シナリオには『一般』と『特定』の二つがあり、『一般シナリオ』はシステム全般を測定するのに使用する。『特定シナリオ』は特定のシステムを測定するのに使用する。 すべてのシナリオは、以下の要素で構成される。 - 誘発源（外部/内部の誘発のもと。タイマーだったりエンドユーザーだったり） - 誘発（システムの応答を促す原因） - 環境（システムが誘発を受けたときの状態） - アーティファクト（誘発によって影響を受ける部分のシステム） - レスポンス（誘発をうけてシステムがどのように振る舞うのかの結果） - レスポンスの測定（品質特性の測定のため、レスポンスの内容を計測する基準）
シナリオでは、正常な場合のシナリオに加えて、不正な入力があった場合、ロードアベレージが高い場合なども含める必要がある。品質特性で可用性を挙げている場合なら、システムが使えなくなる場合のシナリオを作成し、回復にどれくらい時間がかかるのかを測定しないといけない。
一般シナリオでは、 - 誘発源:エンドユーザー、内部のサブシステム、外部システム - 誘発:不正なユーザー入力、内部エラー、認識されていないシステムからのリクエスト、巨大なリクエスト、高負荷 - 環境:通常、スタートアップ中、シャットダウン中、高負荷、エラーからの回復中、リクエストへ返答中 - アーティファクト:サーバー、プロセス - レスポンス:例外をログする、ユーザー通知、外部システムにエラーを返す、システムがスタートアップ中/シャットダウン中と通知する - レスポンスの測定:リスタートにかかる時間、回復までの時間、レスポンス完了までの時間 などのように場合を用意し、それぞれについてシナリオを作成する。
特定シナリオでは、ある特定の場合についてシナリオを作成する。例えば、可用性について、 - 誘発源:顧客 - 誘発:コンサートチケット購入リクエスト - 環境:プロセス数が最大数に到達 - アーティファクト: Webサーバー - レスポンス:顧客にサービスがビジーと返答 - レスポンスの測定:現在のリクエストを完了させるまでの時間 のようにして特定の場合について評価する。
このシナリオを、品質特性の評価について使うやり方として、ATAM（Architecture Tradeoff Analysis Method）というものがある（カーネギーメロン大学によって開発された）。 これは、評価者はアーキテクチャー自体や問題のスコープに詳しくなくても利用できるメソッドである。
ATAMは、参加者を３つのグループに分ける。一つは評価グループ。評価グループは３つのサブグループに分かれ、それぞれデザイナー、ピア、外部の人間となる。 評価グループの一番大事な特徴は、バイアスがかかっていないということである。 デザイナーはアーキテクチャーデザインに関わる。仮説を立て、要求を分析し、デザインを作成し、レビューすることを反復的に行う。 ピアはデザインプロセスにはかかわらないが、デザインに必要な別角度からの観点を提供する。 外部の人間は、プロジェクトやチームとはかかわらず、バイアスがまったくないことが必要である。しかしアーキテクチャの分析には経験を持ち、バイアスのない視点からの分析を可能とする。
二つ目のグループは、プロジェクトの決定者である。このグループには、プロジェクトマネージャー、顧客、プロジェクトオーナー、ソフトウェアアーキテクト、テクニカルリードが含まれる。このグループはプロジェクトの行う決定について権限と責任をもつ。
３つ目のグループは、アーキテクチャステークホルダーである。このグループには、アーキテクチャにビジネス上のニーズを表現することを求める誰でもが含まれる。しかしその誰でもは、評価プロセス自体には含まれないこともある。エンドユーザー、開発者、サポートスタッフはこのグループに属する。
ATAMによる評価のプロセスは、ざっくりと以下のようになる。
- ビジネスメンバーが必要性からシステム開発プロジェクトを立ち上げる。
- ビジネスメンバーは連帯してビジネス上の問題を解決するためのシステムアーキテクチャを作成する。
- ビジネスメンバーとシステムアーキテクチャは品質特性とデザインを作成する。
- 品質特性とデザインから、品質特性シナリオを作成する。
- シナリオは分析結果から、トレードオフ・重要な点・非リスク・リスクの４つに分けられる。
- リスクシナリオはビジネスによくない影響を与えるため、リスクシナリオをカテゴライズしてリスクテーマに分類する。
ATAMの詳細なプロセスは、以下の9段階に分けられる。 1. ATAMについてプレゼンする。 2. ビジネスメンバーがビジネス上の問題とシステムのゴール、それにシステムの機能、要求、プロジェクトの制約、スコープをプレゼンする。 3. 現在のアーキテクチャと将来のアーキテクチャについてプレゼンする。アーキテクチャはプロジェクトの制約の影響を受ける。 4. アーキテクチャの方針を確認する。ドキュメントや3でのプレゼンを評価し、システムについてより詳しい情報を得る。 5. 品質特性木をつくる。個々の品質特性についての要求は、品質特性木であらわされる。システム内部の情報と、ビジネスメンバーから得られる品質の優先順位によってこの木を更新できる。 6. アーキテクチャのアプローチを分析する。品質特性木のASRによって、システムがどのように要求を満たすようになっているのか評価する。 7: それぞれのグループがグループにとって大事な点についてシナリオを作成し、優先順位をつける。それぞれのグループのシナリオで、似ているものはマージする。 - 重要な点: ASRに影響する（例：高トラフィックはシステム応答の遅れの要因になる） - トレードオフ:一つの品質特性を満たそうとすると他の特性が犠牲になる（例：システムの高負荷対策に同時接続人数を制限できるが、それは可用性を低めることになる。どちらを選ぶかはビジネス的な決定になる） 8: 優先順位五〜十位までのシナリオを使い、再度品質特性木を作成する。 9 結果を評価し、ドキュメント化する。
Coursera Software Architecture Week3 Architectual Trade-offs
Quality Attributes
- 何がアーキテクチャの良し悪しを決めるのか？
- 品質をどのように評価するのか？ 品質が改善されたかどうかということをどのように評価するのか？
- 開発プランと開発チーム構築の場面でアーキテクチャをどのように使用するのか？
- 開発コストを削減し、開発効率を上げる機会をどのように検知するのか？ についてこの週のモジュールでは学ぶ。
デザインパターンは、特定の技術的な問題に対処するのによい方法だが、広い範囲のビジネス上の問題と関心に対処するための方法ではない。 現代のシステム開発では、後者の問題についても対処するべきである。システムアーキテクチャは、機能要件・非機能要件を含む、システム全体の図を扱う。
アーキテクチャはデザインパターンやデザイン原則のためにガイドラインを提供する。これは、システムがConceptual Integrity（概念上の一貫性）をもつことが、システム全体にわたって一貫性をもつことにつながるからである。 デザインパターンはシステムのメンテナンス性、再利用性、パフォーマンスを向上させるが、システムのテスト可能性、ユーザビリティ、信頼性については関心を持たない。システムアーキテクチャは、後者の非機能要件にも関心をもち、デザインパターンを注意深く組み合わせることで、一貫性のあるシステムを構築する。
システムアーキテクチャの本質的な良さ・悪さというものはない。システムアーキテクチャは要求に沿ってデザインされるものであり、要求は問題や必要に応じて生成されるものである。 たとえば、Web上のゲームシステムに対しては、リポジトリベースアーキテクチャ上で構築されたイベントベースアーキテクチャを使用する。しかしこれはリポジトリベースアーキテクチャが悪いというわけではなく、多数のユーザーのプレイに対応する方法としてリポジトリベースアーキテクチャが適切でないというだけである。このように、現代のシステムでは、複雑な問題に対処するために複数のアーキテクチャを組み合わせて使用する。コンテキストが重要なのである。
システムをデザインするときには、機能要件のほかに非機能要件も重要になってくる。非機能要件は、クライアントやステークホルダーによって明示的に示されないことも多い。また、これらはステークホルダーごとに異なってくることもある。例えば、開発チームはシステムのメンテナンス性、再利用性、テスト可能性を気にするが、エンドユーザーはテスト可能性などは気にかけない。そのかわり、ユーザビリティ、エラーハンドリング、安定性を気にかける。システムアーキテクチャはそれぞれのグループの関心事を組み込まなければいけない。そして、それぞれの要求に優先度をつけ、よいバランスをとらなければいけない。
開発者が気にする品質特性
- メンテナンス性
- 再利用性
- 柔軟性
- 変更用意制
- テスト可能性
- 一貫性
エンドユーザーが気にする品質特性
- 可用性（アップタイムから算出する）
- 操作性
- セキュリティ
- パフォーマンス（スループット、レイテンシから算出する）
- ユーザビリティ
品質の高いシステムアーキテクチャのデザインは、方法論的に確立されている。どのようにデザインするかのルールとガイドラインに従うことで、よいデザインを行うことができる。
Coursera Software Architecture Week2 Learning Objectives-3
Data Flow Architecture
Pipe and Filter Architecture
Filter: データの変換 Pipe: データの通り道
Filterは『どのようなデータが入ってきて』『どのようなデータが出ていくのか』だけに集中することで、疎結合になる。 また、Filterの内部をブラックボックスとすることができ、Filterは再利用が可能である。
しかし、Filterを増やすと、そのぶんオーバーヘッドが増える。 また、このPipe & Filter Architectureはインタラクティブなアプリケーションには向かない。レスポンスに時間がかかるからである。
Event Based
Event Based Architectureでは、イベントはシステム内の主要要素である。シグナルやユーザー入力、メッセージ、データなどがイベントになりうる。イベントが発生することにより、何かしらの機能が動作する。 Event Based Architectureでは、イベントジェネレータ（イベントを作成する）とイベントコンシューマ（イベントを受け取り処理する）の二つの役割のものがある。
イベントによって起動される機能は、サブルーチンを実行するときのように明示的に実行されるのではなく、イベントバスを通じて暗黙的に実行される。イベントバスはイベントジェネレータとイベントコンシューマをつなぐ役割をする。イベントジェネレータがイベントを作成すると、イベントバスがそれを検知しイベントコンシューマに通知する。つまり、すべてのイベントはイベントバスを通じてイベントコンシューマに届けられる。これはデザインパターンのオブザーバーパターンと同じである。
このようにすると、イベントジェネレータはどのコンシューマがイベントを受け取るのかを気にしないし、イベントコンシューマはどのジェネレータがイベントを作成したのかを気にしなくて良くなる。
しかし、イベントバスを使うと、複数のコンシューマが同時に同じイベントを受け取り処理することで、データ更新で競合するということが発生する。競合を防ぐため、セマフォという仕組みが考えられた。値が使用されているかどうかを示すことで、競合を防ぐ。
Event Based Architectureでは、事前に機能が実行される順番を予測することはできない。
Process Control
フィードバックループ
- センサー：状態を監視する
- コントローラー：ロジック
- アクチュエーター：プロセスを操作する
- プロセス：操作したい対象 センサーがプロセスの状態を取得し、コントローラーに送る。コントローラーのロジックが状態をあるべき状態の差を計算し、アクチュエーターに操作をリクエストする。アクチュエーターはプロセスを操作する。そしてその状態をセンサーが取得する。
コントローラーは常に動いていなければいけない（状態はつねに変化するので）。
フィードフォワードループ
フィードバックループに、外的要因を排除するための修正操作を追加したもの。
Coursera Software Architecture Week2 Learning Objectives-2
ちょっと体調を崩してしまい、中断していました。今日から再開します
Database
データを集中管理し、スケーラビリティを確保するため、データベースを使用することが一つの有益な方法である。 データベースを使用する際には、データベースの管理コンポーネントと、その管理コンポーネントへのアクセサ（トランザクションなどを行うのもこの部分）を併用する。 これにより、データの保存、信頼性の担保を管理コンポーネントに任せ、システムはデータベースへのアクセスについてだけ考えればよいことになる。 しかし、このやり方にも問題はある。データベースに依存することにより、データベースが使えなくなるとシステム全体が使えなくなる。データベースの構造変更にはコストがかかる。 それでもデータベースアーキテクチャは広く使われており、システム構築にあたって有益な方法である。
Layered System
レイヤードアーキテクチャーでは、コンポーネントを複数のレイヤーの内部に配置することを想定する。このとき、各レイヤー内のコンポーネントは、同じレイヤー内のコンポーネントか、隣接するレイヤーのコンポーネントとのみやりとりする。例えば、三層のレイヤーを想定したとき、一番上のレイヤーは真ん中のレイヤーとしかやりとりができず、一番下のレイヤーと直接やりとりすることはできない。
下部（コアに近い）レイヤーは、上のレイヤーにサービスを提供する。上部のレイヤーは下部のレイヤーから命令を受け取る。各レイヤーのインターフェースはシステムのニーズに応じて設計される。 このようにすると、関心の分離を行うことができる。レイヤーをプレゼンテーション層、ロジック層、データ層に分け、それぞれのレイヤーがそれぞれの役割に注力するなどである。 OSは関心の分離のよい例である。最下部にカーネル層がある。この層はハードウェアとのやりとりと、リソース配置を役割として受け持つ。その上にはシステム・アプリケーションライブラリ層がある。これはプログラミング可能な高レベルの機能（実装内ではカーネルとのやりとりを行う）を提供する。一番上にユーティリティ・アプリケーション層がある。ユーティリティはコマンドラインのようなツールであり、OSの機能をユーザーが実行したりファイル一覧を見たりすることができる。アプリケーションはユーザーによってインストールされる特定の用途のプログラムである。これらは下部のレイヤーに依存しているが、下部の実装を知らなくても使うことができる。
システムの実装をきれいレイヤー分けできないことも多い。また、隣接するレイヤーとしかやりとりができないということは、それだけオーバーヘッドを生む要因にもなる。 しかし、レイヤードアーキテクチャーは関心の分離・疎結合なシステムの構築に役立つ。
n-Tier/Multitier
n-Tierは、レイヤードアーキテクチャーと似ているが、各レイヤー内のコンポーネントが物理的に別のマシン内に存在することがある場合につかわれる。 2-Tierの具体的な例はクライアントとサーバーの関係である。サーバーがデータ操作やロジックその他の処理を行い、クライアントが処理の実行をサーバーに要求する。
3-Tierの具体的な例は、クライアント、アプリケーションサーバー、データベースサーバーという構成である。
Tierを追加すると、それだけシステム全体の複雑性は増す。障害発生時のリカバリーにも時間がかかることになる。 しかし、レイヤードアーキテクチャーの利点に加え、スケーラビリティの向上、集中管理、リソースの最適な配置などの利点により、n-Tierは一般的に使用されている。
Interpreter-Based Architecture
エクセルの計算式のように、ユーザー自身がスクリプトやマクロなどを書き、実行できる構造をInterpreter-Based Architectureという。 インタープリターは既存の機能からシステム上で作成され、インタープリターがスクリプトやマクロを実行する。このアーキテクチャーは柔軟性、ポータビリティというメリットがある。
