Python競プロライブラリの整理をする
(19/11/22 追記)
一応最新のはgithubに上げてる
そのうち整理されるかもしれないので個別のページへのリンクを貼ったりするのはやめといたほうがいいかも
この記事は何
PyCharmに常に貼ってたライブラリが長くなりすぎて整理する必要が出てきた
使わなくなったライブラリを消すのが何となくもったいないので公開してから消す
ついでに競プロライブラリを共有する
前置き
この記事のコードは公開を前提に書いたわけじゃないので、Python競プロライブラリを探しているならまず↓のサイトを見るといいと思う
アルゴリズム [いかたこのたこつぼ] DTMでもよくお世話になりました
ライブラリ整理
拡張ユークリッド互除法・中国剰余定理
拡張ユークリッド互除法
# 拡張ユークリッド互除法 # gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す def egcd(a, b): if a == 0: return b, 0, 1 else: g, y, x = egcd(b % a, a) return g, x - (b // a) * y, y
AtCoderを初めて間もない頃に誰だったかの解答からコピペしたもの
m1 = 10 m2 = 6 gcd, x, y = egcd(m1, m2) # 10で割ると1余り6で割ると3余る数を求める b1 = 1 b2 = 3 s = (b2 - b1) // gcd # これは必ず割り切れる ans = b1 + m1 * s * x print(ans)
使い方のメモがあったけどこれはいらない、消す
中国剰余定理
def chineseRem(b1, m1, b2, m2): # 中国剰余定理 # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m) # となる(r. m)を返す # 解無しのとき(0, -1) d, p, q = egcd(m1, m2) if (b2 - b1) % d != 0: return 0, -1 m = m1 * (m2 // d) # m = lcm(m1, m2) tmp = (b2-b1) // d * p % (m2 // d) r = (b1 + m1 * tmp) % m return r, m
なんか効率悪いことしてる気がするけどまあこのままでいいか
乗法のmod逆元・組み合わせ
乗法のmod逆元(mod-2乗)
def modinv(a, mod=10**9+7): return pow(a, mod-2, mod)
こっちを普段使ってる
乗法のmod逆元(拡張ユークリッド互除法)
# mを法とするaの乗法的逆元 def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m
egcdと一緒にパクったものを残してるけどpowでいいこと知ってから使われていない
組み合わせ
# nCr mod m # modinvが必要 # rがn/2に近いと非常に重くなる def combination(n, r, mod=10**9+7): r = min(r, n-r) res = 1 for i in range(r): res = res * (n - i) * modinv(i+1, mod) % mod return res
愚直に求めるものだけどたまに使う
組み合わせ(2)
# nCrをすべてのr(0<=r<=n)について求める # nC0, nC1, nC2, ... , nCn を求める # modinvが必要 def combination_list(n, mod=10**9+7): lst = [1] for i in range(1, n+1): lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod) return lst
これは使ってない、消す
階乗のmod逆元のリスト
# 階乗のmod逆元のリストを返す O(n) def facinv_list(n, mod=10**9+7): L = [1] for i in range(1, n+1): L.append(L[i-1] * modinv(i, mod) % mod) return L
これO(n)って書いてるけどO(nlog(mod))では?効率悪いし使ってないので消す
重複組み合わせ
# nHr mod m def H(n, r, mod=10**9+7): return combination(n+r-1, r, mod)
combination()
の部分は必要に応じて下記のCombinationオブジェクトに書き換えて使う
組み合わせ(何回も使う方)
class Combination: """ O(n)の前計算を1回行うことで,O(1)でnCr mod mを求められる n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms) 使用例: comb = Combination(1000000) print(comb(5, 3)) # 10 """ def __init__(self, n_max, mod=10**9+7): self.mod = mod self.modinv = self.make_modinv_list(n_max) self.fac, self.facinv = self.make_factorial_list(n_max) def __call__(self, n, r): return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod def make_factorial_list(self, n): # 階乗のリストと階乗のmod逆元のリストを返す O(n) # self.make_modinv_list()が先に実行されている必要がある fac = [1] facinv = [1] for i in range(1, n+1): fac.append(fac[i-1] * i % self.mod) facinv.append(facinv[i-1] * self.modinv[i] % self.mod) return fac, facinv def make_modinv_list(self, n): # 0からnまでのmod逆元のリストを返す O(n) modinv = [0] * (n+1) modinv[1] = 1 for i in range(2, n+1): modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod return modinv
(久々に中身見たけどこれどうやって動いてるんだっけ)
下2つのメソッドはクラス内から呼び出されることを前提にしてるので_
をつけたほうがいいのかもしれない、知らんけど
素数判定、素因数分解
エラトステネスの篩
# nまでの自然数が素数かどうかを表すリストを返す def makePrimeChecker(n): isPrime = [True] * (n + 1) isPrime[0] = False isPrime[1] = False for i in range(2, int(n ** 0.5) + 1): if isPrime[i]: for j in range(i * i, n + 1, i): isPrime[j] = False return isPrime
若干効率悪く書いてたのに気付いたので修正した
素因数分解
# 素因数分解 def prime_decomposition(n): i = 2 table = [] while i * i <= n: while n % i == 0: n //= i table.append(i) i += 1 if n > 1: table.append(n) return table
素因数分解はなんか高速にやる方法もあったと思うけどそれは持ってない
確率的素数判定もあった方がいい気がしたのでyaketakeさんのものを参考に導入することにした
順列
def full(L): # 並び替えをすべて挙げる,全探索用 # これitertools.permutationsでええやん!!!!!!! if len(L) == 1: return [L] else: L2 = [] for i in range(len(L)): L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])]) return L2
itertools.permutations
を知るまで使っていたもの
思い出的に残してた(消す)
転倒数
# 転倒数 def mergecount(A): cnt = 0 n = len(A) if n>1: A1 = A[:n>>1] A2 = A[n>>1:] cnt += mergecount(A1) cnt += mergecount(A2) i1=0 i2=0 for i in range(n): if i2 == len(A2): A[i] = A1[i1] i1 += 1 elif i1 == len(A1): A[i] = A2[i2] i2 += 1 elif A1[i1] <= A2[i2]: A[i] = A1[i1] i1 += 1 else: A[i] = A2[i2] i2 += 1 cnt += n//2 - i1 return cnt
Spaghetti Source - バブルソートの交換回数 をPythonで書き換えたもの
動作原理は理解してない
転倒数はBinary Indexed Treeで求められるし使ってないけど…一応残しておく
Binary Indexed Tree
一点加算・区間和取得
class Bit: def __init__(self, n): self.size = n self.tree = [0]*(n+1) def __iter__(self): psum = 0 for i in range(self.size): csum = self.sum(i+1) yield csum - psum psum = csum raise StopIteration() def __str__(self): # O(nlogn) return str(list(self)) def sum(self, i): # [0, i) の要素の総和を返す if not (0 <= i <= self.size): raise ValueError("error!") s = 0 while i>0: s += self.tree[i] i -= i & -i return s def add(self, i, x): if not (0 <= i < self.size): raise ValueError("error!") i += 1 while i <= self.size: self.tree[i] += x i += i & -i def __getitem__(self, key): if not (0 <= key < self.size): raise IndexError("error!") return self.sum(key+1) - self.sum(key) def __setitem__(self, key, value): # 足し算と引き算にはaddを使うべき if not (0 <= key < self.size): raise IndexError("error!") self.add(key, value - self[key])
初期値をO(n)で入れられるようにするべきかもしれない
和以外の演算もできるようにすべきかもしれない
# BITで転倒数を求められる A = [3, 10, 1, 8, 5, 5, 1] bit = Bit(max(A)+1) ans = 0 for i, a in enumerate(A): ans += i - bit.sum(a+1) bit.add(a, 1) print(ans)
Binary Indexed Treeの使い方のメモ
区間加算・一点取得
class BitImos: """ ・範囲すべての要素に加算 ・ひとつの値を取得 の2種類のクエリをO(logn)で処理 """ def __init__(self, n): self.bit = Bit(n+1) def add(self, s, t, x): # [s, t)にxを加算 self.bit.add(s, x) self.bit.add(t, -x) def get(self, i): return self[i] def __getitem__(self, key): # 位置iの値を取得 return self.bit.sum(key+1)
いもす法みたいな使い方をしやすいようなBIT
区間加算・区間取得
# 未検証 class Bit2: def __init__(self, n): self.bit0 = Bit(n) self.bit1 = Bit(n) def add(self, l, r, x): # [l, r) に x を足す self.bit0.add(l, -x * (l-1)) self.bit1.add(l, x) self.bit0.add(r, x * (r-1)) self.bit1.add(r, -x) def sum(self, l, r): res = 0 res += self.bit0.sum(r) + self.bit1.sum(r) * (r-1) res -= self.bit0.sum(l) + self.bit1.sum(l) * (l-1) return res
原理わかってない
セグメント木
RMQ
# セグ木 class SegTree: # 根は 1 # 親は node>>1 # 子は node<<1, node<<1 | 1 # 兄弟は node^1 # 値が入ってるのは offset: def __init__(self, n): self.n = n # 要素数 self.INF = float("inf") self.seg = [self.INF] * (n * 4) self.depth = len(bin(n))-2 self.offset = 1<<self.depth def initialize(self, lst): # あとで書く pass def update(self, i, x): node = self.offset + i self.seg[node] = x while node > 1: # 親を更新 self.seg[node >> 1] = min(self.seg[node], self.seg[node ^ 1]) node >>= 1 def getmin(self, a, b, k=1, l=0, r=None): if r is None: r = self.offset # a, b は再帰で変化しない値 # 要求区間[a,b)と今見ている区間[l,r)が交わらない if r <= a or b <= l: return self.INF # 今見ている区間は要求区間に完全に含まれている if a <= l and r <= b: return self.seg[k] # どちらでもなければ子ノードを見る vl = self.getmin(a, b, k << 1, l, (l + r) >> 1) vr = self.getmin(a, b, (k << 1) | 1, (l + r) >> 1, r) return min(vl, vr)
確か プログラミングコンテストでのデータ構造 をPythonで書き換えたもののはず
コピペしてきたもののほうがクオリティが高いので供養
一点更新・区間取得
# https://atcoder.jp/contests/abc014/submissions/3935971 class SegmentTree(object): __slots__ = ["elem_size", "tree", "default", "op"] def __init__(self, a: list, default: int, op): from math import ceil, log real_size = len(a) self.elem_size = elem_size = 1 << ceil(log(real_size, 2)) self.tree = tree = [default] * (elem_size * 2) tree[elem_size:elem_size + real_size] = a self.default = default self.op = op for i in range(elem_size - 1, 0, -1): tree[i] = op(tree[i << 1], tree[(i << 1) + 1]) def get_value(self, x: int, y: int) -> int: # 半開区間 l, r = x + self.elem_size, y + self.elem_size tree, result, op = self.tree, self.default, self.op while l < r: if l & 1: result = op(tree[l], result) l += 1 if r & 1: r -= 1 result = op(tree[r], result) l, r = l >> 1, r >> 1 return result def set_value(self, i: int, value: int) -> None: k = self.elem_size + i self.tree[k] = value self.update(k) def update(self, i: int) -> None: op, tree = self.op, self.tree while i > 1: i >>= 1 tree[i] = op(tree[i << 1], tree[(i << 1) + 1]) """ C = [int(input()) for _ in range(N)] idx = [0] * N for i, c in enumerate(C): idx[c-1] = i seg = SegmentTree([0]*(N+1), 0, min) for i in range(N): idx_ = idx[i] seg.set_value(idx_, seg.get_value(0, idx_)-1) print(seg.get_value(0, N+1)+N) """
htkbさんのセグメント木
神
平衡二分探索木
Treap
# Treap import random class Treap: def __init__(self): self.node = None # root def __str__(self): L = [] def recursiveSearch(node): if node.left is not None: recursiveSearch(node.left) L.append((node.val, node.priority)) if node.right is not None: recursiveSearch(node.right) recursiveSearch(self.node) return str(L) def add(self, x): i = self.bisect(x) self.node = self.insert(self.node, i, x) def remove(self, x): i = self.bisect(x) self.node = self.erase(self.node, i) def bisect(self, x): # bisect_left def recursiveSearch(node): if node is None: return 0 res = 0 if x <= node.val: if node.left is not None: return recursiveSearch(node.left) else: return 0 else: res += self.count(node.left) + 1 if node.right is not None: return res + recursiveSearch(node.right) else: return res return recursiveSearch(self.node) def __getitem__(self, k, t=None): if t is None: t = self.node if k < self.count(t.left): if t.left is None: return t.val return self.__getitem__(k, t.left) elif k == self.count(t.left): return t.val else: if t.right is None: return t.val return self.__getitem__(k - self.count(t.left) - 1, t.right) class Node: def __init__(self, x): self.val = x self.priority = random.randint(0, 1<<30) self.left = None self.right = None self.cnt = 1 def __str__(self): return str(self.val) def count(self, t: Node): return 0 if t is None else t.cnt def update(self, t: Node): t.cnt = self.count(t.left) + self.count(t.right) + 1 return t def merge(self, l: Node, r: Node): if l is None: return r if r is None: return l if l.priority > r.priority: l.right = self.merge(l.right, r) return self.update(l) else: r.left = self.merge(l, r.left) return self.update(r) def split(self, t: Node, k: int) -> (Node, Node): # [0,k),[k,n) if t is None: return None, None if k <= self.count(t.left): s = self.split(t.left, k) t.left = s[1] return s[0], self.update(t) else: s = self.split(t.right, k - self.count(t.left) - 1) t.right = s[0] return self.update(t), s[1] def insert(self, t: Node, k: int, x): l, r = self.split(t, k) return self.merge(self.merge(l, self.Node(x)), r) def erase(self, t: Node, k): l, r = self.split(t, k) _, r = self.split(r, 1) return self.merge(l, r) """ treap = Treap() for i in range(100000): treap.add(i) s.add(i) print(treap[50]) """
重すぎて使い物にならない、供養
AVL木
これ
PythonでAVL木を競プロ用に実装した(誰か高速化してくれ) - 菜
↑はPythonにC++のsetに相当するものが無いから実装したものだけど、クエリ先読みできるならBITでなんとかなるらしい(わかってない)
オフラインクエリのset実装 - Tallfallの日記
ダイクストラ法
from collections import defaultdict import heapq class Dijkstra: # 計算量 O((E+V)logV) # adjはdefaultdictのリスト def dijkstra(self, adj, start, goal=None): num = len(adj) # グラフのノード数 self.dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する self.prev = [float('inf') for i in range(num)] # 最短経路における,その頂点の前の頂点のIDを格納する self.dist[start] = 0 q = [(0, start)] # プライオリティキュー.各要素は,(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル while len(q) != 0: prov_cost, src = heapq.heappop(q) # pop # プライオリティキューに格納されている最短距離が,現在計算できている最短距離より大きければ,distの更新をする必要はない if self.dist[src] < prov_cost: continue # 探索で辺を見つける場合ここに書く # 他の頂点の探索 for dest, cost in adj[src].items(): if self.dist[dest] > self.dist[src] + cost: self.dist[dest] = self.dist[src] + cost # distの更新 heapq.heappush(q, (self.dist[dest], dest)) # キューに新たな仮の距離の情報をpush self.prev[dest] = src # 前の頂点を記録 if goal is not None: return self.get_path(goal, self.prev) else: return self.dist def get_path(self, goal, prev): path = [goal] # 最短経路 dest = goal # 終点から最短経路を逆順に辿る while prev[dest] != float('inf'): path.append(prev[dest]) dest = prev[dest] # 経路をreverseして出力 return list(reversed(path))
Pythonでダイクストラアルゴリズムを実装した - フツーって言うなぁ! を改造したもの
クラスになってるけどそのまま使うことはほとんどしていなくて、
実装の参考にするために置いている
経路が必要がないならself.prev
は必要ない
Union Find木
# unionfind class Uf: def __init__(self, N): self.p = list(range(N)) self.rank = [0] * N self.size = [1] * N def root(self, x): if self.p[x] != x: self.p[x] = self.root(self.p[x]) return self.p[x] def same(self, x, y): return self.root(x) == self.root(y) def unite(self, x, y): u = self.root(x) v = self.root(y) if u == v: return if self.rank[u] < self.rank[v]: self.p[u] = v self.size[v] += self.size[u] self.size[u] = 0 else: self.p[v] = u self.size[u] += self.size[v] self.size[v] = 0 if self.rank[u] == self.rank[v]: self.rank[u] += 1 def count(self, x): return self.size[self.root(x)]
これどこかからコピペしたんだっけ…?
マス目の幅優先探索
# マス目の幅優先探索 for y, s in enumerate(S): for x, c in enumerate(s): if c=="S": start = (x, y) elif c=="G": goal = (x, y) ans = 0 Open = [start] Close = {start} a = 0 flg = True while flg: a += 1 OpenNext = [] for x, y in Open: for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]: if (x+dx, y+dy) not in Close and S[y+dy][x+dx] != "#": if (x+dx, y+dy) == goal: flg = False OpenNext.append((x+dx, y+dy)) Close.add((x+dx, y+dy)) Open = OpenNext if len(Open) == 0: a = float("inf") break ans += a
だいぶ前にメモとして置いておいた気がするけど使ってないし微妙に効率悪い、消す
高速ゼータ変換・高速メビウス変換
# 高速ゼータ変換 # 自身を含む集合を全て挙げる方 N = 3 f = [{i} for i in range(1<<N)] for i in range(N): for j in range(1<<N): if not (j & 1<<i): f[j] |= f[j | (1<<i)] # 総和は += # -=にすると逆変換になる print(f) # 部分集合をすべて挙げる方 f = [{i} for i in range(1<<N)] for i in range(N): for j in range(1<<N): if j & 1<<i: f[j] |= f[j ^ (1<<i)] print(f)
メモだけどわかりにくいと思うしどうやればわかりやすく書けるのかわからない
[{0, 1, 2, 3, 4, 5, 6, 7}, {1, 3, 5, 7}, {2, 3, 6, 7}, {3, 7}, {4, 5, 6, 7}, {5, 7}, {6, 7}, {7}] [{0}, {0, 1}, {0, 2}, {0, 1, 2, 3}, {0, 4}, {0, 1, 4, 5}, {0, 2, 4, 6}, {0, 1, 2, 3, 4, 5, 6, 7}]
実行結果
最長回文
# Manacherのアルゴリズム def man(S): i = 0 j = 0 n = len(S) R = [0]*n while i < n: while i-j >= 0 and i+j < n and S[i-j] == S[i+j]: j+=1 R[i] = j k = 1 while i-k >= 0 and i+k < n and k+R[i-k] < j: R[i+k] = R[i-k] k += 1 i += k j -= k return R
フロー
Dinic法
# 最大流問題 from collections import deque INF = float("inf") TO = 0; CAP = 1; REV = 2 class Dinic: def __init__(self, N): self.N = N self.V = [[] for _ in range(N)] # to, cap, rev # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]] self.level = [0] * N def add_edge(self, u, v, cap): self.V[u].append([v, cap, len(self.V[v])]) self.V[v].append([u, 0, len(self.V[u])-1]) def add_edge_undirected(self, u, v, cap): # 未検証 self.V[u].append([v, cap, len(self.V[v])]) self.V[v].append([u, cap, len(self.V[u])-1]) def bfs(self, s: int) -> bool: self.level = [-1] * self.N self.level[s] = 0 q = deque() q.append(s) while len(q) != 0: v = q.popleft() for e in self.V[v]: if e[CAP] > 0 and self.level[e[TO]] == -1: # capが1以上で未探索の辺 self.level[e[TO]] = self.level[v] + 1 q.append(e[TO]) return True if self.level[self.g] != -1 else False # 到達可能 def dfs(self, v: int, f) -> int: if v == self.g: return f for i in range(self.ite[v], len(self.V[v])): self.ite[v] = i e = self.V[v][i] if e[CAP] > 0 and self.level[v] < self.level[e[TO]]: d = self.dfs(e[TO], min(f, e[CAP])) if d > 0: # 増加路 e[CAP] -= d # cap を減らす self.V[e[TO]][e[REV]][CAP] += d # 反対方向の cap を増やす return d return 0 def solve(self, s, g): self.g = g flow = 0 while self.bfs(s): # 到達可能な間 self.ite = [0] * self.N f = self.dfs(s, INF) while f > 0: flow += f f = self.dfs(s, INF) return flow
これ何を参考に実装したのか全く思い出せないけど気付いたらあった
最長増加部分列(LIS)
いかたこさんのものを使っています
最近共通祖先(LCA)
class Lca: # 最近共通祖先 def __init__(self, E, root): import sys sys.setrecursionlimit(500000) self.root = root self.E = E # V<V> self.n = len(E) # 頂点数 self.logn = 1 # n < 1<<logn ぴったりはだめ while self.n >= (1<<self.logn): self.logn += 1 # parent[n][v] = ノード v から 1<<n 個親をたどったノード self.parent = [[-1]*self.n for _ in range(self.logn)] self.depth = [0] * self.n self.dfs(root, -1, 0) for k in range(self.logn-1): for v in range(self.n): p_ = self.parent[k][v] if p_ >= 0: self.parent[k+1][v] = self.parent[k][p_] def dfs(self, v, p, dep): # ノード番号、親のノード番号、深さ self.parent[0][v] = p self.depth[v] = dep for e in self.E[v]: if e != p: self.dfs(e, v, dep+1) def get(self, u, v): if self.depth[u] > self.depth[v]: u, v = v, u # self.depth[u] <= self.depth[v] dep_diff = self.depth[v]-self.depth[u] for k in range(self.logn): if dep_diff >> k & 1: v = self.parent[k][v] if u==v: return u for k in range(self.logn-1, -1, -1): if self.parent[k][u] != self.parent[k][v]: u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u]
これパクったんじゃないっけ…?AOJ見たら自分がverifyしてる痕跡があったけど…
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3526639#1
幾何
いくつかあるけどAOJからコピペしたものが多いので割愛
その他細かいメモ
import sys def input(): return sys.stdin.readline()[:-1] input = sys.stdin.readline from functools import lru_cache @lru_cache(maxsize=None) # メモ化再帰したい関数の前につける import sys sys.setrecursionlimit(500000) from operator import itemgetter from collections import defaultdict from itertools import product # 直積 ord("a") - 97 # chr N = int(input()) N, K = map(int, input().split()) L = [int(input()) for _ in range(N)] A = list(map(int, input().split())) S = [list(map(int, input().split())) for _ in range(H)]
itemgetter
とかがどこにあったのか昔は覚えてなかったけど今は大丈夫なのでそのへんは消す
input = sys.stdin.readline は読み込むものが文字列じゃないときに使ってる
まとめ
コピペ多いね…
AtCoder黄色になった
注: この記事のPythonはPyPyを含む
黄色になった
やっと黄色になれました!長かった… pic.twitter.com/TQfGqMNre9
— Lgeu(るぎう) (@lgeuwce) June 22, 2019
年が変わる前に黄色になりたい → 無理だわ。AtCoder始めて1年経つ前に黄色になりたい → 無理だったわ。何が何でも黄色になりたい → なったわ。
黄色になるまでにやったこと
精進
C++はunratedだった平成ABCでしか使ってない
初見で解けなかった問題はACしないようにしてる(これは多分良くないが)ので少なめに出てると思う
知識
やった
青のときとの差分で(青のときの記事は今見ると微妙なので貼らないけど)
やったけど使えてない
やってない
- 最小費用流
- 遅延評価セグメント木
- プリム法
- Rolling Hash
- Trie木
- Suffix Array
- 行列(ABCで出たけど)
- 高速フーリエ変換(FFT)
- kD木
- 幾何
- 永続データ構造
ポエム(Python競プロについて)
賛否両論ありそう
Pythonの実行速度
AtCoderにはPyPyがあるので、その辺のスクリプト言語とは話が違う
このおかげで、保証されていないとはいえ、実際のところratedなコンテストではPythonで通せない問題は0に近い(黄coderが解かないような高難易度の問題は知らないが)
まあ定数倍で厳しい気持ちになることもあるけど、他の人の提出を見ると「頭悪い実装してた…」ってなるので…
「C#が遅いせいで落ちたー><」ってなることもたまにあるけど、単純に書き方が悪いことが多いので、実際はそんなに落ちないイメージ。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年6月10日
Pythonもだいたいこれ
Pythonの利点
配列Aをもとのindexを保持したままソートしたい
C++の場合は
V<pair<ll, ll>> B; rep(i, A.size()) B.emplace_back(A[i], i); sort(B.begin(), B.end());
普通だな!
pythonなら
B = sorted(zip(A, range(len(A))))
楽~~~~~~~神~~~~~~~~~(実行速度を気にするならB = sorted(enumerate(A), key=itemgetter(1))
としたほうがいいかもしれない)
コードが短く書けると間違いにくく・速く実装できるし、デバッグもしやすくなって、
これはかなり大きな利点だと思う
あとitertoolsのおかげで再帰を書く機会が大きく減るのが嬉しい
再帰は天才過ぎて頭がバグるのでitertoolsがあると天才を無駄遣いしなくて良くなる
next_permutationで解けちゃうよ的問題、C++とかPythonが有利過ぎるとは思うんだけれども、それでも「順列を全て生成する」というのはやっぱり基本操作として出来てほしいなぁ、と思うので、やっぱりちょこちょこと出していきたい問題ではある
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) May 12, 2014
itertools知る前は自力で書いてたので許して
結局Python競プロってどうなの
2019年6月現在Pythonで橙以上が存在しないので、Pythonが過小評価されている印象がある
これのせいで黄色が限界とかいう説まであるが、Pythonで黄色の人がC++使い始めたら途端に赤になるなんてことは有り得ない
少なくともAtCoderにおいては、自分はPythonの実行速度で悩むより頭の回転速度で悩むことがずっと多い
Pythonは実装が簡単に済むので余計なことに頭のリソースを割かずに済み、このレート帯ではC++に比べて不利ということはないと思う(似たことは他の人にも言及されている:
titiaのノート: AtCoderで青になるまで)
頭の回転が速い人ならPythonでももっと上の色に十分到達できるはず
黄色しかいないのは確かですが、2色ダウンするほどのハンデではないと思うので、単純に使い手が別言語に変えちゃうのが、高レートの人がいない最大の理由ですね><
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年3月9日
(どちらかというとPython競プロを長い期間続けている人が少ないことが原因な気がする)
Python競プロはまだ発展途上だと思っている
去年の段階ではPythonサブウエポン無しで黄色の人は3人程度(iehnさん、yaketake08さん、ukikagiさん)しかいなかったが、半年で4人増えた(hoxoshさん、ikatakosさん、maspyさん、自分)
http://atcoder-circles.com/circles/pythonista
Python橙coderが出るのも時間の問題だと思う
まとめ
PythonでAVL木を競プロ用に実装した(誰か高速化してくれ)
(19/11/22 追記)
このAVL木どうも遅いっぽい
順序付き集合はPythonだと平方分割が速いことが熨斗袋さんによって判明したのでそれを使うといいと思う
熨斗袋さんによる実装
Submission #7482671 - AtCoder Beginner Contest 140
自分の実装(SkipListベース)
Submission #7488620 - AtCoder Regular Contest 033
Pythonで競プロをやるとAtCoderのレートが1970上がることが知られている(※個人の感想であり、効果・効能には個人差がある)が、Pythonには平衡二分探索木がなくて悲しい。なのでAVL木を実装した。
writerの助言もあり、なんとかPyPyでCPSCO2019 Session1 E - Exclusive OR Queriesを通せたが、かなり制限時間ぎりぎり。自分は諦めたので誰かこれをもっと高速にしてほしい(他力本願寺建立)
コピペだらけのコードだけど実行速度優先だから多少はね?
class AvlTree: # std::set def __init__(self, values=None, sorted_=False, n=0): # values: 初期値のリスト # sorted_: 初期値がソート済みであるか # n: add メソッドを使う回数の最大値 # sorted_==True であれば、初期値の数の線形時間で木を構築する # 値を追加するときは必ず n を設定する if values is None: self.left = [-1] * (n + 1) self.right = [-1] * (n + 1) self.values = [-float("inf")] self.diff = [0] * (n + 1) # left - right self.size_l = [0] * (n + 1) self.idx_new_val = 0 else: if not sorted_: values.sort() len_ = self.idx_new_val = len(values) n += len_ self_left = self.left = [-1] * (n + 1) self_right = self.right = [-1] * (n + 1) self_values = self.values = [-float("inf")] + values self_diff = self.diff = [0] * (n + 1) # left - right self_size_l = self.size_l = [0] * (n + 1) st = [[1, len_ + 1, 0]] while len(st) > 0: # dfs っぽく木を構築 l, r, idx_par = st.pop() # 半開区間 c = (l + r) >> 1 # python -> //2 pypy -> >>1 if self_values[c] < self_values[idx_par]: self_left[idx_par] = c else: self_right[idx_par] = c siz = r - l if siz & -siz == siz != 1: # 2 冪だったら self_diff[c] = 1 self_size_l[c] = siz_l = c - l if siz_l > 0: st.append([l, c, c]) c1 = c + 1 if c1 < r: # 左にノードがなければ右には必ず無いので st.append([c1, r, c]) def rotate_right(self, idx_par, lr): # lr: 親の左なら 0 self_left = self.left self_right = self.right self_diff = self.diff self_size_l = self.size_l lr_container = self_right if lr else self_left idx = lr_container[idx_par] #assert self_diff[idx] == 2 idx_l = self_left[idx] diff_l = self_diff[idx_l] if diff_l == -1: # 複回転 idx_lr = self_right[idx_l] diff_lr = self_diff[idx_lr] if diff_lr == 0: self_diff[idx] = 0 self_diff[idx_l] = 0 elif diff_lr == 1: self_diff[idx] = -1 self_diff[idx_l] = 0 self_diff[idx_lr] = 0 else: # diff_lr == -1 self_diff[idx] = 0 self_diff[idx_l] = 1 self_diff[idx_lr] = 0 # 部分木の大きさの計算 self_size_l[idx_lr] += self_size_l[idx_l] + 1 self_size_l[idx] -= self_size_l[idx_lr] + 1 # 回転 self_right[idx_l] = self_left[idx_lr] self_left[idx] = self_right[idx_lr] self_left[idx_lr] = idx_l self_right[idx_lr] = idx lr_container[idx_par] = idx_lr return 0 else: # 単回転 if diff_l == 0: self_diff[idx] = 1 nb = self_diff[idx_l] = -1 else: # diff_l == 1 self_diff[idx] = 0 nb = self_diff[idx_l] = 0 # 部分木の大きさの計算 self_size_l[idx] -= self_size_l[idx_l] + 1 # 回転 self_left[idx] = self_right[idx_l] self_right[idx_l] = idx lr_container[idx_par] = idx_l return nb # 新しい根の diff を返す def rotate_left(self, idx_par, lr): # lr: 親の左なら 0 self_left = self.left self_right = self.right self_diff = self.diff self_size_l = self.size_l lr_container = self_right if lr else self_left idx = lr_container[idx_par] #assert self_diff[idx] == -2 idx_r = self_right[idx] diff_l = self_diff[idx_r] if diff_l == 1: # 複回転 idx_rl = self_left[idx_r] diff_rl = self_diff[idx_rl] if diff_rl == 0: self_diff[idx] = 0 self_diff[idx_r] = 0 elif diff_rl == -1: self_diff[idx] = 1 self_diff[idx_r] = 0 self_diff[idx_rl] = 0 else: # diff_lr == 1 self_diff[idx] = 0 self_diff[idx_r] = -1 self_diff[idx_rl] = 0 # 部分木の大きさの計算 self_size_l[idx_r] -= self_size_l[idx_rl] + 1 self_size_l[idx_rl] += self_size_l[idx] + 1 # 回転 self_left[idx_r] = self_right[idx_rl] self_right[idx] = self_left[idx_rl] self_right[idx_rl] = idx_r self_left[idx_rl] = idx lr_container[idx_par] = idx_rl return 0 else: # 単回転 if diff_l == 0: self_diff[idx] = -1 nb = self_diff[idx_r] = 1 else: # diff_l == 1 self_diff[idx] = 0 nb = self_diff[idx_r] = 0 # 部分木の大きさの計算 self_size_l[idx_r] += self_size_l[idx] + 1 # 回転 self_right[idx] = self_left[idx_r] self_left[idx_r] = idx lr_container[idx_par] = idx_r return nb # 新しい根の diff を返す def add(self, x): # insert # x を加える # x が既に入ってる場合は False を、 # そうでなければ True を返す idx = 0 path = [] path_left = [] self_values = self.values self_left = self.left self_right = self.right while idx != -1: path.append(idx) value = self_values[idx] if x < value: path_left.append(idx) # 重複を許さないので処理を後にする必要がある idx = self_left[idx] elif value < x: idx = self_right[idx] else: # x == value return False # 重複を許さない self.idx_new_val += 1 self_diff = self.diff self_size_l = self.size_l idx = path[-1] if x < value: self_left[idx] = self.idx_new_val else: self_right[idx] = self.idx_new_val self_values.append(x) for idx_ in path_left: self_size_l[idx_] += 1 self_diff[idx] += 1 if x < value else -1 for idx_par in path[-2::-1]: diff = self_diff[idx] if diff == 0: return True elif diff == 2: # 右回転 self.rotate_right(idx_par, self_right[idx_par] == idx) return True elif diff == -2: # 左回転 self.rotate_left(idx_par, self_right[idx_par] == idx) return True else: self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1 idx = idx_par return True def remove(self, x): # erase # x を削除する # x の存在が保証されている必要がある idx = 0 path = [] idx_x = -1 self_values = self.values self_left = self.left self_right = self.right self_diff = self.diff self_size_l = self.size_l while idx != -1: path.append(idx) value = self_values[idx] if value < x: idx = self_right[idx] elif x < value: self_size_l[idx] -= 1 # 値の存在を保証しているので idx = self_left[idx] else: # x == value idx_x = idx self_size_l[idx] -= 1 idx = self_left[idx] idx_last_par, idx_last = path[-2:] if idx_last == idx_x: # x に左の子が存在しない # 親の idx を付け替える if self_left[idx_last_par] == idx_x: self_left[idx_last_par] = self_right[idx_x] self_diff[idx_last_par] -= 1 else: self_right[idx_last_par] = self_right[idx_x] self_diff[idx_last_par] += 1 else: # x に左の子が存在する # 自身の value を付け替える self_values[idx_x] = self_values[idx_last] if idx_last_par == idx_x: # x 左 idx_last (左 _)? self_left[idx_last_par] = self_left[idx_last] self_diff[idx_last_par] -= 1 else: # x 左 _ 右 ... 右 idx_last (左 _)? self_right[idx_last_par] = self_left[idx_last] self_diff[idx_last_par] += 1 self_rotate_left = self.rotate_left self_rotate_right = self.rotate_right diff = self_diff[idx_last_par] idx = idx_last_par for idx_par in path[-3::-1]: # assert diff == self_diff[idx] lr = self_right[idx_par] == idx if diff == 0: pass elif diff == 2: # 右回転 diff_ = self_rotate_right(idx_par, lr) if diff_ != 0: return True elif diff == -2: # 左回転 diff_ = self_rotate_left(idx_par, lr) if diff_ != 0: return True else: return True diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1) idx = idx_par return True def pop(self, idx_): # 小さい方から idx_ 番目の要素を削除してその要素を返す(0-indexed) # idx_ 番目の値の存在が保証されている必要がある path = [0] idx_x = -1 self_values = self.values self_left = self.left self_right = self.right self_diff = self.diff self_size_l = self.size_l sum_left = 0 idx = self_right[0] while idx != -1: path.append(idx) c = sum_left + self_size_l[idx] if idx_ < c: self_size_l[idx] -= 1 # 値の存在が保証されているので idx = self_left[idx] elif c < idx_: idx = self_right[idx] sum_left = c + 1 else: idx_x = idx x = self_values[idx] self_size_l[idx] -= 1 # なんで? idx = self_left[idx] idx_last_par, idx_last = path[-2:] if idx_last == idx_x: # x に左の子が存在しない # 親の idx を付け替える if self_left[idx_last_par] == idx_x: self_left[idx_last_par] = self_right[idx_x] self_diff[idx_last_par] -= 1 else: self_right[idx_last_par] = self_right[idx_x] self_diff[idx_last_par] += 1 else: # x に左の子が存在する # 自身の value を付け替える self_values[idx_x] = self_values[idx_last] if idx_last_par == idx_x: # x 左 idx_last (左 _)? self_left[idx_last_par] = self_left[idx_last] self_diff[idx_last_par] -= 1 else: # x 左 _ 右 ... 右 idx_last (左 _)? self_right[idx_last_par] = self_left[idx_last] self_diff[idx_last_par] += 1 self_rotate_left = self.rotate_left self_rotate_right = self.rotate_right diff = self_diff[idx_last_par] idx = idx_last_par for idx_par in path[-3::-1]: # assert diff == self_diff[idx] lr = self_right[idx_par] == idx if diff == 0: pass elif diff == 2: # 右回転 diff_ = self_rotate_right(idx_par, lr) if diff_ != 0: return x elif diff == -2: # 左回転 diff_ = self_rotate_left(idx_par, lr) if diff_ != 0: return x else: return x diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1) idx = idx_par return x def __getitem__(self, idx_): # 小さい方から idx_ 番目の要素を返す self_left = self.left self_right = self.right self_size_l = self.size_l sum_left = 0 idx = self_right[0] while idx != -1: c = sum_left + self_size_l[idx] if idx_ < c: idx = self_left[idx] elif c < idx_: idx = self_right[idx] sum_left = c + 1 else: # c == idx_ return self.values[idx] raise IndexError def __contains__(self, x): # count # 値 x があるか self_left = self.left self_right = self.right self_values = self.values self_size_l = self.size_l idx = self_right[0] res = 0 while idx != -1: value = self_values[idx] if value < x: res += self_size_l[idx] + 1 idx = self_right[idx] elif x < value: idx = self_left[idx] else: return True # res + self_size_l[idx] return False def bisect_left(self, x): # lower_bound self_left = self.left self_right = self.right self_values = self.values self_size_l = self.size_l idx = self_right[0] res = 0 while idx != -1: value = self_values[idx] if value < x: res += self_size_l[idx] + 1 idx = self_right[idx] elif x < value: idx = self_left[idx] else: # value == x return res + self_size_l[idx] return res def bisect_right(self, x): # upper_bound self_left = self.left self_right = self.right self_values = self.values self_size_l = self.size_l idx = self_right[0] res = 0 while idx != -1: value = self_values[idx] if value < x: res += self_size_l[idx] + 1 idx = self_right[idx] elif x < value: idx = self_left[idx] else: # value == x: return res + self_size_l[idx] + 1 return res def print_tree(self, idx=0, depth=0, from_="・"): if idx == 0: idx = self.right[idx] if idx == -1: return self.print_tree(self.left[idx], depth + 1, "┏") print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) + "] diff=[" + str(self.diff[idx]) + "] size_l=[" + str(self.size_l[idx]) + "]") self.print_tree(self.right[idx], depth + 1, "┗")
まとめ
# なんで?
をつけたコードをブログで公開するやつがいるらしい
Kaggle Master になるまでにやったこと
きやうぷろあゝもすなる〇〇になるまでにやったことといふものを、かぐらもしてみむとてするなり
Kaggle 橙だ~~~~~ pic.twitter.com/1GqTJliSb7
— ⎳geu(るぎう) (@lgeuwce) 2019年4月16日
Kaggle以前
授業
自分の通う大学には各学部が開講する科目とは別にグローバルエデュケーションセンター(GEC)という謎の部門(文科省が好きそうな名前だなあ)が開講する科目がある
その中に『学習者言語の分析』という自然言語処理をする授業があって、一昨年(2017年)何故かそれを取っていた
(この時点では機械学習って言葉を知っていたか怪しい)
この授業は理系向けというわけでもなかったので理論はそこそこに実際にPythonとsklearnでいろいろ書いていく感じだった
この授業で初めてPythonをさわった
この授業で
あたりを勉強した
大学の授業は玉石混交だけどこの授業はかなり良かったし確実にKaggleにも役立った
近藤先生ありがとうございました
AtCoder
去年(2018年)の5月くらいにAtCoderをPythonで始めたら面白かったのでいっぱい問題を解いた
Kaggle以降
夏休み前くらいに学科の友人に言われてKaggleを始めた
Titanic: Machine Learning from Disaster
Titanic: Machine Learning from Disaster | Kaggle
Kaggleチュートリアルの定番であるところのTitanicをやった(8/17)
Kernelsを見ながら色々弄ってみてKaggleが何をする場所なのか把握した
去年取った授業でやったのは機械学習だったんだなあって初めて気付いた
多分初めてGBDTをさわった
解法が知れ渡っているものを実装したり(GBDTほど)精度が出ない学習器を実装したりするのは絶望的に面白くなかった記憶がある
Digit Recognizer
画像もやってみたいなと思ったのでやはり定番のMNISTをやった(8/18)
Kernels のこれ Introduction to CNN Keras - 0.997 (top 6%) | Kaggle を見ながらほぼそのまま手元で動かしてみた
Augmentationの章に入るところで飽きたので提出データを作るところまで行かなかった
NNを触ったのはこれが初めてだったと思う
Home Credit Default Risk
1423位/7198
Home Credit Default Risk | Kaggle
1週間チャレンジだった(8月下旬くらい)
AUCという評価指標に初めて出会う人になった
特徴量エンジニアリングについてめっちゃいろいろググりながらやったけど何もわからなくて公開Kernelを超えるものを作れなかった
LightGBMの他にxgboostとCatBoostも試してみたりしてLightGBMの強さを実感した
hyperoptも触ってみたりした
shakedownしたので"trust your CV"を実感した
Google Analytics Customer Revenue Prediction
29位/1089 銀
Google Analytics Customer Revenue Prediction | Kaggle
通称: Rコンペ、GAコンペ、GACRP
通称を知っておくとTwitterでググるときに役立つ
学科の友人と後輩と4人で週3で集まって取り組んだ(10月・11月)
ひどいリーク(Google Analyticsのデモアカウントに答えがある)が発覚して途中でリスタートして未来を予測するコンペになった
これのせいでKernelsが死んだ(リスタート前のいっぱいupvoteされてるKernelがずっと跋扈していた)ので色々と自力でやることになった(これのおかげで良い順位が取りやすくなってたのかもしれない)
このコンペで一番悩んだのが交叉検証だった
時系列データに対して交叉検証をどう行えば良いのかググってもよくわからなかった
結局次のようにした:
- 2017/05/01~2017/11/15のデータで2017/12/01~2018/01/31のトランザクションを予測
- 1.を全部62日ずつずらしたものを計9個作る
特徴はよく覚えてないけど確認したらこんな感じだった
(集約の方法が<lambda>
になってるのはlambda x: sum(map(bool, x))
)
あと全部Kaggle Kernelで作業してたのでデータをメモリに乗せるのに苦労した
メモリ管理が大変でhitsの情報を使い切れなかったのは少し勿体なかった
未来を予測するコンペだったので結果が出たのは2月下旬、メダル付与されたのは3月になってからだった
結果公開されてから確認したらちゃんと特徴加えてCV良くなるごとにLBも良くなってたので普通に意味のあるコンペだったと思う
PLAsTiCC Astronomical Classification
161位/1094
PLAsTiCC Astronomical Classification | Kaggle
通称: plasticc
2週間チャレンジだった気がする(12月前半)
Discussionでガウス過程が話題になってたけどなんだそれと思って流していたら何も出来なかった
Kaggleは定跡とか考えてるだけじゃだめで、よく言われるように"do everything"が大事なんだなって思った
競プロ(のマラソンマッチじゃないやつ)とかだと正しいものをじっくり考えて実装するのが大事だけど
Kaggleはとにかく思いついたものを全部やってみるのがいいっぽくて、その違いをここで理解した
Traveling Santa 2018 - Prime Paths
78位/1874 銀
Traveling Santa 2018 - Prime Paths | Kaggle
通称: サンタコンペ、kaggleサンタ
機械学習コンペじゃなくていわゆる競プロのマラソンマッチ
メダルを1個も獲れてないのがつらかったのでとにかくこのコンペで初メダルを獲ろうと思っていた(12月後半~1月上旬)
このコンペでは参加してから終わりまで大体銀圏に居ることができた
コンペ中にしても結果にしてもメダル圏に入れたのは初めてだったので、
このコンペで初めて各メダルのレベル感を理解できた
それと公開Kernelのレベルは(コンペの規模とかにもよるんだろうけど)そんなに高くないのかもしれないなって認識を得た
(巡回セールスマン問題の計算量は動的計画法を使えば都市数nに対してO(n2 2n)で済むのはググればすぐわかるけど終盤までO(n*n!)のKernelしかなかった)(でも終盤に公開されたKernel群はつよつよだったね…)
Quora Insincere Questions Classification
Quora Insincere Questions Classification | Kaggle
Rコンペのときの人たちとチームを組んだけど自分は全然協力できなかった…(1月)
NTT corevoチャレンジ: 話者の性別・年代識別 (SIGNATE)
6位/190
Competition Detail/Nippon Telegraph and Telephone Corporation | SIGNATE - Data Science Competition
通称: 音声コンペ
音声には多少ドメイン知識があったので春休みの前半を使ってこっそり参加していた(2月)
NN系のコンペにちゃんと取り組むのは初だった
最終的に特徴抽出はWORLD(f0とスペクトル包絡)、モデルはDenseNet121(転移学習)を使った
前後の無音が長いデータも多かったので似非RMS値が一番大きくなる3秒くらいを抜き出してモデルの入力に使った
入力の正規化のやり方が悪くて10回目くらいに出したスコアを50回目くらいまでずっと超えられなくて地獄だった
敗因はAugmentationをほとんどしなかったことだったと思う
自分がやったのはtrain dataに対してローパスフィルタをかけたりかけなかったりすることだけだった
なんで普通に伸縮とかピッチシフトとかしなかったのか、今思うと本当にわからない
このコンペではずっとGoogle Colaboratoryを使って実験して最後seed averageするときにKaggle Kernelも使ったりした
無課金でも割といけるなと思った
このコンペが終わったころにRコンペのメダルが付与されてKaggle Expertになった
Kaggle Expert になった pic.twitter.com/HkVVyGWROS
— ⎳geu(るぎう) (@lgeuwce) 2019年3月2日
Santander Customer Transaction Prediction
9位/8800 金
Santander Customer Transaction Prediction | Kaggle
通称: Santander
春休みの後半もデータ分析に溶けた(3月)
解法とか大体のことはもう書いた気がする
9th place solution (nagiss part) | Kaggle
Santanderコンペ中に日記をつけようとしたけど途中で飽きたもの - 菜
日記のあとの部分のハイライトを今適当に書くと、
- 爆速で順位表を駆け上がるguchioさんとチームマージ、単純なrank meanでスコアが0.922から0.923になる
- mamasさんが奔走して順位の近いソロ勢2人(Graseck、Vicens)とチームマージ
- Vicensが色々stackingを試してくれる
- 色々やってスコアが上がらないと思ったらGraseckのアンサンブル用のsubmitデータがバグっていた
- みんなお互いの特徴使い合って伸ばしてるなとか、なんかチームメイト信用しすぎると良くないなとか思って勝手にNNを試したらバグって重みが共有されていい感じのスコアが出た
- 最終日にmamasさんの提案でNNの正規化を変えたものを試すことになった(もとはRankGaussだった) MinMaxScaler使ったら学習が上手く行き過ぎたせいで締切25分前まで学習が終わらなくててんてこまいになった 10fold分の学習結果を自分がまとめるときにミスってsubmitデータの予測値を倍にしてしまったけどVicensがrerankしてくれていたのでとても救われた 残り5分の攻防だった
- 最終日の日本勢skypeで彼女いない歴=年齢の自分が地蔵になる出来事が起こった
はい
(念のためですがGraseckもしっかり活躍しています)
チームを組むと天邪鬼な性格が良い結果を生むこともあるっぽい(多様性的な意味で)
あとチームメイトは適度に信用しつつ適度に信用しないのがいいっぽい(多様性的な意味とチームメイトのバグを見つける的な意味で) 自分が一番信用出来ないけど
(4/19 0:09追記) このコンペでGBDTに5倍くらい詳しくなった(mamasさんのおかげ)
(4/19 12:24追記) mamasさんの記事が上がりました。必読です
シナモンが金メダルを3つ取ってKaggle Masterになるまでにやったこと - mamastan’s blog
まとめ
Kaggle Masterになるためにはコンペに出る必要があるようです
Santanderコンペ中に日記をつけようとしたけど途中で飽きたもの
ここはチラシの裏――
3/7 (木) くらい
R コンペがのメダルが確定して Expert になったのでしばらく Kaggle はいいかなとか思ったけど
コンペがいっぱいあってつよい人が分散してる今しか Master になるチャンスはないのでは?とも思っていた
、
Signate の音声コンペで3位を取っていた方が Santander で4位にいることに気づいたので
リベンジするために(?)Santander を始める
世界の秘密を知りつつある。 pic.twitter.com/1wdhZsRjno
— jsato (@synapse_r) March 7, 2019
この時点での kernel top は 0.898 か 0.899 くらいだったはず
R コンペのときの友人も誘ったが忙しそうだったので1人でやることになった
discussion や公開 kernel で触れられていることは
- データが綺麗すぎる(欠損値がない、全部数値データ)
- 変数どうしの相関係数を取るとどれもほぼ 0 (列が直交している)
- そのため主成分分析済みのデータかと疑う意見もあった(否定的な意見の方がそれっぽかった)
- var_68 が奇妙 (分散が小さいのに小数第4位で丸められているせい)
- なにか工夫をするよりそのまま LGBM にかける方が良いスコアが出る
他に得られた情報として、
- LB の 4位以下のスコアは 0.901 以下なのに上位 3 位は 0.904 以上
- このツイート
すごいものを見つけたかもしれない。明日真偽のほどを確かめる。
— jsato (@synapse_r) March 6, 2019
があったので、何かあるんだろうなと思った
3/8 (金) くらい
なんかデータランダムじゃなくない?と思った(このときはヒストグラムの書き方が悪くて勘違いしただけ)ので変数を Count Encoding してみたら何故かスコアが上がった
この時点では LGBM のパラメータを公開 kernel にあるベストなやつにしてなかったりしたので上位に上がったのは次の日の朝
3/9 (土)
Count Encoding したやつを提出したら 0.900 の最上位近くに来た (CV は 0.90374)
世界の秘密の一端を知りつつあるような気がする…? pic.twitter.com/w933jje90J
— ⎳geu(るぎう) (@lgeuwce) March 9, 2019
ヒストグラムの書き方の間違いに気付いたので無限に悩み始めた
The Zoo チームがぶっちぎりのスコアを出して LB 1位 に躍り出ていた
変数ごとにガウス混合モデルつかってどの山に属するかの特徴を作って
Count Encoding したやつと一緒に計 1000 特徴で学習したらなんかちょっと上がって 0.901 の最下位になった (CV は 0.90212 で低下)
たぶん誤差
ABC中に学習回してたやつ提出したらなんか順位上がった(誤差) pic.twitter.com/XY5zgSncGm
— ⎳geu(るぎう) (@lgeuwce) March 9, 2019
この時点で 11 位
3/10 (日)
bandwidth=0.004 は見た目と直感で決めた
たしかこの日くらいに一瞬 12 位に落ちたあと 11 位に戻った気がする
その後に GIBA 氏が The Zoo に join したんだけどあれは GIBA 氏だったのか・・・?
3/11 (月)
kde/count_enc の特徴量を (元の変数、count_enc と合わせて計 600 特徴量で) 使ってみると CV で 0.90578 が出た(LB は 0.900)
3/12 (火)
train の count_enc の平均と test の count_enc の平均に必ず 1.5 程度の差があることに気付いた (test のが大きい)
それに基づいて test だけ count_enc の値から 1.0 を引いて 400 特徴量で学習すると
LB が 0.901 中位くらいで 11 位から 8 位に上がった
private と public の境目らしきものに気付いた
夜 2 時間くらいしか寝られなかった
3/13 (水)
mamas さんとチームマージさせていただいた
count_enc の平均はだいたい train+2 ≒ public+1 ≒ private になってることに気付いた
それに基づいて test だけ count_enc の値から 1.0 を引いて 400 特徴量で学習すると
LB が 0.902 になって 7 位になった(直後に 8 位に戻された)
夜中
private が 50000 個ずつに分けられることを発見した
public も 50000 個ずつに分けられた
group1, group2 とした
3/14 (木)
朝 Disscussion に動きがあった https://www.kaggle.com/c/santander-customer-transaction-prediction/discussion/83882
train を target で分けて各列をシャッフルしても結果が変わらないという
このスレで CPMP がカテゴリカル変数なんじゃね的なことを言ってる
勘弁してほしい
シャッフルしても結果が変わらないってことは多分交互作用がないってことなので
ロジスティック回帰が結構良い精度出すって情報見たときに気づくべきだったなと思った
group2 を全部 0 にして submit したらスコアが変わらなくて意味不明だった
group1 を全部 0 にすると 0.500 になった
group2 || private を 0 にすると 0.901 (変化なし) だった
50% ってうそじゃん!ってなった
こうなると今まで public と private と呼んでいたものが本当に public と private なのか怪しくなってくる
mamas さんがダミーデータが入ってるのでは?と考えてくれたのでなるほどとなった
mamas さんに AUC について教わったりした
色々と提案していただいた
・全体でcount encodingした特徴を加える
・count encodingをグループ毎に行う(public group1, public, group2, private group1, private group2)
・catboostでカテゴリカルを使う
・XGBoostでexact
3/15 (金)
そういえば num_leaves=2 のモデルが効果的だって話があったけどこれ交互作用を考慮してないモデルだな?って気付いた
LB が 0.902 のやつ(元の 200 特徴と count_enc から test だけ 1 を引いた 200 特徴の計 400 特徴)に、
Train だけに fit させた Count Encoding 特徴を加えて 600 特徴で学習させると LB が 0.903 になった
ぬぬ… pic.twitter.com/OFNWKsDxY0
— ⎳geu(るぎう) (@lgeuwce) March 15, 2019
その後、複製されたデータを全部除いて Count Encoding すれば良いんじゃね?と気付いて
やってみたら count_enc の平均が違う問題とか CV と LB が一致しない問題とか色々と解決した
CV 0.90438, LB 0.904 で 8 位になってようやくスタートラインに立った気がした
⎳geu(るぎう) on Twitter: "なるほどね… "
cnt_trn と cnt_all の比をとってみると CV 0.90478 になった
mamas さんに GCP の使い方を教わった
32CPU、128GB RAM、つよそう
プリエンプティブならお金出すのでどんどん使ってください的なことを言われた
僕は貧乏性だったので価値観の違いを感じてちょっとつらい気持ちになった
cnt_trn と cnt_all の比を取った 200 特徴と差をとった(これは実質的に cnt_test) 200 特徴を加えて、
計 1000 特徴で学習させると CV 0.90517 LB 0.905 が出た(差を取るのは mamas さんの提案)
+0.001
— ⎳geu(るぎう) (@lgeuwce) March 15, 2019
現在5708teams pic.twitter.com/As2k9S9P87
3/16 (土)
AtCoder で AGC があったので始まる前に発見の要点だけ mamas さんに伝えておいた
・talkingdataをググった
・kdeを試したらcntとの比でスコアが上がった
・比を取らないでそのまま使うとCVが下がった
・ダミーのデータは正例でも負例でもなさそうだった
・public(だと思っていたもの)から目的変数にかかわらず適当に値をコピーしてる
AGC で爆死したのでしばらく引きずった
mamas さんからカテゴリカル特徴と numerical 特徴が混ざってると仮定した場合の処理を
色々と教わった
3/17 (日)
カテゴリカル特徴があると仮定して 2 つの列を使った aggrigation 特徴を作ったがスコアは下がった
この日に自分の見つけたのはこんな感じだった
・cnt/kdeの特徴量が割と強くて、cnt_trnとcnt_trn/cnt_allを消しても(=元の変数とcnt_allとcnt/kdeの600特徴で学習させても)ほとんどCVが変わらない
・target=1とtarget=0でcnt/kdeの分布が変わらないように見える
3/18 (月)
朝(昼)目を覚ますと mamas さんが 10 時くらいにこんなツイートをしていた
santander, 完全に理解してしまった可能性がある
— まます (@mamas16k) March 18, 2019
スマホを見ると mamas さんからの 9 時頃の通知があったが探しても見つからなくて幻覚だったのか?となった
mamas さんが何を発見したのか知らされてなくてずっと悶々としていた
KDE の bandwidth を倍にしたり半分にしたりしたやつの学習を試したりした(効果は微妙)
結構昼寝した
colsample_bytree を 0.05 から 0.5 まで上げたら LB 0.909 が出て順位が上がった
0.05 は交互作用あんまり考えないってことだったからそれはそうだった
0.9 も試したけどやりすぎっぽかった
6th!!! pic.twitter.com/B2fHvO5GmR
— ⎳geu(るぎう) (@lgeuwce) March 18, 2019
夜になって教えてもらったことによれば、どうやらデータは既にシャッフル済みのものらしい
話を聞いているときは割と疑ってかかってたがその後いろいろ考えてみると段々と納得してきた
それなら確かに count encoding が効いたり kde が効いたりする
そっから使える特徴が何か話し合ったりした
各 n について var_n と n_count_enc と n_cnt_per_kde だけで予測して、
その 200 個の予測結果をつかって num_leaves=2 で学習 (stacking) させたらスコアが爆上がりした
Cinnamon Power!!!!!!!!!! pic.twitter.com/8bfJds73Nj
— ⎳geu(るぎう) (@lgeuwce) March 19, 2019
それぞれちびモデルとメタモデルと名付けられた
3/19 (月) ~ 3/25 (月)
あらゆることを試したがスコアがびくともしない
順位が 3 位から 11 位に落ちた
public/private 分割とダミーデータの存在が Kernel で一気にバレた
もうおしまいだよ
3/26 (火)
mamas さんと久々におはなしして kde 抜いたのを試してないなとなったので抜いてみたらいとも簡単にスコアが上がってしまった
??? pic.twitter.com/U63nyoJr5j
— ⎳geu(るぎう) (@lgeuwce) March 26, 2019
それとは全く関係なく、ちびモデルの num_leaves を 13 から 7 に減らしたらもっとスコアが上がってしまった
?????????????? pic.twitter.com/k0EJYFvE9A
— ⎳geu(るぎう) (@lgeuwce) March 26, 2019
3/27 (水)
パラメタ探索を始めた
日記はここで終わっている・・・
Python で AtCoder を遊ぶときに知ってると便利かもしれないこと
気が向いたら後で検証したりで増やしたりするかも
割と当たり前のこととかそんなに使わないこととかが混じってる
PyPy を使う
これ必須
AtCoder で使える言語には PyPy があって Python の代わりに使える
Numpy が使えなかったりするけど速い
特にループが 3 重とかになるときに効果的
(オーバーヘッドが大きいので最初使ったときに微妙だなって勘違いしがち)
同じコードでの比較(もっと差がついたのもあった気がするけど忘れた)
Python (TLE)
https://atcoder.jp/contests/abc073/submissions/2692814
PyPy (841ms)
https://atcoder.jp/contests/abc073/submissions/2692842
入力の基本
下の 5 通りをコピペできるようにしておくと便利
# 整数 1 つ N = int(input()) # 整数複数個 N, K = map(int, input().split()) # 整数 N 個 (改行区切り) L = [int(input()) for i in range(N)] # 整数 N 個 (スペース区切り) A = list(map(int, input().split())) # 整数 (縦 H 横 W の行列) S = [list(map(int, input().split())) for i in range(H)]
input()
を速くする
import sys def input(): return sys.stdin.readline()[:-1]
これを書いておくとよくわからないけど速くなる
特に PyPy だと効果的
というか PyPy の input()
って Python より遅くないですか?なんで?
標準出力で便利なやつ
リストをスペース区切りで出力
arr = [1, 2, 3] print(*arr)
1 2 3
リストを改行区切りで出力
arr = [1, 2, 3] print(*arr, sep="\n")
1 2 3
最後に改行を入れない出力
print("あああ", end="")
処理を途中で終了するやつ
exit()
pow()
の第3引数
pow(x, y, z)
は x の y 乗を z で割った余りを返す
計算途中で巨大な数にならないので x**y % z
より高速
mod = 10**9+7 print(pow(10, 10, mod)) # 10 の 10 乗を 1000000007 で割った余り
999999937
整数 x の mod 逆元は pow(x, mod-2, mod)
で求められる
拡張ユークリッドの互除法を使うより速かった気がする
i 番目のアルファベットを整数 i に変換
ord()
で ascii 的なやつに変換して 97 を引けばいい
"a" は 0 番目なので 0 になる
print(ord("a") - 97)
0
逆変換
1 番目のアルファベットは b なので "b" になる
print(chr(97 + 1))
b
再帰の深さの上限を増やす
何もしないと深い再帰で RE する
import sys sys.setrecursionlimit(500000)
無限大
float("inf")
勝手にメモ化してくれる便利なやつ
デコレータ @lru_cache
from functools import lru_cache @lru_cache(maxsize=None) # メモ化したい関数の前につける def fib(n): # n 番目のフィボナッチ数を求める関数 if n <= 1: return 1 else: return fib(n - 2) + fib(n - 1) print(fib(80))
37889062373143906
デフォルト値のある辞書型
collections.defaultdict がかなり便利
dd = defaultdict(lambda: 3)
みたいにすると 3 が初期値の辞書ができる
グラフの問題とかいろんな問題で頻繁に使う
from collections import defaultdict cnt = defaultdict(int) # int を引数にすると 0 が初期値になる # cnt = defaultdict(lambda: 0) と書いても良い cnt[1] += 1 cnt[4] += 1 for i in range(5): print(cnt[i])
0 1 0 0 1
グラフのエッジを登録する例
from collections import defaultdict # dafaultdict をデフォルト値とした defaultdict E = defaultdict(lambda: defaultdict(lambda: float("inf"))) E[0][1] = 2 # ノード 0 から ノード 1 への長さ 2 のエッジを張る
itertools
組み合わせとか直積とか、普通なら再帰を使わないといけなくて面倒そうなやつらが一瞬で書ける
直積
from itertools import product for t in product([1, 2, 3], ["a", "b"]): print(t)
(1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b')
直積その 2
from itertools import product for t in product(["a", "b"], repeat=3): print("".join(t))
aaa aab aba abb baa bab bba bbb
順列
from itertools import permutations # ["a", "b", "c"] の並べ替えをすべて列挙する for t in permutations(["a", "b", "c"]): print(t)
('a', 'b', 'c') ('a', 'c', 'b') ('b', 'a', 'c') ('b', 'c', 'a') ('c', 'a', 'b') ('c', 'b', 'a')
組み合わせ
from itertools import combinations # ["a", "b", "c"] から 2 つ選ぶ組み合わせをすべて列挙する for t in combinations(["a", "b", "c"], 2): print(t)
('a', 'b') ('a', 'c') ('b', 'c')
重複を許す組み合わせ
from itertools import combinations_with_replacement # ["a", "b", "c"] から重複を許して 2 つ選ぶ組み合わせをすべて列挙する for t in combinations_with_replacement(["a", "b", "c"], 2): print(t)
('a', 'a') ('a', 'b') ('a', 'c') ('b', 'b') ('b', 'c') ('c', 'c')
Python のビット演算は速くない
&1 をするより %2 をしたほうが速かったりする
PyPy だと互角くらい
ソートいろいろ
from operator import itemgetter a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)] print(sorted(a)) # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る print(sorted(a, key=itemgetter(0))) # 0 番目の要素だけでソート print(sorted(a, key=itemgetter(0, 2))) # 0 番目と 2 番目の要素でソート print(sorted(a, key=lambda x: x[0] * x[2])) # 0 番目の要素 * 2 番目の要素でソート print(sorted(a, reverse=True)) # 降順にソート a.sort() # 破壊的にソート、sorted() よりも高速 print(a)
[(1, 'a', 2), (1, 'b', 3), (1, 'c', 1), (2, 'a', 0)] [(1, 'c', 1), (1, 'b', 3), (1, 'a', 2), (2, 'a', 0)] [(1, 'c', 1), (1, 'a', 2), (1, 'b', 3), (2, 'a', 0)] [(2, 'a', 0), (1, 'c', 1), (1, 'a', 2), (1, 'b', 3)] [(2, 'a', 0), (1, 'c', 1), (1, 'b', 3), (1, 'a', 2)] [(1, 'a', 2), (1, 'b', 3), (1, 'c', 1), (2, 'a', 0)]