単一始点最短距離問題をPythonで解答
負の閉路が存在しない場合、更新はいずれ止まるため、この更新方法で対応できるらしい。
## ベルマンフォード法 class BellmanFord(object): def __init__(self, v): self.e = 0 self.d = [float("inf") for i in range(v)] self.edge = [] def append(self, _from, _to, _cost): self.edge.append({ 'from': _from, 'to': _to, 'cost': _cost }) self.e = len(self.edge) def shortest_path(self, s): self.d[s] = 0 while 1: update = True for i in range(self.e): e = self.edge[i] if self.d[e['from']] != float("inf") and self.d[e['to']] > self.d[e['from']] + e['cost']: self.d[e['to']] = self.d[e['from']] + e['cost'] update = True if update: break ## ダイクストラ法 class Dijkstra(object): def __init__(self, v): self.v = v self.e = 0 self.d = [float("inf") for i in range(v)] self.used = [0 for i in range(v)] self.cost = [[float("inf") for i in range(v)] for i in range(v)] def append(self, _from, _to, _cost): self.cost[_from][_to] = _cost self.e += 1 def shortest_path(self, s): self.d[s] = 0 while 1: v = -1 for u in range(self.v): if not self.used[u] and (v == -1 or (self.d[u] < self.d[v])): v = u if (v == -1): break self.used[v] = 1 for u in range(self.v): self.d[u] = min(self.d[u], self.d[v] + self.cost[v][u])
b = BellmanFord(7) b.append(0, 1, 2) b.append(1, 0, 2) b.append(0, 2, 5) b.append(2, 0, 5) b.append(1, 2, 4) b.append(2, 1, 4) b.append(1, 3, 6) b.append(3, 1, 6) b.append(2, 3, 2) b.append(3, 2, 2) b.append(1, 4, 10) b.append(4, 1, 10) b.append(3, 5, 1) b.append(5, 3, 1) b.append(4, 5, 3) b.append(5, 4, 3) b.append(4, 6, 5) b.append(6, 4, 5) b.append(5, 6, 9) b.append(6, 5, 9) b.shortest_path(0) In [40]: b.d Out[40]: [0, 2, 5, 7, 11, 8, 16] In [41]: b.d[6] Out[41]: 16
AWSのタイムゾーン設定
Amazon Linuxのタイムゾーンの設定は、 timedatectlがなかったので以下で対応した。
勝手にMySQLのタイムゾーンも変更
$ sudo yum -y install ntp $ sudo ntpdate ntp.nict.jp $ su # service --status-all | grep ntp # vim /etc/ntp.conf ==(vim /etc/ntp.conf)========= # Use public servers from the pool.ntp.org project. # Please consider joining the pool (http://www.pool.ntp.org/join.html). #server 0.amazon.pool.ntp.org iburst #server 1.amazon.pool.ntp.org iburst #server 2.amazon.pool.ntp.org iburst #server 3.amazon.pool.ntp.org iburst server -4 ntp.nict.jp server -4 ntp1.jst.mfeed.ad.jp server -4 ntp2.jst.mfeed.ad.jp server -4 ntp3.jst.mfeed.ad.jp =========== # strings /etc/localtime # cp /etc/localtime /etc/localtime.org # ls /usr/share/zoneinfo/Japan # ln -sf /usr/share/zoneinfo/Japan /etc/localtime
あとは、再起動。
Jupyterを外部サーバに設置してアクセスする方法
以下の設定で可能。
In [1]: from notebook.auth import passwd In [2]: passwd() Enter password: <パスワードを入力> Verify password: <パスワードを再入力> Out[2]: 'sha1:<ハッシュ化されたパスワード>'
$ vim ~/.jupyter/jupyter_notebook_config.py
- ~/.jupyter/jupyter_notebook_config.py
# matplotlibで描画したものがnotebook上で表示できるようにする c.InteractiveShellApp.matplotlib = "inline" # 全てのIPから接続を許可 c.NotebookApp.ip = '*' # IPython notebookのログインパスワード c.NotebookApp.password = 'sha1:<ハッシュ化されたパスワード>' # 起動時にブラウザを起動させるかの設定(デフォルトは起動させる) c.NotebookApp.open_browser = False # ポート指定(デフォルトは8888) c.NotebookApp.port = <接続ポート>
UnionFind木のpythonでの実装
UnionFind木で同じグループのものを判定する
class UnionFind(object): def __init__(self, size): self.parent = [i for i in range(size)] self.rank = [0 for _ in range(size)] def find(self, x): if self.parent[x] == x: return x else: return self.find(self.parent[x]) def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.rank[x] < self.rank[y]: self.parent[x] = y else: self.parent[y] = x if self.rank[x] == self.rank[y]: self.rank[x] += 1 def same(self, x, y): return self.find(x) == self.find(y)
In [113]: u = UnionFind(10) In [114]: u.unite(1,2) In [115]: u.unite(3,2) In [116]: u.unite(5,6) In [117]: u.parent Out[117]: [0, 1, 1, 1, 4, 5, 5, 7, 8, 9] In [119]: u.rank Out[119]: [0, 1, 0, 0, 0, 1, 0, 0, 0, 0]
PriorityQueueの確認
PriorityQueueをPythonで表してみる。
こんなんで大きい順に出せるのかと思った。
class PriorityQueue(object): def __init__(self): self.l = [] def push(self, x): self.l.append(x) sz = len(self.l) i = sz - 1 while i > 0: p = (i - 1) // 2 if self.l[p] >= x: break self.l[i] = self.l[p] i = p self.l[i] = x def pop(self): sz = len(self.l) if sz == 0: return None res = self.l[0] x = self.l[-1] i = 0 while (i * 2 + 1) < sz: a = i * 2 + 1 b = i * 2 + 2 if b < sz and self.l[b] > self.l[a]: a = b if self.l[a] <= x: break self.l[i] = self.l[a] i = a self.l[i] = x self.l = self.l[:-1] return res
In [91]: a = PriorityQueue() In [92]: a.push(2) In [92]: a.push(2) In [93]: a.push(2) In [94]: a.push(4) In [95]: a.push(5) In [96]: a.push(20) In [97]: a.push(215) In [98]: a.push(23) In [99]: a.push(12) In [100]: a.l Out[100]: [215, 12, 23, 5, 4, 2, 20, 2] In [101]: a.pop() Out[101]: 215 In [102]: a.pop() Out[102]: 23 In [103]: a.pop() Out[103]: 20 In [104]: a.pop() Out[104]: 12 In [105]: a.pop() Out[105]: 5 In [106]: a.pop() Out[106]: 4 In [107]: a.pop() Out[107]: 2 In [108]: a.pop() Out[108]: 2 In [109]: a.pop()
最長共通部分問題のPythonで記述
最長共通部分問題について、pythonで解いてみた。 もしかしたら、間違っているかも
class LCS(object): def __init__(self, s, t): self.s = s self.t = t self.n = len(s) self.m = len(t) self.dp = [[-1 for mm in range(self.m + 1)] for nn in range(self.n + 1)] def solve(self, i, j): if self.dp[i][j] >= 0: return self.dp[i][j] if i == 0 or j == 0: return 0 if self.s[i - 1] == self.t[j - 1]: self.dp[i][j] = max(self.solve(i - 1, j - 1) + 1, self.solve(i, j - 1), self.solve(i - 1, j)) else: self.dp[i][j] = max(self.solve(i, j-1), self.solve(i-1, j)) res = self.dp[i][j] return res def get_lcs(self): return self.solve(self.n, self.m)
In [53]: lcs = LCS('abcd', 'becd') In [54]: lcs.get_lcs() Out[54]: 3
レビューの星の計算方法
最低投票数の閾値の割合 × 全ての投票の☆平均値 ＋ ターゲットの投票数の割合 × ターゲットの☆平均値
(WR) = (v / (v+m)) × R + (m / (v+m)) × C
= (v × R + m × C) / (v+m)
* R = 対象の☆の数の平均
* v = 投票数
* m = 最低投票数閾値
* C = 全ての☆の数の平均
