バイナリサーチ
バイナリサーチ
問: ソートされた数値の配列と数値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('') }
フィボナッチ数列のアルゴリズム
フィボナッチ数列のアルゴリズム
勉強がてらメモ
フィボナッチ数列とは
「フィボナッチ数列」とは「前の2つの数を加えると次の数になる」という数列。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でリネーム可能になるかもしれん。
日本語でのサポートチケットにも対応してるらしいので、もし間違えて名前をつけてしまったら問い合わせてみよう。
コンポーネントのマウント時にリクエストし、アンマウント時にキャンセルする axios リクエスト
とりあえず解はこうなった。
ライブラリのバージョン
- axio 0.18.0
- react 16.8.3
- react-dom 16.8.3
動作確認はこちら:
ボタンクリックでコンポーネントのマウント・アンマウントが切り替えできる。APIリクエスト中にアンマウントされると、下のようなエラーメッセージと共にリクエストがキャンセルされる。
解説
解説というものでもないかもしれないが、ちょっと説明。
useEffect
でマウント時のAPIリクエストのメソッドにキャンセルトークンソースを渡す。また、useEffect
の戻り値はアンマウント時に実行されるので、ここでAPIリクエストのキャンセルを定義する。
function useAxios(fetchAction) { useEffect(() => { const signal = axios.CancelToken.source(); fetchAction({ signal }); return () => { signal.cancel("Api is being canceled"); }; }, []); }
あとはaxios
にキャンセルトークンを渡すだけ:
useAxios(({ signal }) => { async function getUser() { const res = await axios.get("https://randomuser.me/api/", { cancelToken: signal.token }); setResult(res.data.results[0]); } getUser(); });
react-router
との組み合わせが便利なんじゃなかろうか。