Santa's Workshop Tour 2019 参加記

10日前まで開催されていたKaggleのSanta's Workshop Tour 2019に参加していました。結果は1620チーム中の142位。Kaggleで初めてのメダルであるブロンズメダルを獲得できました。最適化系のコンテストなのに問題のサイズが小さく、コンテストの序盤から最適解にたどり着く人が徐々に増えていく展開。しかも最適解にたどり着いた人は皆Gurobi や CPLEXなどの商用最適化ソルバを使っているらしいことがわかり、途中で戦意喪失しました。

問題概要

5000個のファミリーをday1からday100までのいずれかに割り振り、あるコストを最小化する最適化問題です。

各ファミリーには以下の情報が与えられます。

  • 家族を構成する人数: 2人から8人。4人が一番多い
  • 希望日: 各家族はchoice_0からchoice_9までの希望日を持っている。

コストは以下の2つの和として計算されます。

  • preference cost
    • 家族の割りあて方に対してつくコスト。各家族は、choice_0に割り当てるとコストが小さく、choice_9に割り当てるとコストが大きい。choice_0からchoice_9以外の日に割り当てるとさらに大きなコストとなる。
  • accounting penalty
    • 各日に割り当てられた人数の連続性に対してつくコスト。ある日に割り当てられた人数と、その次の日に割り当てられた人数とのずれが大きいほど大きなコストとなる。
    • accounting penaltyは具体的には下式で与えられる。ちょうど125人のときにpenaltyが0になることに注意。

f:id:minus9d:20200127211351p:plain

やったこと

基本的には、以下の繰り返しでした。

  • 強いNotebookが発表されて自分の順位がガタ落ちする
  • 強いNotebookの出力を初期値として、自分の実装した最適化手法を適用し、すこし良い値を出す

最終スコアである69410.61には以下のようにして到達しました。

  • Manual to improve submissions | Kaggle で提案された、特定の日を強制的に125人にするノートブックを流用。day37, day44, day51, ...を強制的に125人とした
  • それにより得られた解はいったんスコアがとても悪くなるが、以下の最適化を繰り返すと、最終的に69410.61に到達した
    • 2家族をランダムに選び、割り当て日をスワップ
      • スコアが悪化する場合でも、少しの悪化であれば確率的に受け入れる
    • N家族をランダムに選び、そのN家族について割当を総当りし、もっともよいスコアのものを選ぶ
      • もしある家族が今choice_Kを選んでいるとしたら、choice_0からchoice_Kまでを総当り
      • Nを大きくするほどあたりを引く可能性が大きくなるが、計算時間も大きくなる

焼きなましで最適解に近づけないかと試行錯誤しましたが、うまくいきませんでした。最適解の割当結果を見るとちょうど125人である日がもう一日多かったのですが、そのような分布を焼きなましで作ることは相当難しいようでした。

Windows Subsystem for Linux (WSL) でscreenを動かす

現象

Windows Subsystem for Linux (WSL) で動かしているUbuntu 16.04にてscreenを動かそうとすると以下のエラーが出ました。

$ screen
Cannot make directory '/var/run/screen': 許可がありません

解決策1 (推奨)

screenが使用するディレクトリを環境変数で指定する方法があります。例えば~/.screendirをそのディレクトリとして指定するとします。以下のコマンドでディレクトリを用意します。

$ mkdir ~/.screendir
$ chmod 700 ~/.screendir

そして、以下に示す環境変数の指定を、.bashrcや.zshrcなどに書けばOKです。

export SCREENDIR=$HOME/.screendir

解決策2 (非推奨)

ベストではない解決策としては/var/run/screenディレクトリを作成する方法があります。

$ sudo mkdir /var/run/screen
$ sudo chmod 777 /var/run/screen

この方法で一時的にscreenを使うようになりますが、OSを再起動すると/var/run/screenディレクトリが消えてしまうので、根本的な解決にはなっていません。

参考URL

Windows Subsystem for Linux (WSL) のホームディレクトリの場所

Windows 10で導入されたWindows Subsystem for Linux (WSL) を使ってインストールしたLinuxのホームディレクトリの場所を調べるには、コンソールでホームディレクトリに移動したあと

$ explorer.exe .

とすればよいです。

WSLで導入しているUbuntu 16.04から上記コマンドを打ったところ、

\\wsl$\Ubuntu\home\(ユーザ名)

エクスプローラーで開きました。

WSL Update Lets You Access Linux Files in Windows Explorer - OMG! Ubuntu! によると、この機能はWindows 10 Version 1903から加わったもので、9P protocolという仕組みを使って実現されているそうです。

Windowsのバージョンを調べるには、Win + Rで出てくるウィンドウにwinverと入力してください。

robocopyの使い方メモ

robocopyというコマンドを使って、Windowsでタイムスタンプを保持してフォルダまるごとコピーするときの自分用メモです。

基本的な使い方

基本コマンドは以下の通り。(src)と(dst)にはそれぞれコピー元フォルダ、コピー先フォルダを入れてください。

robocopy  (src) (dst) /E /COPY:DAT /DCOPY:DAT /r:3 /w:1 /LOG:copy.log /xd "$RECYCLE.BIN" /xd "System Volume Information"

他のオプションの意味は以下の通り。

  • /E: 空のディレクトリもコピー
  • /COPY:DAT: ファイルのデータ、属性、タイムスタンプをコピー
  • /DCOPY:DAT: ディレクトリのデータ、属性、タイムスタンプをコピー
  • /r:3 /w:1: コピー不能なファイルがあったとき、3回リトライ。リトライの間隔は1秒。デフォルト値の設定だとリトライが終わらない。
  • /LOG:copy.log: ログをcopy.logファイルに保存
  • /xd "$RECYCLE.BIN": ごみ箱はコピー対象から外す
  • /xd "System Volume Information"": 隠しシステムフォルダはコピー対象から外す

バッチファイルの名前に関する注意点

robocopy.batというバッチファイルを作って、その中でrobocopyを呼び出すと、robocopyコマンドではなくrobocopy.batが呼び出されてしまうので、無限ループに陥ってしまいます。バッチファイルの名前を変えましょう。

コピー先のフォルダが見えなくなる?

コピー元をドライブ、コピー先をフォルダとすると、なぜかコピー後にコピー先のフォルダが見えなくなる現象が発生しました。以下にそのときの状況を記します。

使ったコマンドは以下です。ここで、 コピー前にはC:\dir1が存在していてC:\dir1\dir2が存在していない状態でした。

robocopy  E:\  C:\dir1\dir2  /E /COPY:DAT /DCOPY:DAT /r:3 /w:1 /LOG:copy.log /xd "$RECYCLE.BIN" /xd "System Volume Information"

コピーは行われたのですが、なぜかC:\dir1\dir2フォルダに隠し属性がついていて、エクスプローラーから見えませんでした。恐ろしいことに、エクスプローラーのオプションで「隠しファイル、隠しフォルダー、および隠しドライブを表示する」を有効にしていたとしても、コピー先のフォルダは見えません。エクスプローラーのオプションで「保護されたオペレーティング システム ファイルを表示しない(推奨)」を庵チェックすることでようやくコピー先のフォルダが見えるようになります。

ちなみにCygwinからは何もしなくてもコピー先のフォルダが見えました。

どうも After Robocopy, the copied Directory and Files are not visible on the destination Drive - Stack Overflow で説明されているように、あるドライブのルートを、あるフォルダにコピーしようとしたときに、コピー先のフォルダが見えなくなることがあるようです。

この現象を回避するには、robocopy

/A-:SH

というオプションをつければOKです。

すでにコピーが終わってしまったあとでも手はあります。コピー先のフォルダに対して

attrib -h -s C:\dir1\dir2

とすれば、隠しフォルダを普通のフォルダに戻せます。

参考リンク

wgetでsegmentation faultが出たときの対症療法

wgetで2.4GBほどある大きなファイルを取得しようとしたとき、以下のようにsegmentation fault (core dumped)が出ました。

$ wget http://developer.download.nvidia.com/compute/cuda/10.1/Prod/local_installers/cuda_10.1.243_418.87.00_linux.run 

(略)
HTTP による接続要求を送信しました、応答を待っています... 200 OK
長さ: 2572375299 (2.4G) [application/octet-stream]
`cuda_10.1.243_418.87.00_linux.run' に保存中

cuda_10.1.243_418.87.00_linux.run                   94%[==========================================================================================================>      ]   2.27G  --.-KB/s    残り1m 49s zsh: segmentation fault (core dumped)  wget 

今回の場合、wget--continueフラグを使ってファイルを取得を途中からやり直すことで、無事完走することができました。

$ wget --continue http://developer.download.nvidia.com/compute/cuda/10.1/Prod/local_installers/cuda_10.1.243_418.87.00_linux.run 

(略)
HTTP による接続要求を送信しました、応答を待っています... 206 Partial Content
長さ: 2572375299 (2.4G), 129407427 (123M) 残っています [application/octet-stream]
`cuda_10.1.243_418.87.00_linux.run' に保存中

cuda_10.1.243_418.87.00_linux.run                  100%[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=====>]   2.40G   786KB/s    時間 1m 52s

2019-10-27 19:29:53 (1.11 MB/s) - `cuda_10.1.243_418.87.00_linux.run' へ保存完了 [2572375299/2572375299]

flake8を使いこなす

Pythonのコード改善のためのツール5つを試してみた - minus9d's diary の中で個人的にもっともよさそうだと感じたflake8について、使い方を詳しく調べました。

インストール

$ pip install flake8

バージョンとプラグインの確認

$ flake8 --version

すると、flake8のバージョンと、インストール済のflake8のプラグインの一覧が出てきます。以下に例を示します。

$ flake8 --version
2.6.2 (pycodestyle: 2.0.0, mccabe: 0.5.3, pyflakes: 1.2.3) CPython 3.6.4 on Windows

これはflake8のプラグインを何も入れていない状態での表示例です。ここで表示されるpycodestyle, mccabe, pyflakesが、flake8が初めから備える基本の3点セットです。pycodestypeは「PEP8のスタイル」を、mccabeは「複雑度」を、pyflakesは「エラー解析」をチェックしてくれるものです。

もしあなたが過去にflake8のプラグインをインストールしているとすると表示量が増えます。例えば以前にflake8のプラグインhacking, flake8-import-order, flake8-docstringを以下のコマンド

$ pip install hacking
$ pip install flake8-import-order
$ pip install flake8-docstrings

でインストールしていたとすると、--versionで表示されるのは以下のようになります。

$ flake8 --version
2.6.2 (pycodestyle: 2.0.0, mccabe: 0.5.3, ProxyChecker: 0.0.1, hacking.core: 0.0.1, pyflakes: 1.2.3, import-order: 0.18, flake8-docstrings: 1.3.0, pydocstyle: 2.1.1) CPython 3.6.4 on Windows

以下ではプラグインは何も入れていないものとして話を進めます。

Pythonコードの解析

コードの解析方法は2つあります。1つ目は、以下のように特定のファイルを指定する方法。

$ flake8 sample.py

2つ目は、ディレクトリを指定する方法。

$ flake8 /path/to/dir

コードの解析例

以下のPython 3コードをsample.pyという名前で保存して

import time
import sys
import fractions

def func1(varA,varB):
    '''return sum of a and b'''
    varC = 42
    return (varA + varB)


print(func1(fractions.Fraction(1, 2), fractions.Fraction(1, 3)))
3 + 5
sys.exit(0)

$ flake8 sample.pyでコード解析した結果は以下になります。

sample.py:1:1: F401 'time' imported but unused
sample.py:5:1: E302 expected 2 blank lines, found 1
sample.py:5:15: E231 missing whitespace after ','
sample.py:7:5: F841 local variable 'varC' is assigned to but never used

読み方は、"ファイルパス":行番号":"列番号":"コード":エラー内容 です。 コードの詳細は Warning / Error codes — flake8 2.6.0 documentation を参照してください。

表示の詳細化

--show-sourceオプションを付けると、ソースコードの該当部分もあわせて表示してくれます。

$ flake8 --show-source sample.py
sample.py:1:1: F401 'time' imported but unused
import time
^
sample.py:5:1: E302 expected 2 blank lines, found 1
def func1(varA,varB):
^
sample.py:5:15: E231 missing whitespace after ','
def func1(varA,varB):
              ^
sample.py:7:5: F841 local variable 'varC' is assigned to but never used
    varC = 42
    ^

さらに--show-pep8オプションを付けると、PEP8のルールを表示してくれます。いちいちメッセージの意味を調べる必要がなくて便利です。

$ flake8 --show-source --show-pep8 sample.py
sample.py:1:1: F401 'time' imported but unused
import time
^
sample.py:5:1: E302 expected 2 blank lines, found 1
def func1(varA,varB):
^
    Separate top-level function and class definitions with two blank lines.

    Method definitions inside a class are separated by a single blank line.

    Extra blank lines may be used (sparingly) to separate groups of related
    functions.  Blank lines may be omitted between a bunch of related
    one-liners (e.g. a set of dummy implementations).

    Use blank lines in functions, sparingly, to indicate logical sections.

    Okay: def a():\n    pass\n\n\ndef b():\n    pass
    Okay: def a():\n    pass\n\n\nasync def b():\n    pass
    Okay: def a():\n    pass\n\n\n# Foo\n# Bar\n\ndef b():\n    pass
    Okay: default = 1\nfoo = 1
    Okay: classify = 1\nfoo = 1

    E301: class Foo:\n    b = 0\n    def bar():\n        pass
    E302: def a():\n    pass\n\ndef b(n):\n    pass
    E302: def a():\n    pass\n\nasync def b(n):\n    pass
    E303: def a():\n    pass\n\n\n\ndef b(n):\n    pass
    E303: def a():\n\n\n\n    pass
    E304: @decorator\n\ndef a():\n    pass
    E305: def a():\n    pass\na()
    E306: def a():\n    def b():\n        pass\n    def c():\n        pass
sample.py:5:15: E231 missing whitespace after ','
def func1(varA,varB):
              ^
    Each comma, semicolon or colon should be followed by whitespace.

    Okay: [a, b]
    Okay: (3,)
    Okay: a[1:4]
    Okay: a[:4]
    Okay: a[1:]
    Okay: a[1:4:2]
    E231: ['a','b']
    E231: foo(bar,baz)
    E231: [{'a':'b'}]
sample.py:7:5: F841 local variable 'varC' is assigned to but never used
    varC = 42
    ^
    Indicates that a variable has been explicitly assigned to but not actually
    used.

79文字制限の緩和

PEP8で決められている1行79文字制限が厳しすぎると感じる場合は--max-line-lengthオプションで制限を緩和できます。

$ flake8 --max-line-length=100 sample.py

自分が修正したコードだけをチェック

既存コードを修正してコミットするとき、既存部分のスタイル違反はいったん見て見ぬふりをして、自分が修正した部分だけにflake8でチェックをかけたいことがあります。そのときに使えるのが--diffオプションです。git diffの結果を以下のようにパイプで受けます。

$ git diff sample.py | flake8 --diff

複雑度のチェック

--max-complexity N (Nは整数)をつけると、コードの複雑度(具体的にはサイクロマチック数)が閾値Nを超えている場合に、警告を出せるようになります。使い方の例は以下です。

$ flake8 --max-complexity 12 sample.py

解析除外

flake8による解析を行いたくないファイルには、

# flake8: noqa

という行を追加します。

flake8による解析を行いたくない行には、行末に# noqaを付けます。noqaとはno quality assuranceの略だそうです。

noqaを無視して解析をかけるには--disable-noqaオプションを使います。

ルールのカスタマイズ

特定のルールを無視したいときは--ignoreを使います。例えば以下のようにするとE1, E23, or W503で始まるルールを無視できます。

$ flake8 --ignore=E1,E23,W503 sample.py

逆に、特定のルールだけを有効にしたいときは--selectを使います。例えば以下のようにするとEで始まるルールだけが有効になります。

$ flake8 --select=E sample.py

自動修正は不可能

指摘点を自動修正する機能はflake8にはないようです。autopep8, black, yapfなどのツールを使ってください。(参考:formatting - How do I autoformat some Python code to be correctly formatted? - Stack Overflow

参考URL