ベスパリブ

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

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で一時保存すればよい。

Chrome拡張のContent Scriptのメモ

Content Scriptについて

  • Content ScriptはWebページに差し込まれる
  • Webページ内のidなどの要素にはアクセス可能
    • document.getElementById('title')などが可能
  • Webページ内のJavaScriptの変数にはアクセス不可能(スコープが違うので、Content Scriptの変数とバッティングすることはない。深く考える必要はない)
  • Chrome拡張のAPIの一部のみ使用可能
  • 上記の使用不可能なものを使いたいときは、Event Pageを介してデータのやり取りを行う
    • chrome.runtimeにあるSend Messageを使って、Content ScriptからEvent Pageに対してMessage Passingしてやり取りを行う

Anacondaの環境変数のパス(Windows)

$ conda update anaconda-navigator をしたらCondaHTTPErrorとかSSLErrorとかエラーだらけになった。

メインPCだとエラーにならず、ノートPCだとエラーになったので、メインPCと同じ設定にしようと思って環境変数のパスを確認したらパスが足りなかった。最終的なパスを残しておく。

C:\Users\XXXX\Anaconda3
C:\Users\XXXX\Anaconda3\Library\mingw-w64\bin
C:\Users\XXXX\Anaconda3\Library\bin
C:\Users\XXXX\Anaconda3\Library\usr\bin
C:\Users\XXXX\Anaconda3\Scripts

SSHでもBitbucketのpushやfetch時に毎回パスワード聞かれるときの対処法

ググったら似たような症状が出るわけです。

ただし上記の記事は、「HTTPSからSSHに変更したら直る」という内容です。

私の場合、SSHからHTTPSに変更したら直りました。以前まではSSH推奨であったが、今ではHTTPS推奨に変わったのでしょうか?(本当か?)推奨は時代によって変わるので、そういうことかもしれませんが確証はありません。

# リモートリポジトリのURLを表示する(git@で始まっているので、SSH接続)
$ git remote -v
origin  git@bitbucket.org:YYYY/MYPROJECT.git (fetch)
origin  git@bitbucket.org:YYYY/MYPROJECT.git (push)

# fetchすると、毎回SSHキーのパスワードを聞かれる
$ git fetch
Enter passphrase for key '/c/Users/XXXX/.ssh/bitbucket/id_ed25519':

# リモートリポジトリのURLをHTTPSに変更する
$ git remote set-url origin https://USERNAME@bitbucket.org/XXXX/MYPROJECT.git

# リモートリポジトリのURLを確認する(HTTPSになっていることを確認)
$ git remote -v
origin  https://USERNAME@bitbucket.org/YYYY/MYPROJECT.git (fetch)
origin  https://USERNAME@bitbucket.org/YYYY/MYPROJECT.git (push)

# 初回だけパスワード聞かれるが、二回目以降は聞かれなくなった
$ git fetch

ちなみにGitHubHTTPS推奨(2019年3月14日現在)というのがわかりますが、Bitbucketはそういう記事を探しても見つかりませんでした。

ただし、Change the remote URL to your repositoryの記事を読んでみると、

Update the URL for Git repositories

(中略)

If you update your URL from HTTPS to SSH, next time you push or pull from your repository, the terminal responds that it is adding the Bitbucket host to the list of known hosts. You also won't have to enter a password.

とあり、「(Gitリポジトリを)HTTPSからSSHに変更した場合は次回からパスワード聞かれない」とあります。

また、

Update the URL for Mercurial repositories

(中略)

If you update your URL from HTTPS to SSH, next time you push or pull from your repository, the terminal responds that it is adding the Bitbucket host to the list of known hosts. You also won't have to enter a password.

とあり、「(Mercurialリポジトリを)SSHからHTTPSに変更した場合は次回からパスワード聞かれない」とあります。

つまりぜんぜんわからないですが、URLを変更したらパスワードは聞かれなくなるということでしょうか。本当か?

com_error at / (-2147221008, 'CoInitialize は呼び出されていません。', None, None)

エラーの対処法

Djangoで作ったWebアプリケーションで表題のエラーが発生しました。

このWebアプリは、Web画面でファイルをアップロードし、ファイルをサーバーに渡し、サーバー側でExcelを起動しファイルを処理する。というようなものです。Excelを起動するときにエラーが発生しているようです。

Internal Server Error: /
Traceback (most recent call last):
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\win32com\client\dynamic.py", line 89, in _GetGoodDispatch
    IDispatch = pythoncom.connect(IDispatch)
pywintypes.com_error: (-2147221008, 'CoInitialize は呼び出されていません。', None, None)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\django\core\handlers\exception.py", line 34, in inner
    response = get_response(request)
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\django\core\handlers\base.py", line 126, in _get_response
    response = self.process_exception_by_middleware(e, request)
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\django\core\handlers\base.py", line 124, in _get_response
    response = wrapped_callback(request, *callback_args, **callback_kwargs)
  File "C:\Users\XXXX\workspace\myproject\csv2excel\views.py", line 73, in config_table_maker
    feat_names = handle_uploaded_file(request.FILES["file"])
  File "C:\Users\XXXX\workspace\myproject\csv2excel\views.py", line 61, in handle_uploaded_file
    feat_names = sample(file_name)
  File "C:\Users\XXXX\workspace\myproject\csv2excel\views.py", line 20, in sample
    excel = Excel()
  File "C:\Users\XXXX\workspace\myproject\src\mods\Excel.py", line 17, in __init__
    self._app = win32com.client.Dispatch("Excel.Application")
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\win32com\client\__init__.py", line 95, in Dispatch
    dispatch, userName = dynamic._GetGoodDispatchAndUserName(dispatch,userName,clsctx)
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\win32com\client\dynamic.py", line 114, in _GetGoodDispatchAndUserName
    return (_GetGoodDispatch(IDispatch, clsctx), userName)
  File "C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\myproject\lib\site-packages\win32com\client\dynamic.py", line 91, in _GetGoodDispatch
    IDispatch = pythoncom.CoCreateInstance(IDispatch, None, clsctx, pythoncom.IID_IDispatch)
pywintypes.com_error: (-2147221008, 'CoInitialize は呼び出されていません。', None, None)

サーバー側でログインしてコンソールでプログラムを動かすことはできていて、Webアプリを介して(ブラウザからリクエストして)プログラムを動かそうとしたらこのエラーが発生します。

Apacheでアプリを作った時に、Apacheユーザ(www-data)にsudoersで権限を渡さないとブラウザからのリクエストでサーバ側のプログラムを走らせられないという現象に似ているので、それと同様のエラーでしょうか。

ということはDjangoに何かしらの権限を渡せば動きそうですが、そういう設定はどこで書けばいいのかちょっとわかりません。

色々調べてたら、下記の記事に同様の現象について書いてありました。

[Delphi] CoInitializeが呼び出されていません - くろねこ研究所

このため、CUI アプリケーションでこのエラーメッセージを回避するには、CoInitialize を呼び出すなどの対策が必要になる。また、CoInitialize と対で CoUninitialize を呼び出さないといけない。

この方は私とは逆に、CUIだとエラーが発生するそうです。

COM を使うとその部分は、結構長くなることが多いと思うので、クラス化して、その Create と Destroy に それぞれ CoInitialize と CoUninitialize を追加するのがオススメである。

ほかの記事も色々見たのですが、Excelを起動する前にCoInitialize()を呼び出し、Excelを終了した後にCoUninitialize()を呼び出すとOKっぽいことがわかります。クラスで書くとこんな感じでしょうか。

# -*- coding:utf-8 -*-
from win32com.client import gencache, Dispatch
import pythoncom

class Excel():

    def __init__(self, visible=False):
        """ Excel機能を提供するクラス """
        pythoncom.CoInitialize()  # Excelを起動する前にこれを呼び出す
        self._app = Dispatch("Excel.Application")
        self._app.Visible = visible

    @property
    def app(self):
        return self._app

    def quit(self):
        """ Excelを終了させる """
        self.app.Quit()
        pythoncom.CoUninitialize()  # Excelを終了した後はこれを呼び出す

で、書き換えたら動きました。ただ、このCoInitialize()が何なのか正直よくわからない。

参考URL

Coinitializeとは?

わからないままにしとくのはちょっと怖かったので、少し調べます。

[連載! とことん VC++] 第 1 回 COM 再入門 ~ COM オブジェクトの基本的利用 (COM クライアントの実装) ~ in C++

  1. CoInitialize の初期化が意味すること ~ アパートメントの準備 ~ ここで、[3] の初期化の意味をもう少しく詳しく確認しましょう。

CoInitialize 関数は COM オブジェクトの実行環境ともいえる「アパートメント」を必要に応じて 1 つ作成する役割を持ちます。この関数呼び出しによって、アパートメントを準備しなければ、COM オブジェクトを実行できません。

このアパートメントには 2 つの種類があります。それは、「STA (Single Thread Apartment)」と「MTA (Multi Thread Apartment)」です。実は、[3] の CoInitialize 関数は、STA のアパートメントを作成する作用があり、次のように CoInitializeEx 関数を使用する場合と同じです。

CoInitializeはCOMの初期化をする関数で、STAかMTAで初期化するそう。

そもそもCOMというものを明確に理解していないのでググります。

COM(Component Object Model)とは - IT用語辞典 e-Words

COMとは、マイクロソフトMicrosoft)社が提唱していた、ソフトウェアの機能を部品化して外部から呼び出して利用する仕組みを定めた技術仕様の一つ。主に同社のWindowsシリーズのOSやその上で動作するソフトウェアで利用された。

プログラムの機能を外部から呼び出して利用するための手順やデータ形式などの標準を定めており、COMの仕様に則って開発されたソフトウェア間は容易に連携して動作させることができる。特定のOSやプログラミング言語に依存しない仕様になっており、異なる言語やOSで開発されたプログラムを連携させることができる。

まあつまり、「外部アプリケーションであるExcelpythonで呼び出すにはCOMという技術を使うので、COMの初期化が必要。」というのはわかりました。でも結局、どうしてWebアプリから実行したときだけこの初期化が必要になったのかはよくわかりませんでしたね(眼鏡クイッ)。