2020-03-05

VSCodeのShortCutKeys

VSCode

概要

VSCodeのShortCutKeysを忘れてしまうのでメモする。

環境

移動系

key	command	when
ctrl+h	workbench.action.focusSideBar	editorTextFocus
ctrl+j	workbench.action.terminal.focus	editorTextFocus
ctrl+l	workbench.action.focusFirstEditorGroup	filesExplorerFocus
ctrl+k	workbench.action.focusFirstEditorGroup	terminalFocus
cmd+k+→	エディタを分割後にアクティブなエディタを移動
ctrl+1, 2,...	同じエディタ内でのファイル移動

*ctrl+h, ctrl+j, ctrl+l, ctrl+kは編集した。VSCodeのkeybindings.jsonを編集してより便利に

ファイル系

key	command	when
ctrl+n	explorer.newFile
cmd+w	ファイルを閉じる
l	サイドバーのファイルを編集

*ctrl+nは編集した。VSCodeのkeybindings.jsonを編集してより便利に

サイドバー

key	command	when
com+b	表示/非表示

2020-01-25

bitsetの使い方

AtCoder

概要

bit演算子を勉強しようしよう思っていたのですが、以下の問題にぶち当たってようやくやる気になりました。bitsetの使い方がわかればbit演算子の威力がご理解いただけると思う。自分は思い知った。。。

問題

https://atcoder.jp/contests/abc147/tasks/abc147_e

bitsetの有用性

この問題は回答方針が決まってもTLEとなってしまう。最初はデータの保存をsetで管理していたのが問題だった。ACの人のコードを見てみると、bit演算を使って何やらかっこよく記述していた。尊敬の眼差しでした。自分なりの理解をした結果、bitsetでできることは、同じ値を足す、引くといった作業を繰り返す処理を一発でできるということ。ん、どういうこと？

bitset

その前に、bitsetについて簡単に解説する。bitsetは右からi番目（0からスタート）にその数値があるかないかを表す。百間は一見にしかずということで以下の例を見て欲しい。

数値	bitset
0	0
1	10
2	100
3	1000
[1, 3]	1010
[0, 2, 3]	1101

同じ値を足す、引く

このbitsetを使えば、同じ値を足す、引くという操作が一瞬で行える。例えば、以下のようなリストの各値に2を足したいとする。

a = [1, 2, 1, 4]

pythonで普通に書くと以下のようになる。リストの要素が大きくなるとかなり時間がかかってしまう。

for i in range(4):
    a[i] += 2

bitsetを使うと、この処理を一瞬でできる。

b = b << 2 #2を足す
b = b >> 2 #2を引く

コード

def run():
  ofs = 1000
  H, W = map(int, input().split())
  dp = [[0 for w in range(W)] for h in range(H)]
  a = [list(map(int, input().split())) for i in range(H)]
  b = [list(map(int, input().split())) for i in range(H)]
  c = [[abs(a[i][j] - b[i][j]) for j in range(W)] for i in range(H)]
  dp[0][0] = (1 << ofs + c[0][0]) | (1 << ofs - c[0][0])
  for h in range(1, H):
    dp[h][0] = (dp[h-1][0] << c[h][0]) | (dp[h-1][0] >> c[h][0])
  for w in range(1, W):
    dp[0][w] = (dp[0][w-1] << c[0][w]) | (dp[0][w-1] >> c[0][w])
  for h in range(1, H):
    for w in range(1, W):
      v = c[h][w]
      dp[h][w] = (dp[h-1][w] << v) | (dp[h-1][w] >> v)
      dp[h][w] |= (dp[h][w-1] << v) | (dp[h][w-1] >> v)
  s = list(bin(dp[-1][-1] >> ofs))
  for i in range(len(s)):
    if s[-1-i] == '1':
      print(i)
      break
 
if __name__ == '__main__':
  run()

参考文献

Python ビット演算超入門
 ABC147 E Balanced Pathでbitset高速化を完全に理解する
 Balanced Path [AtCoder Beginner Contest 147 E]

2020-01-25

ABC147 D - Xor Sum 4 をPythonで考える

AtCoder

概要

題ではPythonで考えると書きましたが、正確にはPythonではなくPyPy3でACでした。Pythonで通らなくてもPyPyで通ることがたまにある。。。bitsetの有用性に気付いた初めての問題でした。

問題

ABC147 D - Xor Sum 4

方針

dpでとく。dp[i][j]にはA_i番目までの全てのAの2^jの位に1がいくつ含まれるかを格納する。

コード

def run():
  bit = 60
  N = int(input())
  a_li = list(map(int, input().split()))
  ans = 0
  dp = [[0]*bit for i in range(N)]
  for i in range(bit):
    dp[0][i] = (a_li[0] >> i) & 1
  for i in range(1, N):
    for j in range(bit):
      a_j = (a_li[i] >> j) & 1
      dp[i][j] = dp[i-1][j] + a_j
      if a_j == 1:
        ans += (i-dp[i-1][j]) << j
      else:
        ans += dp[i-1][j] << j
  print(ans%(10**9+7))
 
if __name__ == '__main__':
  run()

2019-12-16

Support Vector Regressorの実装（sklearn）

sklearn Python Python-sklearn

概要

sklearnのSupport Vector Regressor(SVR)は主にSVR, NuSVR, LinearSVRの三種類がある。LinearSVRの方がSVRより計算が若干早く、NuSVRはSVRとLinearSVRと実装の仕方が若干違う。詳しくはこちら。今回は一般的なSVRを使用する。

注意点

今回の実装ではsklearnバージョン0.21.2を使用したが、参考文献としてはバージョン0.22のドキュメントを参考にしている点に注意してほしい。しかし、今回の実装では、バージョンによるデフォルト設定が少し違ったものの、それ以外はほとんど変わらない。

環境

sklearn 0.21.2

デフォルトパラメータ

from sklearn.svm import SVR

model = SVR()

SVR(C=1.0, cache_size=200, coef0=0.0, degree=3, epsilon=0.1,
    gamma='auto_deprecated', kernel='rbf', max_iter=-1, shrinking=True,
    tol=0.001, verbose=False)

パラメータ

kernel (rbf) : linear, poly, rbf, sigmoid, precomputedから選択可能
- linear : $\left\lt x, x'\right\gt$
- poly : $(\gamma\left\lt x, x'\right\gt + r) ^ d$
- rbf : $\rm{exp}(-\gamma|x-x'| ^ 2)$
- sigmoid : $(\rm{tanh}(\gamma\left\lt x, x'\right\gt + r)$
degree (3) : kernelがpolyのときのみ有効。 $d$ のこと。
gamma (auto) : kernelがrbf, poly, sigmoidのときに有効。scale, auto, 数値から選択可能。のこと。
- scale : 1 / (n_features * X.var())
- auto : 1 / n_features
coef0 (0) : kernelがpoly, sigmoidのときに有効。 $r$ のこと。
tol (1e-3) :
C (1.0) : 正則化に使用。l2正則化を行う
epsilon (0.1) :

実装

今回はrbfカーネルを使用する。よって、gamma, C, epsilonの３つのパラメータを決める。

データ

ボストンデータを利用する。訓練、テストデータに分離した後、スケーリングする。

from sklearn.datasets import load_boston
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

data = load_boston()
x_train, x_test, y_train, y_test = train_test_split(data['data'], data['target'], test_size=0.2, random_state=0)
scaler = StandardScaler()
scaler.fit(data['data'])
x_train = scaler.transform(x_train)
x_test = scaler.transform(x_test)

モデル

from sklearn.svm import SVR

model = SVR()

ハイパーパラメータチューニング

今回のハイパーパラメータはC, epsilon, gammaの３つ。グリッドサーチクロスバリデーションで最適化する。5-fold cross validationをする。

n_splits = 5
params = {'C' : [1], 'epsilon' : [1], 'gamma' : ['scale']}

gammaをまずscaleに固定して他のパラメータを調整する。グリッドサーチや１つのパラメータチューニングはRidge回帰の実装で定義されている関数(gscv, search_param1)を使う。GridsearchCV を利用しても内容はほとんど変わらない。今回は、二つのパラメータチューニングの結果をヒートマップで可視化してみる。

def ShowHeatMap(df, param1_name, param2_name):
    x = df.columns
    y = df.index
    score_max = df.max().max()
    score_min = df.min().min()
    fig = plt.figure(figsize=(10, 6))
    ax = fig.add_subplot(111)
    im = ax.imshow(df, interpolation='nearest', vmin=score_min, vmax=score_max, cmap='Reds')
    fig.colorbar(im)
    ax.set_xticks(range(0, len(x)))
    ax.set_yticks(range(0, len(y)))
    ax.set_xticklabels(x)
    ax.set_yticklabels(y)
    ax.set_ylabel(f'param_{param1_name}')
    ax.set_xlabel(f'param_{param2_name}')
    plt.show()

次に、ハイパーパラメータをチューニングするパイプラインを関数で定義する。ハイパーパラメータをチューニングし、グラフを表示し、もっともよかったパラメータを自動的に更新する。

def search_param2(param1_name, param1_values, param2_name, param2_values, params):
    new_params = params.copy()
    new_params[param1_name] = param1_values
    new_params[param2_name] = param2_values
    print(f'set new_params: {new_params}')
    results = gscv([x_train, y_train], new_params)
    cv_score_li = results['validation_score_mean']
    best_index = cv_score_li.index(max(cv_score_li))
    print(f"cv score: {results['validation_score_mean'][best_index]:.2f}+-{results['validation_score_std'][best_index]:.3f}")
    print(f"best params: {results['params'][best_index]}")
          
    scores = results['validation_score_mean']
    param1_li = results[f'param_{param1_name}']
    param2_li = results[f'param_{param2_name}']
    cv_data = np.stack([scores, param1_li, param2_li], axis=1)
    cv_data = sorted(cv_data, key=lambda x: (x[1], x[2]))
    scores = np.array(cv_data).T[0].astype(float)
    x = sorted(new_params[param1_name])
    y = sorted(new_params[param2_name])
    scores = scores.reshape((len(x),len(y)))
    df = pd.DataFrame(scores, columns=y, index=x)
    display(df )
    ShowHeatMap(df, param1_name, param2_name)
    params[param1_name] = [results['params'][best_index][param1_name]]
    params[param2_name] = [results['params'][best_index][param2_name]]

実行する。

search_param2('C', [0.01, 0.1, 1, 10, 100, 1000], 'epsilon', [0, 0.01, 0.1, 1, 10, 100], params)

set new_params: {'C': [0.01, 0.1, 1, 10, 100, 1000, 10000], 'epsilon': [0, 0.01, 0.1, 1, 10, 100], 'gamma': ['scale']}
cv score: 0.87+-0.041
best params: {'C': 100, 'epsilon': 1, 'gamma': 'scale'}

f:id:oosakik:20191216011040p:plain

Cが100、epsilonが1で最も良い結果が出た。次に、gammaをsearch_param1を使って検証してみる。

search_param1('gamma', [0, 0.001,  0.01, 0.1, 1, 10, 100, 1000], params )

set new_params: {'C': [100], 'epsilon': [1], 'gamma': [0, 0.001, 0.01, 0.1, 1, 10, 100, 1000]}
cv score: 0.86+-0.031
best params: {'C': 100, 'epsilon': 1, 'gamma': 0.1}

f:id:oosakik:20191216011113p:plain `

gamma`は0.01がベストであった。

訓練と予測

#train
for k, v in params.items():
    params[k] = v[0]
model.set_params(**params)
model.fit(x_train, y_train)

#predict
y_pred = model.predict(x_test)

結果と分析

決定係数は組み込み関数で計算できる。

r2 = model.score(x_test, y_test)
print(r2)

0.768769885637091

予測した値をプロットする。

import matplotlib.pyplot as plt
fig = plt.figure(figsize=(6,6))
ax = fig.add_subplot(111)
ax.scatter(y_test, y_pred)
ax.set_xlabel('y_test')
ax.set_ylabel('y_pred')
plt.show()

f:id:oosakik:20191216010553p:plain

参照文献

scikit-learn 0.22 sklearn.svm.SVR
scikit-learn 0.22 1.4.Support Vector Machines

2019-12-15

汎関数微分と鎖則

理論

概要

汎関数 微分の定義

ある関数 $\phi (x)$ を与えると、実数を与えるような関数 $F[\phi (x) ]$ を考える。代表的なものに以下のような関数が考えられる。

$\begin{align} F [ \phi (x) ] =\int f(\phi (x)) \rm{d}x \end{align}\tag{1}$

上記の式で $f$ は任意に成り立つ。ここで、 $\phi (x) \rightarrow \phi (x) + \delta\phi (x)$ と変化したとすると関数 $F$ がどのように変化するのかを考える。これが汎関数微分である。まずは、以下のように $\delta F$ を考える。

(3)を導いてみる。まず、 $P \equiv P(f _ 1, f_2, \cdots )$ を考える。そうすると $P$ の偏微分は以下のようになる。

fが連続な値になると以下のようになる。

$\begin{align} \delta P = \int \frac{\delta P}{\delta f _ k}\delta f _ k \rm{d}k \end{align} \tag{4}$

鎖則の導出

$F$ が(1)で表される場合を考える。 $f(\phi (x)) \equiv \phi (x) \delta (x-y)$ とすると $F[\phi (x)] = \int\phi (x)\delta (x-y)\rm{d}x = \phi (y)$ が成り立つ。これを(3)に代入すると

また、デルタ関数の性質により以下の式が成り立つ。 $\begin{align} \delta\phi (y) = \int\delta (x-y)\delta\phi (x)\rm{d}x\tag{6} \end{align}$ (5), (6)より以下の式が導かれる。

$\begin{align} \delta (x-y) = \frac{\delta\phi (y)}{\delta\phi (x)}\tag{7} \end{align}$

2019-12-12

VSCodeのkeybindings.jsonを編集してより便利に

VSCode

概要

VSCodeは便利であるが、さらに便利にするためにkeybindings.jsonを編集する。自分用のメモとして残しておく。

環境

vscode 1.40.2

keybindings.jsonを開く

こちらを参考する。 vscodeでVimを導入し、インサートモードを設定する

keybindings.jsonを編集する

編集する時に注意が必要。keybindings.jsonを記入するときには[]は一回しか適用できないらしい。初めて記すときは問題ないが、追記するときには注意する必要がある。

これはだめ

[
    {
        "key": "tab",
        "command": "-jumpToNextSnippetPlaceholder",
        "when": "editorTextFocus && hasNextTabstop && inSnippetMode"
    }
]
[
    {
      "key": "ctrl+j",
      "command": "workbench.action.terminal.focus",
      "when": "editorTextFocus"
    },
]

こうする

[
    {
        "key": "tab",
        "command": "-jumpToNextSnippetPlaceholder",
        "when": "editorTextFocus && hasNextTabstop && inSnippetMode"
    }
    {
      "key": "ctrl+j",
      "command": "workbench.action.terminal.focus",
      "when": "editorTextFocus"
    },
]

エディター、ターミナル、サイドバー間の移動

エディター、ターミナル、サイドバーの移動をコマンドで移動できるようにkeybindings.jsonで設定する。移動はvimっぽく移動できるようにする。かなり快適になった。

以下のように記入する。

// move to editor, terminal, sidebar
    {
      "key": "ctrl+h",
      "command": "workbench.action.focusSideBar",
      "when": "editorTextFocus"
    },
    {
      "key": "ctrl+j",
      "command": "workbench.action.terminal.focus",
      "when": "editorTextFocus"
    },
    {
      "key": "ctrl+l",
      "command": "workbench.action.focusFirstEditorGroup",
      "when": "filesExplorerFocus"
    },
    {
        "key": "ctrl+k",
        "command": "workbench.action.focusFirstEditorGroup",
        "when": "terminalFocus"
    }

ファイルの作成

デフォルトでのファイルの作成コマンドはcmd+nでこれはこれでよい。しかし、保存する時に名前を指定するなどの不具合がストレスとなるため、解消する。

    {"key": "cmd+n", "command": "explorer.newFile" }

ちなみに、編集中のファイルを閉じるのはcmd+w。サイドバーにあるファイルを編集するためにはl。ディレクトリを作成するときは、ターミナルを使えばよい。エディタを分割後に、アクティブなエディタを移動させたいときはcom+k→とする。

参照文献

【VSCode】エディタ、サイドバー、ターミナル間のフォーカスのショートカットを設定する
 VSCodeの「新規ファイル作成(cmd+n)」をカスタマイズする

2019-12-12

vscodeでVimを導入し、インサートモードを設定する

VSCode

概要

vscodeにvimを導入したものの、下に移動するコマンドjが使えなくて試行錯誤したのでメモする。

環境

vscode 1.40.2
Vim 1.12.2

keybindings.jsonファイルを開く

code => Preferences => Keyboard Shortcutsへ移動

f:id:oosakik:20191212012138p:plain

ここのextension.vim_escapeコマンドをEscapeにしたいのだが、編集をしてescコマンドを打つと、なぜか終了してしまい、うまく設定できない。そこで以下の赤く囲われているところをクリックしてkeybindings.jsonファイルを開く。

f:id:oosakik:20191212012257p:plain

keybindings.jsonファイルの編集

keybindings.jsonファイルを以下のように変更。

// Place your key bindings in this file to override the defaultsauto[]
[
    {
        "key": "escape",
        "command": "extension.vim_escape",
        "when": "editorTextFocus && vim.active && !inDebugRepl"
    },
    {
        "key": "escape",
        "command": "-extension.vim_escape",
        "when": "editorTextFocus && vim.active && !inDebugRepl"
    },
    {
        "key": "tab cmd+",
        "command": "jumpToNextSnippetPlaceholder",
        "when": "editorTextFocus && hasNextTabstop && inSnippetMode"
    },
    {
        "key": "tab",
        "command": "-jumpToNextSnippetPlaceholder",
        "when": "editorTextFocus && hasNextTabstop && inSnippetMode"
    }
]

参照文献

Visual Studio Codeを使ってみる。-どん底から這い上がるまでの記録