二分探索木(binary search tree)から近似値を求める
二分探索木(binary search tree)から近似値を求める
二分探索木のデータとtargetが与えられる。二分探索木のデータの中からtargetの近似値を求める。
例えば次のような二分探索木のデータとtarget 5が与えられるとき、答えは6である。
8
/\
3 10
/\ \
1 6 14
/\ /
4 7 13
ref: https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8
二分探索木の定義
二分探索木のデータ構造は「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。与えられた値の近似値を求めるには、一時的にそれまで見つかった近似値を保持しておいて、次の子ノード、孫ノード、…と子ノードが存在しなくなるまで探索を続ける必要があるため、計算量はどのアルゴリズムでも最低O(n)となるはず。
子ノードが存在しないときに保持していた近似値が解となる。
与えられる引数
引数はtreeとtargetが与えられる。
treeオブジェクトは数値value、treeオブジェクトleft、treeオブジェクトrightのプロパティを持つ再帰的なオブジェクト。targetは数値。
アルゴリズム実装(1) O(n)
ノードが存在しないとき、treeオブジェクトはnullをとる。近似値を保持しておいて、tree === nullとなるまでループを続ける。二分探索木の定義から、leftプロパティのvalueは必ず現在のノードのvalueより小さく、rightプロパティのvalueは必ず現在のノードのvalueより大きい。
function findClosestValueInBst(tree, target) { return traverseNode(tree, target, null); } function traverseNode(node, target, closest) { while (node !== null) { if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) { closest = node.value } if (target < node.value) { node = node.left } else if (target > node.value) { node = node.right } else { break } } return closest }
アルゴリズム実装(2) O(n)
メモリ的には優しくないかもしれないが、再帰関数のほうが理解しやすいかも？
function findClosestValueInBst(tree, target) { return traverseNode(tree, target, null); } function traverseNode(node, target, closest) { if (node === null) { return closest } if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) { closest = node.value } if (target < node.value) { return traverseNode(node.left, target, closest) } else if (target > node.value) { return traverseNode(node.right, target, closest) } return closest }
VS Code Extensionの公開を簡単にするCircleCI Orb作りました
VS Code Extensionの公開を簡単にするCircleCI Orb作りました
作りました: https://circleci.com/orbs/registry/orb/uraway/vsce
リポジトリ: https://github.com/uraway/vsce
使い方
環境変数としてVSCODE_MARKETPLACE_TOKENにPersonal Access Tokenをセットして、package.jsonのバージョンフィールドを更新してコミットすればあとは自動的に公開されます。
push-git-tagオプションをtrueにしてフィンガープリントもつければ、タグリリースやってくれるのでかんぺき。キャッシュの処理はキャッシュキーがややこしくなりそうなので、post-install-stepsとpre-install-stepsでユーザー定義にしました。
orbs: vsce: uraway/vsce@0.0.3 version: 2.1 workflows: test-publish: jobs: - vsce/publish: filters: branches: only: master post-install-steps: - save_cache: key: v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json" }} paths: - node_modules pre-install-steps: - restore_cache: keys: - v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json"}} - v1-node-cache-{{ .Branch }} - v1-node-cache- push-git-tag: true ssh-fingerprints: <フィンガープリント>
Orb開発
orbs: orb-tools: circleci/orb-tools@9.0.0 your-orb: your-namespace/your-orb@<<pipeline.parameters.dev-orb-version>> parameters: dev-orb-version: default: 'dev:alpha' type: string run-integration-tests: default: false type: boolean jobs: integration-tests: executor: orb-tools/ubuntu steps: - checkout version: 2.1 workflows: integration-tests_prod-release: jobs: - integration-tests - orb-tools/dev-promote-prod-from-commit-subject: add-pr-comment: true bot-user: your-namespace fail-if-semver-not-indicated: true publish-version-tag: true ssh-fingerprints: <フィンガープリント> filters: branches: only: master orb-name: your-namespace/your-orb requires: - integration-tests when: << pipeline.parameters.run-integration-tests >> lint_pack-validate_publish-dev: jobs: - orb-tools/lint - orb-tools/pack: requires: - orb-tools/lint - orb-tools/publish-dev: orb-name: your-namespace/your-orb requires: - orb-tools/pack - orb-tools/trigger-integration-tests-workflow: name: trigger-integration-dev requires: - orb-tools/publish-dev unless: << pipeline.parameters.run-integration-tests >>
orb-toolsをフルに使う
https://circleci.com/orbs/registry/orb/circleci/orb-tools
orb-tools、これはもうOrb開発に必須。だいたいこれで良い。v9.0.0になってまた使いやすくなりました。orb-tools/lint、orb-tools/pack、orb-tools/publish-devはもちろん便利ですが、orb-tools/dev-promote-prod-from-commit-subjectジョブがまた良い仕事してくれる。
- orb-tools/dev-promote-prod-from-commit-subject: add-pr-comment: true bot-user: your-namespace fail-if-semver-not-indicated: true publish-version-tag: true ssh-fingerprints: <フィンガープリント> filters: branches: only: master orb-name: your-namespace/your-orb
プルリクエストをマージするときに、下記図のようにコミットサブジェクトに[semver:patch|minor|major|skip]を入れるとsemverにそってプロモートしてくれます。
また、add-pr-comment: trueを渡して、環境変数PR_COMMENTER_GITHUB_TOKENとしてbot-userに対応するGitHubトークンをプロジェクトに追加すれば、そのプルリクエストに、Orb公開したよ、とコメントしてくれます。
さらに、publish-version-tag: trueを渡して、デプロイキーのフィンガープリントをセットすればタグコミットをプッシュしてくれます。さいこう
必要であればインテグレーションテスト
Orbによっては必要なこともあるインテグレーションテスト。vsce Orbでは、外部APIであるVS Code Marketplaceとの連携をテストしたいので、リポジトリ内にテスト用のVS Code Extension (vsce-orb-integration-test)を持ち、そのExtensionの公開・非公開をワークフロー内で繰り返しています。API制限とかあるのかな？
https://github.com/uraway/vsce
workflows: integration-tests_prod-release: jobs: - vsce/publish: name: publish-vsce publish-token-variable: VSCODE_MARKETPLACE_TOKEN push-git-tag: false package-path: vsce-orb-integration-test pre-install-steps: - restore_cache: keys: - v1-node-cache-{{ .Branch }}-{{ checksum "vsce-orb-integration-test/package-lock.json" }} - v1-node-cache-{{ .Branch }} - v1-node-cache- post-install-steps: - save_cache: key: v1-node-cache-{{ .Branch }}-{{ checksum "vsce-orb-integration-test/package-lock.json" }} paths: - node_modules - vsce/unpublish: name: unpublish-vsce publish-token-variable: VSCODE_MARKETPLACE_TOKEN package-path: vsce-orb-integration-test requires: - publish-vsce
2つの数の和
2つの数の和
2つ以上のユニークな数字の集合Aの中から、ターゲット(target)の数字の和となる数字のペアを見つけ出す。数字のペアは最大1つある。答えは値が小さい順に並べるとする。
例えばAが1, 10, 5, -1、12、targetが15であれば、答えは10, 5のペアである。Aを数字の配列の引数、targetを数字の引数としてこれを実装する。
アルゴリズム実装(1) O(n2)
最も簡単なアルゴリズムは二重ループして、すべての要素の和のパターンを出すこと。計算量はO(n^2)。使用しているsortは2つの数値の比較なので無視する。
function twoNumberSum(A, target) { for (let i = 0; i < A.length; i++) { for (let j = 0; j < A.length; j++) { if (i === j) continue; if (A[i] + A[j] === target){ return [A[i], A[j]].sort((a, b) => a - b) } } } return []; }
アルゴリズム実装(2) O(n)
計算し終えた要素を配列storeに保存していき、ワンループで済ます。計算量はO(n)
ループ中の数値をxとすると、ペアになる可能性のある数値yはtarget - xと表せる。storeにyが存在しなければ、xをstoreに保存する。
こちらも使用しているsortは2つの数値の比較なので無視する。
function twoNumberSum(A, target) { const store = [] for (const x of A) { const y = target - x if (store.includes(y)) { return [x, y].sort((a, b) => a - b) } else { store.push(x) } } return []; }
includesの実装が気になる。ハッシュテーブルに保存のほうがいいかも？
アルゴリズム実装(3) O(n log n)
まず、Aを小さい順に並び替える。ソートに関しては、JavaScriptの実装はブラウザにもよるがここではクイックソート、計算量O(n log n)とする。
[-1, 1, 5, 10, 12]
現在の最小の値のインデックスをmin、最大の値のインデックスをmaxとおくと
sum = array[left] + array[right]
となる。sumがtargetより大きい場合、値を小さくしたいのでrightを小さくする。逆にsumがtargetより小さい場合、値を大きくしたいので、leftを小さくする。
例えば初期状態でleft=0、right=4であるためsum=11
left right | | [-1, 1, 5, 10, 12]
targetはそれより大きいのでleftを右に動かしてleft=1、right=4ならばsum=13
left right
| |
[-1, 1, 5, 10, 12]
targetはそれより大きいのでleftを右に動かしてleft=2、right=4ならばsum=17
left right
| |
[-1, 1, 5, 10, 12]
targetはそれより小さいのでrightを左に動かしてleft=2、right=3ならばsum=15
left right
| |
[-1, 1, 5, 10, 12]
クイックソートと一回のループの計算量は
O(n log n) + O(n) = O (n log n)
であることからO(n log n)
答えのペアはユニークな数値となることに注意してこれを実装すると
function twoNumberSum(A, target) { A.sort((a, b) => a - b) let left = 0 let right = A.length - 1 while (left < right) { const sum = A[left] + A[right] if (sum === target) { return [A[left], A[right]] } else if (sum < target) { left++ } else if (sum > target) { right-- } } return []; }
バイナリサーチ
バイナリサーチ
問: ソートされた数値の配列と数値targetを受け取り、配列中のtargetのインデックスを求める。その際、バイナリサーチを用いること。
アルゴリズム実装 $O(\log n)$
配列の要素数をnとしたとき、left=0、right=nの変数を作る。また、leftとrightの中央の位置をmidとする。
array[mid] === targetならtargetが見つかったとして探索終了。left >= rightなら見つからなかったとして探索終了。array[mid] > targetならtargetは配列の左半分にあるので、right=mid-1として0へarray[mid] < targetならtargetは配列の右半分にあるので、left=mid+1として0へ
function binarySearch(array, target) { let left = 0 let right = array.length - 1 while (left <= right) { const mid = Math.floor((left + right) / 2) if (array[mid] > target) { right = mid - 1 } else if (array[mid] < target) { left = mid + 1 } else { return mid } } return -1 }
バイナリサーチは一回実行するごとに対象の配列の要素数が1/2になる。最悪の場合要素数が1になるまで実行されるので、計算量はその繰り返し回数をkとすると
底数を無視して、$O(\log n)$となる
VPC Peeringを使って、異なるVPCにあるRDSとEC2を接続する
VPC Peeringを使って、異なるVPCにあるRDSとEC2を接続する
VPC Peeringとは
VPC Peeringを設定する
VPC Peeringを作成する
EC2インスタンスから、同一アカウント、同一リージョン、異なるVPCにあるRDSへのアクセスを設定したいとする。
マネジメントコンソールからVPC設定を開いて、"Create Peering Connection"をクリック、項目を入力してVPC Peeringを作成する
| 項目 | 説明 |
|---|---|
| Peering connection name tag | 識別名 |
| VPC (Requester)* | 接続元のVPC |
| Account | 接続先のAWSアカウント |
| Region | 接続先のAWSリージョン |
| VPC (Accepter)* | 接続先のVPC |
Routeを追加する
VPC Peering作成しただけではトラフィックのルートができないので、Route Tablesから、ルートを追加する。
接続元のVPC Route Table
| Destination | Target |
|---|---|
| (接続元のCIDRs) | local |
| (接続先のCIDRs) | (作成したVPC Peering) pcx-*** |
接続先のVPC Route Table
| Destination | Target |
|---|---|
| (接続先のCIDRs) | local |
| (接続元のCIDRs) | (作成したVPC Peering) pcx-*** |
Security Groupsを設定する
接続元のインスタンスから、接続先のRDSに対してincoming trafficを許可する。
| Type | Protocol | Port Range | Source |
|---|---|---|---|
| お好み | TCP | お好み | 接続元のセキュリティグループ |
VPC Peeringの設定が上手くいっていない場合、ここで「異なるVPC間のセキュリティグループは設定できない」旨のエラーが出る。
DNS解決を許可する
上記までの設定で、プライベートIPアドレスを用いればルーティングが可能になるが、RDSはプライベートIPアドレスが固定ではないため、ルーティングにはDNS名を使いたい。
なので作成したVPC Peeringの"Edit DNS Settings"からDNS resolutionを許可して、DNS名でアクセスできるようにする。
Palindrome Check (回文チェック) アルゴリズム
Palindrome Check (回文チェック) アルゴリズム
文字列stringを受け取って、回文かどうかをチェックする。すべての文字を比較しないといけないので、どうやっても計算量が$O(n)$以上になるはず。
アルゴリズム実装(1) $O(n)$
両端から文字が等しいか比較していく:
function isPalindrome(string) { let left = 0 let right = string.length - 1 let result = true while (left <= right) { if (string[left] === string[right]) { left++ right-- } else { result = false break } } return result }
アルゴリズム実装(2) $O(n)$
文字の位置を反転させたreversedString文字列とstringの比較:
function isPalindrome(string) { const reversedString = [] for (let i = string.length - 1; 0 <= i; i--) { reversedString.push(string[i]) } return string === reversedString.join('') }
フィボナッチ数列のアルゴリズム
フィボナッチ数列のアルゴリズム
勉強がてらメモ
フィボナッチ数列とは
「フィボナッチ数列」とは「前の２つの数を加えると次の数になる」という数列。1番目は0、2番目は1。n番目の数字は(n - 1)番目と(n - 2)番目の数字の和。
例えば、6番目の数は5 (0, 1, 1, 2, 3, 5)
アルゴリズム実装(1) O(n2)
n番目のフィボナッチ数をfib(n)とすれば、
fib(4)を求めるには
1 fib(4)
________________|________________
| |
2 fib(3) fib(2)
________|________ ________|________
| | | |
4 fib(2) fib(1) fib(1) fib(0)
________|________
| |
0 fib(1) fib(0)
となるので、計算量はO(n^2)
1番目と2番めの例外に注意してこれを実装すると次のようになる:
function getFib(n) { if (n === 2) { return 1 } else if (n === 1) { return 0 } return getFib(n - 1) + getFib(n - 2) }
アルゴリズム実装(2) O(n)
先程の樹形図を見ると、fib(2)などすでに答えがでているものでも計算しているので、改善の余地があることに気づく。
一度出した答えを覚えておいて再利用できるならば、fib(4)の答えを得た時、例えばfib(6)を新たに求めたい場合は
であるが、fib(4)の答えはわかっているので、fib(5)だけを求めれば良い。同様にfib(n)を求めたい時、fib(n - 1)だけを求めれば良いから計算量はO(n)
これを実装するとき、fibStore配列にフィボナッチ数列を格納する。インデックスiの数字はfibStore[i - 1] + fibStore[i - 2]である。したがって
function getFib(n) { if (n === 2) { return 1 } else if (n === 1) { return 0 } const fibStore = [0, 1]; for (let i = 2; i < n; i ++) { const ithFib = fibStore[i - 1] + fibStore[i - 2] fibStore[i] = ithFib } // n番目のフィボナッチ数 (インデックス n - 1) return fibStore[n - 1]; }
