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]; }
No such file or directory - bs_fetch:atomic_write_cache_file:chmod
No such file or directory - bs_fetch:atomic_write_cache_file:chmod
docker-composeを使ってサーバーとsidekiq両方を動かそうとすると次のようなエラーが出る場合があります:
$ docker-compose up app_1 | [12] Puma starting in cluster mode... app_1 | [12] * Version 4.1.0 (ruby 2.6.3-p62), codename: Fourth and One app_1 | [12] * Min threads: 5, max threads: 5 app_1 | [12] * Environment: development app_1 | [12] * Process workers: 2 app_1 | [12] * Preloading application app_1 | [12] ! Unable to load application: Errno::ENOENT: No such file or directory - bs_fetch:atomic_write_cache_file:chmod app_1 | bundler: failed to load command: puma (/usr/local/bundle/bin/puma) app_1 | Errno::ENOENT: No such file or directory - bs_fetch:atomic_write_cache_file:chmod app_1 | /usr/local/bundle/gems/bootsnap-1.4.5/lib/bootsnap/compile_cache/iseq.rb:37:in `fetch'
簡略化しますが、docker-compose.ymlはだいたいこんなかんじ。appを2つのコンテナが共有している状態:
version: "3" services: app: build: . command: bundle exec puma volumes: - .:/app ports: - "8080:8080" links: - redis sidekiq: build: . command: bundle exec sidekiq volumes: - .:/app links: - redis redis: image: redis volumes: - ./tmp/db:/var/lib/redis/data
おそらく、サーバーが立ち上がってからbootsnapで生み出されるapp/tmp/cacheをappコンテナとsidekiqコンテナの両方が読み込もうとしてエラーが起きている様子。であれば、キャッシュフォルダをマウントしないか、bootsnapをsidekiqコンテナでは使わないようにしてあげれば良さそうです
volumes: - .:/app /app/tmp/cache
CircleCIのorb namespaceをリネーム(あるいは削除)したい
TL;DR
表題について
namespace を作り間違えたので、リネーム方法を探したところ、ドキュメントに次の一文が:
Note: Namespaces cannot be removed or renamed once you have claimed a namespace.
コミュニティフォーラムでもnamespaceを削除したいという質問を発見したが、
There is no way to delete the namespace right now. We can rename a namespace if you open up a support ticket.
サポートに連絡してくれとの回答だったので、素直にここから連絡
すると、ものの20分位でリネームに対応してくれた。
Hi Masato,
Currently namespace renames are only possible with assistance from Support. I've gone ahead and renamed the namespace to uraway for you, let me know if there are any issues!
"Currently"って言ってるので、もしかしたらこの先CLIでリネーム可能になるかもしれん。
日本語でのサポートチケットにも対応してるらしいので、もし間違えて名前をつけてしまったら問い合わせてみよう。
