ベスパリブ

ベスパもってないです。バイク買いました。

Pythonのin演算子の計算量について

リスト(list)、タプル(tuple)、集合(set)、辞書(dict)にはin演算子がありますが、それぞれ計算量が違うようです。

python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。 - Qiita

Python Speed - www.peignot.net

リスト(list) タプル(tuple) 集合(set) 辞書(dict)
O(N) O(N) O(1) O(1)

今まではin演算子は全部O(N)かと思っていました。

なのでforループの中にin演算子を書いたら計算量がO(NM)とかになっちゃうのが嫌で使用を避けていたのですが、集合と辞書にはin演算子使っても良さそうです。

Pythonでベルマンフォード法

ベルマンフォード法とは

蟻本によれば、「重み付き有向グラフにおける単一始点最短路アルゴリズム

つまり、「始点s から各頂点i までの最短コストを求める」アルゴリズムです。

以下の条件で使えます。

  • DAG(有向グラフで閉路を持たない)である
  • 負のコストがあってもOK

すべての辺のコストが非負の場合、ダイクストラ法を使ったほうが高速に最短路が求まります。

実装と使用例

辺の数を E、頂点の数を Vとすると、計算量は O( EV )

実行結果

---sample1---
bf.exist_negatve_loop(): False
path: [0, 5, 3, 5, 4, 7]
---sample2---
bf.exist_negatve_loop(): True
---sample3---
bf.exist_negatve_loop(): True

参考URL

ベルマンフォード法の動きは、以下のリンク先が詳しいです。

Algorithm

行き詰まったり、やる気が起きないときの対処法

今の所の個人的なベストプラクティス

  • 行き詰まっているとき

  • やる気が起きないとき

    • さっさと家を出る(家にいる場合、最優先でこれをすること。家以外の施設で作業する)
    • 発声練習する
    • 体を動かす(ストレッチ・筋トレ)
    • 席を立つ(コンビニに行く)
    • アプリケーションをすべて閉じる

効果があるかもしれないと思っているもの

  • 何か書く

    • 今何しているか、何をしようとしているか、何に行き詰まっているかをノートに書き下す
    • お絵かきをしてみる
    • boogie board で思うままにラクガキ
  • 発声練習する

  • 席を立つ

    • コーヒーを淹れる
    • ストレッチ・筋トレをする
    • コンビニに行く
    • 廊下をうろうろしながら考える
  • アプリケーションをすべて閉じる

    • ブラウザのすべてのタブを閉じてみる
    • エディタを閉じてみる
    • Windowsのデスクトップ背景を眺める
    • PCをシャットダウンする
      • 一度シャットダウンする
      • 席を立つ(どっか行く)
      • 戻ってきてPCの電源を入れる
      • 最初からやり直してみる
  • 場所を変える

    • 家にいるなら、家を出る
      • 基本的に家で作業できるとは思わないこと
      • マック、スタバ、カラオケ、ビジネスホテル など
        • 車でしかいけないようなマックがgood

試したけど効果があるかわからなかったもの

  • アニメに話しかけてみる

    • 発声練習の一環
    • NEW GAME!を視聴しながら、ツッコミを入れる
      • 「なんでだよw」「走ると転ぶぞ」「怪我は大丈夫か」「俺もそう思ってた」「俺はあおっちに賛成」
      • 楽しくはあったが、何か解決策が湧いたりするわけではなかった
      • 気分転換にはなったか?
      • ついつい次の話を観てしまう
      • Amazon Primeを開いた時点で余計な情報が目に映って、そっちに興味を持っていかれる
  • そろばんアプリをしてみる

    • 頭の体操
    • ちょうどいい達成感と疲労感が残った
  • アルコール駆動開発

    • まったくうまくいかない
    • 眠くなる
  • 音楽・ラジオを聴きながら作業

    • 考えながらやるときはNG
    • 「あとはやるだけ」のときはまあOK

PythonでUnion-Find木

Union-Find木とは

Union-FindまたはDisjoint Setとは、蟻本の言葉を借りると「グループ管理のためのデータ構造」。

・要素aと要素bが同じグループかどうか

・aが属するグループと、bが属するグループを併合(unite)する

ということをしたいときに使います。

Union-Find木(深さバージョン)の実装

蟻本に書いてあるとおりの実装。

グループの併合のとき、木の深さが深いものに浅いものを併合する。

あまり使わない。競プロでは後述のサイズバージョンばかり使用している。

class UnionFindVerDepth():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループの深さ
        self._depth = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる(木の偏りが減るので)
        if self._depth[gx] < self._depth[gy]:
            self._parent[gx] = gy
        else:
            self._parent[gy] = gx
            if self._depth[gx] == self._depth[gy]: self._depth[gx] += 1

    def get_depth(self, x):
        """ xが属するグループの深さを返す """
        return self._depth[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

Union-Find木(サイズバージョン)の実装

Union-Findのサイズバージョン。

グループの併合のとき、グループのサイズ(ノードの個数)が大きいものに、小さいものを併合させる。

競プロでは大抵、ノードの個数やグループ数の最小値とかを求めるので、こちらを使うことが多い。

class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ(個数)
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる(木の偏りが減るので)
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ(個数)を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

使い方

N = 10
uf = UnionFindVerSize(N)

uf.unite(0, 1)
uf.unite(1, 2)
uf.unite(2, 3)
uf.unite(4, 5)
uf.unite(4, 6)

# {0, 1, 2, 3}, {4, 5, 6}, {7}, {8}, {9} の5グループ

a = uf.find_root(2)
print(a) # 0

a = uf.get_size(2)
print(a) # 4

a = uf.is_same_group(3, 4)
print(a) # False

a = uf.calc_group_num()
print(a) # 5

Union-Find木を使う問題

(あともう一問くらいあった気がするけど忘れた)

Pythonのリスト操作のinsert(0, v)やpop(0)の計算コストはO(N)かかる

散々語り尽くされていますが、リストの先頭に対する要素の挿入(insert)や要素の削除(pop)の計算コストはO(N)かかります。このことは公式ドキュメントのcolections.dequeの説明に記載されていているのでその該当箇所を引用すると、

docs.python.org

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

と書いてあります。

つまり、N回のforループ内で先頭に要素を追加する処理をしたら計算コストはO(N2)になります。

具体的に言うと、 C - pushpush のような問題でリストを使って解こうとすると、TLEします。

よって、先頭に対する挿入や削除操作を何度もするときはリストの代わりにcolections.dequeを使うと良いという話になります。deque(デックと読む)の先頭に対する挿入や削除操作の計算コストはO(1)です。ただしソートは使えないので注意。

検証

リストとdequeの検証を少ししてみます。

listとdequeの先頭の要素に対する操作の比較 · GitHub

from collections import deque
import time

N = 2*10**5

def list_append():
    a = []
    start = time.time()

    for i in range(N):
        a.append(100)  # 末尾に要素を追加

    end = time.time()

    print(f"list_pop: {end-start}sec.")


def list_insert():
    a = []
    start = time.time()

    for i in range(N):
        a.insert(0, 100)  # 先頭に要素を挿入

    end = time.time()

    print(f"list_insert: {end-start}sec.")


def list_pop():
    a = [1] * N
    start = time.time()

    for i in range(N):
        a.pop(0)  # 先頭の要素の削除

    end = time.time()

    print(f"list_pop: {end-start}sec.")


def deque_append():
    a = deque()
    start = time.time()

    for i in range(N):
        a.append(100)  # 末尾に要素を追加

    end = time.time()

    print(f"deque_append: {end-start}sec.")

def deque_appendleft():
    a = deque()
    start = time.time()

    for i in range(N):
        a.appendleft(100)  # 先頭に要素を挿入
    
    end = time.time()

    print(f"deque_appendleft: {end-start}sec.")


def deque_popleft():
    a = [1] * N
    a = deque(a)
    start = time.time()

    for i in range(N):
        a.popleft()  # 先頭の要素の削除
    
    end = time.time()

    print(f"deque_popleft: {end-start}sec.")


if __name__ == "__main__":
    list_append()
    list_insert()
    list_pop()

    print()

    deque_append()
    deque_appendleft()
    deque_popleft()

結果は以下の通り。

list_append: 0.009970903396606445sec.
list_insert: 5.814519643783569sec.
list_pop: 3.187533140182495sec.

deque_append: 0.008010149002075195sec.
deque_appendleft: 0.00896906852722168sec.
deque_popleft: 0.008002996444702148sec.

やはりリストでは、先頭に対する挿入と削除操作(insertとpop)は時間がかかっています。appendは両方共高速です。

RecursionError: maximum recursion depth exceeded in comparison の対策(Python3)

再帰関数を書いたら以下のエラーが発生した。

RecursionError: maximum recursion depth exceeded in comparison

エラーで検索したら以下の記事にあたった。

Python3で再帰上限数の変更 - Qiita

書いてあるとおりに、ソースに以下のコードを追加したらなおった。

import sys
sys.setrecursionlimit(100000)  # RecursionError対策

おわり。

おまけ

以下の問題を解いていた。

atcoder.jp

DPで解くと以下になる。

# -*- coding:utf-8 -*-

def solve():
    """ DP """
    N = int(input())
    H = list(map(int, input().split()))

    INF = 10**4+10
    dp = [INF]*(N+10)
    dp[0] = 0
    dp[1] = abs(H[1] - H[0])
    for i in range(2, N):
        dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]), dp[i-2]+abs(H[i]-H[i-2]))
    
    print(dp[N-1])

if __name__ == "__main__":
    solve()

再帰関数で解くと以下になる。

def solve2():
    """ メモ化再帰 
    N=1000以上で RecursionError: maximum recursion depth exceeded in comparison

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    """
    import sys
    sys.setrecursionlimit(10**5+10)  # RecursionError対策

    N = int(input())
    H = list(map(int, input().split()))

    INF = 10**14+10
    dp = [INF] * (N+10)
    dp[0] = 0
    dp[1] = abs(H[0]-H[1])

    def dfs(i):
        """ 足場iの時点の最小値を返す """
        if dp[i] < INF: return dp[i]
                
        ans1, ans2 = INF, INF
        ans1 = dfs(i-1) + abs(H[i]-H[i-1])  # i-1の足場から来た場合
        if i-2 >= 0:
            ans2 = dfs(i-2) + abs(H[i]-H[i-2])  # i-2の足場から来た場合

        dp[i] = min(ans1, ans2)

        return dp[i]
    
    print(dfs(N-1))


if __name__ == "__main__":
    solve2()

ソースのコメントに書いてあるとおり、N=1000以上のときにRecursionErrorになることを確認したが、sys.setrecursionlimit(10**5+10)を追加したら無事ACした。

競技プログラミング再帰関数を書くときは注意しよう。

私のGitの定形フロー

Gitに慣れ、だいたい以下の流れが定形になったので、備忘録として残します。

1. featureブランチの作成

機能Aを追加することになったので、developブランチから機能Aを実装する用のブランチ(feat/task-A)を作り、そこで機能Aを実装します。

# ローカルのdevelopブランチを最新の状態にする(リモートのdevelopブランチの状態にする)
$ git checkout develop  # developブランチへ移動する
$ git fetch  # リモートの情報を、リモート追跡ブランチに取ってくる
$ git merge origin/develop  # リモート追跡ブランチをマージする

# developブランチからfeat/task-Aブランチを作成する
$ git checkout develop
$ git checkout -b feat/task-A  # feat/task-Aブランチを作成し、移動する

2. 機能Aの実装中

機能Aを実装中、適当にきりのいい作業単位でコミットする

$ git add .             # ファイルをすべてインデックスに追加する
$ git status           # addしたファイルの確認
$ git reset piyo.txt    # インデックスから除外したいファイルがある場合はresetコマンドを使う(piyo.txtが除外される)
$ git commit        # インデックスをコミットする

# エディタが開くので、コミットメッセージを入力する
# 保存をするとコミット完了。やっぱりコミットしたくないときは保存しないで終了する

# コミットログを見たいときは以下のようにします。
$ git log     # commitのログが見れる(qで終了)

機能Aが実装完了するまで、これを繰り返します。

3. 機能Aの実装完了

feat/task-Aブランチで機能Aを実装しました。忘れずコミットします。

# 機能Aを実装完了したので、きちんとコミットする
$ git add .
$ git commit

ローカルリポジトリのコミットを、リモートリポジトリにpushします。

# ローカルのfeat/task-Aブランチのコミットを、リモートのfeat/task-Aにpushする。
$ git checkout feat/task-A
$ git push origin feat/task-A

pushができたら、プルリクエストをします。プルリクエストをコマンドでやる方法はわからないので、GitHubだったらそのページに行ってぽちぽち適当にボタンをクリックします。

3-1. コンフリクトが発生したら

# 競合の解決方法例

# developブランチを最新の状態にする
$ git checkout develop
$ git fetch
$ git merge origin/develop

# developブランチをfeat/task-Aにマージする
$ git checkout feat/task-A
$ git merge develop

# 競合が発生した場合、競合を解決する必要がある
# 競合の解決は、基本的に手動でファイルを修正する
# 注意1. 自分の変更内容を必ずしも優先しない 
# 注意2. わからなければ誰かに相談する

# <<<<<<< HEAD
# 自分の環境の変更点
# =======
# マージを試みた他の環境での変更点
# >>>>>>> [commit id]

# ファイルを修正して競合を解決したら、通常通りにaddしてコミットします。
$ git add .
$ git commit -m "fix conflict"

# コミット出来たらfeat/task-Aをリモートへpushします。
$ git push origin feat/task-A

4. プルリクエストが承認されたら

ローカルのfeatureブランチはもう必要ないので削除します。

$ git checkout develop
$ git branch --delete feat/task-A  # feat/task-Aブランチの削除

その他

git branch --delete feat/task-A できないとき

ローカルのdevelopブランチにfeat/task-Aの内容がマージされてない場合、エラーが出る。なので、developブランチを最新の状態にしてやれば良い。

# developブランチを最新の状態にする
$ git checkout develop
$ git fetch
$ git merge origin/develop
# 消せるようになる
$ git branch --delete feat/task-A

git checkout [ブランチ] できないとき

ブランチを移動できないとき、大抵はコミットしてないのが原因です。コミットしたくない場合、stashで一時保存すればよい。