よく使うコマンドをまとめる（自分用メモ）

Linux(shellコマンド)

ファイル検索

`dir/` 配下の`.py` または `.ipynb` ファイルで `hogehoge` を含むものを検索したい

grep -r --include='*.py' --include='*.ipynb' "hogehoge" dir/

`dir/` 配下の特定の文字列を含むファイルを一括で置換したい

例えば、 calender のタイポを一括で修正したい場合

find dir/* \( -name "*.py" -o -name "*.ipynb" \)  | xargs sed -e 's/calender/calendar/g' -i

mac OS の場合, POSIX sed が標準で入っているので上書きしてしまってから実行するとよい

brew install gnu-sed --with-default-names

git

複数に分かれたコミットをまとめたい

すでに作成したコミットに対して、些細な修正を加えた場合など

git add hoge.py
git commit -m "Add important method"
git add hoge.py
git commit -m "些細な fix"

git rebase -i HEAD~~
# "些細な fix" のコミットを `pick` から `f` (`fixup`) に変更することで、直前のコミットにまとめられる
git push -f origin feature/branch_name

git rebase を行うとそれ以後のハッシュ値が変更されてしまうので、main ブランチを marge した後は行わないのが無難

terraform

tfstate ファイルから `hoge.tf` に含まれるリソースを一括で削除する

grep "resource" hoge.tf | sed -e "s/resource //g" -e "s/\" \"/\./g" -e "s/\"//g" -e "s/ {//g" | xargs -I arg terraform 
state rm arg

count や for_each で作成したリソースがどうなるかは検証していません

tfstate ファイルに稼働中のリソースを紐づける

事前に resource "aws_subnet" "example" を .tf ファイルに記載しておく

terraform import aws_subnet.example subnet-01234567890123456

コンソールから手作業で作ったリソースを紐づけるときに便利

tfstate ファイルに紐づいたリソースの状態を見る

terraform state show aws_subnet.example

ここから適当にコピペして .tf ファイルに転記すると手作業で作ったリソースを削除せずにIaCができるが、以下に注意

他のリソースの値がリテラルで入る( instance_id = i-hogehoge などとされてしまう)ので、aws_instance.example.id などで書き換える
id や arn などの自動的に決まるべき値も出力されるため、適宜削除する必要がある
セキュリティーグループルールなど、忘れがちなリソースがあるので、検証環境で横着せずいったん削除してから作り直しておくと安心

tfstate ファイルの内容を全件見る

terraform show -json | jq . | tee current_tfstate.json

パスワードなどの機微情報も見えてしまうので、作業したらファイルを消すこと、パブリックな環境では実行しないこと

AWS

SSMを使って踏み台サーバーを経由せずにSSHトンネリングを実現する

aws ssm start-session \
    --target i-hogehoge --document-name AWS-StartPortForwardingSession \
    --parameters "portNumber=80, localPortNumber=56789" \
    --region ap-northeast-1 --profile profile_name```

この状態で localhost:56789 にアクセスするとトラフィックが i-hogehoge の 80番ポートにリダイレクトされる

windows(command prompt)

AWS

SSMを使って踏み台サーバーを経由せずにSSHトンネリングを実現する

aws ssm start-session --target i-hogehoge --document-name AWS-StartPortForwardingSession --parameters "portNumber=3389, localPortNumber=13389" --region ap-northeast-1 --profile profile_name

この状態で「リモートデスクトップ接続」から localhost:13389 に接続すると i-hogehoge にRDP接続することができる。

i-hogehoge は Windowsマシンであること
ログイン時に求められるユーザー名は Administrator, パスワードはEC2のコンソール画面から取得する
ちなみに、Windows マシンは Linux マシンに比べて（同一スペックの場合）割高です

2021-06-17

離散カントロビッチ問題のエントロピー正則化とその双対問題

最適輸送理論数理最適化

離散カントロビッチ問題とは？

次のような問題を考えます

商品を $n$ 個の工場から, $m$ 個のお店に輸送することを考えます.
商品の輸送に掛かる労力が「重量」と「始点と終点の距離」の積で決まっているとき,
トータルの労力が最小になるような運び方はどんなものでしょうか？

2021-04-16

Python で mod. p での二項係数 (nCk mod. p) の求め方

python 組合せ

過去記事, Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっきでは, modの下での階乗の逆元を求めました.

本記事では, 以下の記事を参考にして二項係数 ${}_nC_k$ を前処理 $O(N)$ , 実行 $O(1)$ で行うアルゴリズムを紹介します.
drken1215.hatenablog.com

2021-03-20

AHC001（マラソンマッチ）の参加者の使用言語の分布を調べてみた

プログラミングコンテストマラソン

競技プログラミングコンテストサイトである AtCoder のマラソン部門のコンテストに参加してみました： atcoder.jp 本記事では、コンテスト参加者の使用しているプログラミング言語はどういうものがあるのかを順位から調査してみました。

2021-02-27

ABC192 D - Base n を Python で解いてみる

ABC-D AtCoder python プログラミングコンテスト

問題概要

atcoder.jp

数字列 $X$ を $n$ 進法表記と見なしたとき, $M$ 以下になるような値が何種類あるか求めよ.

ただし, $n$ は $X$ に含まれる数字より大きいものとする.

考えたこと

入力例 1

22
10

22 を 3 進数と見なすと, $2\times 3 + 2 = 8 \leqq 10$
22 を 4 進数と見なすと, $2\times 4 + 2 = 10 \leqq 10$
22 を 5 進数と見なすと, $2\times 5 + 2 = 12 > 10$
22 を 6 進数と見なすと, $2\times 6 + 2 = 14 > 10$

により, 最初の2つだけが条件を満たします.

このことから, $n$ が小さいときには条件を満たし, $n$ を大きくするにつれて $M$ を超えてしまう閾値を見つければよさそうです.

以下, $X$ の長さが $K$ であるとし, $k$ 桁目を $a_k$ ( $a_k\leqq d$ )と表します. このとき, $X$ を $n(>d)$ 進法表記と見なすと,

[tex: \displaystyle X_n = \sum_{k=0}^{K-1} n^k a_k ]

と表すことができ, これは $X$ が二桁以上の場合には, $n$ について単調増大であり, したがっていつかは $M$ よりも大きくなります.

一方で, $X$ が一桁の場合には, 何進法表記であっても

$\displaystyle X_n = a_0$

です. いくら $n$ を大きくしても $M$ を超えないことがあり得ますが, 問題文で問われているのは $M$ 以下になるような値が何種類あるかであるため, $X$ そのものが $M$ 以下であれば $1$ が, そうでなければ $0$ が解答になります

解いていく

まずは, 入力を受け取ります. 数字列 $X$ は整数として入力されますが, $n$ 進数展開を行うことを見越してリストとして受け取りましょう.

X = [int(k) for k in list(input())]
d = max(X)
M = int(input())

また, 数字列 $X$ を $n$ 進数展開したときの値を p_adic(X, n) により計算します.

def p_adic(X, p):
  curr = 0
  for k in X:
    curr += k
    curr *= p
  curr //= p
  return curr

以下のようなコードだと, TLEしてしまいます

for ループが $O(M)$ の例 1

ans = 0
for j in range(d+1, M+1):
  if p_adic(X,j) <= M:
    ans += 1

print(ans)

for ループが $O(M)$ の例 2

ans = 0
for j in range(d+1, M+1):
  if p_adic(X,j) <= M:
    ans = j - d
  else:
    break

print(ans)

今回の制約では $M \leqq 10^{18}$ のため, より高速なアルゴリズムを構築する必要があります.

二分探索

今回の問題では $n$ が小さいときには条件を満たし, $n$ を大きくするにつれて, ある閾値を超えると条件を満たさなくなるという単調性があります.

したがって, その閾値を探す問題に帰着することができます. その際には,

は条件を満たすか？
- 満たさないならば閾値は $0$ から $M/2$ の間にある
- 満たすならば閾値は $M/2$ から $M$ の間にある

という性質を使って, 条件の範囲を1ステップごとに半分にしていくことができます. 効率よく探すことで, $O(\log M)$ の計算量で以上の閾値を求めていきましょう.

一般の二分探索については qiita.com

特に Python の二分探索をうまく書く方法については www.forcia.com

がそれぞれ読みやすく, 参考になります. ポイントとしては,

左端が True, 右端が False となるように初期値 ok, ngを設定する
中央値 (ok + ng)//2 での条件を判定する
- 左端が True, 右端が False となる状態を維持しながら ok, ngを変更する
ok と ng の差が1になったとき, ok の値が「条件を満たす $j$ の上限」である

ことになります.

解いていく

以上を踏まえて, - $X$ が一桁の場合がコーナーケースになっていることに注意する - 「 $X$ を $j$ 進数展開した結果が $M$ 以下である」をis_ok(j)と表記し, 二分探索で最大の $j$ を求める - 答えとして $j - d$ を出力する

を行うことにより, ACすることができます

X = [int(k) for k in list(input())]
d = max(X)
M = int(input())

def p_adic(X, p):
  curr = 0
  for k in X:
    curr += k
    curr *= p
  curr //= p
  return curr

def is_ok(j):
  curr = p_adic(X, j)
  if curr <= M:
    return True
  else:
    return False

if len(X) == 1:
  if X[0] <= M:
    print(1)
  else:
    print(0)
  import sys
  sys.exit()

ok = d
ng = M + 1
while ng - ok > 1:
  mid = (ok + ng) // 2 # 平均(小数切り捨て)
  if is_ok(mid):
    ok = mid
  else:
    ng = mid

print(ok-d)

atcoder.jp

2021-02-23

SIRモデル方程式を数値的に解いて、gifで表示させてみる

数値計算数学 python

伝染病の拡大過程を記述するSIRモデル
$\begin{equation} \left\{ \begin{split} S′(t)&=−βS(t)I(t),\\ I′(t)&=βS(t)I(t)−γI(t),\\ R′(t)&=γI(t) \end{split} \right. \end{equation}$
の初期値問題を Python で解き, 得られた解をgifにします.
f:id:wakabame:20210223221730g:plain

PCとインターネットがあればどなたでも, 以下のノートブックを逐次実行することでgifファイルを生成することができます.
colab.research.google.com

2020-10-05

水素原子の基底状態解は原点での値を用いずに特徴付けられる

偏微分方程式数学

3次元空間における水素原子ハミルトニアンに対する固有値問題 *1

\begin{equation}
-\dfrac{1}{2}\Delta \psi - \dfrac{1}{|x|} \psi = E \psi,\quad x \in \mathbb{R}^3
\end{equation}

について, 1s軌道に対応する基底状態解を考察します.

よく知られているように, 基底状態解は球対称であるため,
$u(|x|) = \psi(x)$ と変換することにより, 未知関数 $u: [0,+\infty)\rightarrow \mathbb{C}$ についての方程式

\begin{equation}
\left(-\dfrac{1}{2}\dfrac{d^2}{dr^2} -\dfrac{1}{r}\dfrac{d}{dr} -\dfrac{1}{r}\right)u = E u,\quad r \in (0,\infty) \tag{1}
\end{equation}

と変形できます.
さらに, (1) に対して, $r^2 \bar{\phi}$ をかけて部分積分することにより弱形式

\begin{equation}
\left\langle \dfrac{r}{2}\dfrac{du}{dr}, \dfrac{r}{2}\dfrac{d\phi}{dr}\right\rangle
- \left\langle \sqrt{r}u, \sqrt{r}\phi \right\rangle
=E \left\langle ru, r\phi\right\rangle \tag{2}
\end{equation}

を得ます*2.

本記事では, 1次元における固有値問題 (1) に焦点を当てて, 適当な関数空間での変分問題と見なすことで, 特に陽に境界条件を与えることなく基底状態解が得られることを解説していきます.

また, 本記事は有限要素法による数値計算について紹介している, dc1394さんの記事
qiita.com
についての考察を兼ねています.
モデリングや数値計算の箇所を読んでいて, 境界条件を設定していないように見えるのに, 正しく基底状態解が得られていることが気になり調べてみました.
なお, 弱形式の導出などについても紹介記事にて丁寧に行われているため, 気になる方はそちらを参考にしてみてください.

*1:単に, シュレディンガー方程式とも呼びます

*2:部分積分から境界項が出ますが, その項が 0 になるよう $\bar{\phi}$ が良い性質を持っていることを仮定しますが, ここでは細かいことは気にしない.

Linux(shellコマンド)

ファイル検索

dir/ 配下の.py または .ipynb ファイルで hogehoge を含むものを検索したい

dir/ 配下の特定の文字列を含むファイルを一括で置換したい

git

複数に分かれたコミットをまとめたい

terraform

tfstate ファイルから hoge.tf に含まれるリソースを一括で削除する

tfstate ファイルに稼働中のリソースを紐づける

tfstate ファイルに紐づいたリソースの状態を見る

tfstate ファイルの内容を全件見る

SSMを使って踏み台サーバーを経由せずにSSHトンネリングを実現する

windows(command prompt)

SSMを使って踏み台サーバーを経由せずにSSHトンネリングを実現する

離散カントロビッチ問題とは？

考えたこと

解いていく

以下のようなコードだと, TLEしてしまいます

二分探索

解いていく

`dir/` 配下の`.py` または `.ipynb` ファイルで `hogehoge` を含むものを検索したい

`dir/` 配下の特定の文字列を含むファイルを一括で置換したい

tfstate ファイルから `hoge.tf` に含まれるリソースを一括で削除する