Pythonにてリストの最後の要素を消すにはdelかpop()を使う

python

Pythonにて長さ100000のリスト arr があるとします。このリストの末尾を削除するとき

arr = arr[:-1]

とする方法は非常に遅いので要注意です。arr[:-1]により新規にリストが作成されてしまうのが原因です。ついカジュアルにこのような書き方をしてしまいがちなので注意が必要です。

上記方法に比べ、

del arr[-1]

や

arr.pop(-1)

とする方法だと1000倍ほど高速です。

検証用コードを以下に示します。

import time


ARRAY_SIZE = 100000
REPEAT_NUM = 1000


def func1():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr = arr[:-1]
        arr.append(0)


def func2():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        del arr[-1]
        arr.append(0)


def func3():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr.pop(-1)  # pop()の戻り値(指定したindexの値)はここでは使っていない
        arr.append(0)


def main():
    s = time.time()
    func1()
    print("func1() time:", time.time() - s)

    s = time.time()
    func2()
    print("func2() time:", time.time() - s)

    s = time.time()
    func3()
    print("func3() time:", time.time() - s)


main()

実行例は以下です。

$ python3 tmp.py
func1() time: 1.9272332191467285
func2() time: 0.0010654926300048828
func3() time: 0.0011544227600097656

Windows 10でディスクを入れるとVLCが起動するのを防ぐ

Windows

Windows 10でトレイにCDを入れるとVLCが自動起動して再生が始まってしまう現象に困っていました。

以下の手順により、自動起動を防ぐことができるようになりました。

  1. Explorerを起動
  2. 光学ドライブを右クリックし、「自動再生を開く」を選択
  3. 「何もしない」を選択

kaggle Traveling Santa 2018 参加記

kaggle

kaggleの最適化コンペ "Traveling Santa 2018" にソロで参加しました。結果は1874チーム中328位。着手したのが2018/12/22と遅く、冬休みはまるまる何もできず。かけた時間がいくら何でも少なすぎました。スコアが平凡であまり価値はありませんが、記録としてやったことをメモしておきます。

問題概要

2次元座標上に197769個の都市が与えられる。都市には0から197768までの番号が付いている。0から始まりすべての都市を１つずつ通る経路のうち、「経路の総距離」と「ペナルティ」の和からなるスコアが小さくなるような経路を見つける。

ここで、ペナルティは、経路を構成する都市のうち10個おきに発生しうる。もしその都市の番号が素数ならペナルティなし、素数でないなら、その都市と次の都市との間の距離に0.1をかけた値がペナルティとなる。正確な理解のためには https://www.kaggle.com/seshadrikolluri/understanding-the-problem-and-some-sample-paths を参照すること。

初期検討 - 自力実装

都市番号順に並べるだけの愚直解で 446884407.52。スコア計算が正しくできていることを確認。

初期解を求める方法を2つ実装。

1つ目はNearest Neighbor法。都市0から始めて、未使用の都市のうちもっとも近い都市を繋いでいく方法。これでスコアは1812602.18点。

2つ目は挿入法。都市0→都市1→都市0と戻る最小構成の経路を最初に作成。総距離の増加長をもっとも短くなる場所を選んで都市2, 都市3, ...を順に挿入していく。スコアを記録し忘れたがNN法よりはよかったはず。

当初は、これらで得られる経路を初期解として、後述する経路組み換えを行いスコア改善を狙った。焼きなましも実装した。しかしスコアの改善に行き詰まり、1652066.12点が限界。

Concordeの導入

カーネル https://www.kaggle.com/blacksix/concorde-for-5-min を実行。これは巡回セールスマン問題のソルバであるConcordeを実行するというもの。わずか5分で1518313.05点が出て衝撃を受ける。 これで603位相当。

Concordeは商用利用不可とあったので使って良いのか不安だったが、https://www.kaggle.com/c/traveling-santa-2018-prime-paths/discussion/72767 を読むとConcordeを使ってよいことがわかる。 そこで今後はConcordeの解を初期解として使っていくことにする。

経路組み換えの実装

Concordeで得られる経路を初期解とする。これに以下の経路組み換えを行い、スコアの低減を目指した。

  1. 2都市のスワップ
  2. 1都市を経路から削除し他の場所に挿入
  3. 経路の一部分をreverse

スコアを高速に計算できるように、「経路の総距離」と「ペナルティ」とを分けて持つ工夫をした。上記のどの経路組み換えを行っても「経路の総距離」は一瞬で計算できる。「ペナルティ」は残念ながら再計算が必要だが、それでも最悪で全都市の1/10について再計算すればよい。

また、例えば2都市を入れ替えるとき、遠くにある2都市を入れ替えても意味がない。そこで、各都市についてその近傍の都市をN個（N=10, のちに20) 持っておくようにした。これによりスコアが改善する可能性がある経路組み換えだけを実行できる。

Concordeの初期解に対して上記の経路組み換えを適用して山登りすることで、130ポイントほどスコアが向上することを確認できた。

本当は上記以外にもより複雑な経路組み換え法 (3-optなど) を実装したかったのだが、餅とおせちを食べるのに忙しくなり進捗がなくなる。その間に次々と激強カーネルが投稿された影響で順位が大幅に下がっていることに気付く。これらの激強カーネルの結果を初期解として、上記経路組み換えを行って少しだけスコア改善したものを投稿、というしょうもないことを片手間でしばらくやった。スコア改善に寄与したのは上記の方法のうち2と3だけだったように思う。スコア改善とはいっても改善幅はほんのわずかで、行き詰まりを感じる。

そこで焼きなましを導入してスコア改善を図ったが、スコアが低下したまま向上してくれず、全然うまくいかなかった。

セグメント単位の焼きなまし

終了日前日、経路を適当な長さ（100程度）のセグメントに分割し、セグメント単位で焼きなましを行うことを思いつく。ハイパーパラメータの調節をする暇は全然なかったし、一晩しか回せなかったので全セグメントを舐めきることもできなかったのだが、それでも効果はあった。終了直前に投稿されたカーネルのスコア1515564.01から、1515562.86まで改善。だがここで時間切れ。コンペ終了後も12時間ほど動かしたら1515561.30になったことからまだ少しはポテンシャルがあった。もっと早くこの方針に辿りつくべきだった。とはいえブロンズ圏内である1515493.13までたどり着くためにはこれだけでは足りなかったと思われる。

反省点

  • 他人のカーネルを使わせてもらうばかりで中をほとんど読まなかった。PythonのNumbaを使って高速計算したり、C++のコードを文字列としてファイル保存・コンパイルすることでC++のコードを動かしたり、Concordeのソースを持ってきてビルドして実行したりといった技が詰まっていたので後でも勉強したい。
  • 久しぶりにC++を書くと経路組み換え時のスコア計算がバグだらけでデバッグが大変だった。数十都市からなるミニデータでデバッグするのは有用だったのでもっと簡単にデータを切り替えられるようにしたい。
  • 経路を長さ10程度のセグメントに区切って、全経路順を生成してスコア最小のパスを選ぶ実装は簡単なのでやっておくべきだった。

"WslRegisterDistribution failed with error"への対応法（追記あり）

Windows

Windows 10にてwindows subsystem for linuxを利用したUbuntu 16.04を立ち上げると、以下のようなエラーが出て起動に失敗しました。（エラーコードの部分は0x800703faです）

Installing, this may take a few minutes...
WslRegisterDistribution failed with error: 0xXXXXXXXX
Error: 0xXXXXXXXX The parameter is incorrect.
Press any key to continue...

心当たりがあるとすれば、前回の起動時にsudo apt-get update && sudo apt-get upgradeしたときに、途中でエラーが出て失敗したのでCtrl - Cでkillしたことです。

How to resolve 'WslRegisterDistribution failed with error: - Microsoft Community にあるように以下のことをすると無事起動できるようになりました。

元回答とは異なり、自分の場合はsudo apt-get updateまでで大丈夫でした。

(2018/12/30追記) 後日、Windowsの再起動後に、上記と同じ"WslRegisterDistribution failed with error"が出ました。上記の対応法に則り、bashと打ちEnterをおしたところ、以下のエラーメッセージとともに失敗しました。

> bash
Windows Subsystem for Linux には、ディストリビューションがインストールされていません。
ディストリビューションは Microsoft Store にアクセスしてインストールすることができます:
https://aka.ms/wslstore
続行するには何かキーを押してください...

今度は以下の対応法をとることで再度Ubuntuが復活しました。

  • 「Windowsの機能の有効化または無効化」を開く
    • Explorerに「コントロール パネル\プログラム\プログラムと機能」と入力して、左側のペインから選ぶと簡単
  • "Windows Subsystem for Linux" にチェックが付いているはずなので、チェックを外してWindowsを再起動
  • 再度 "Windows Subsystem for Linux" にチェックを付けてWindowsを再起動

Visual Studio Codeで等幅フォントを使う

vscode

Visual Studio Codeはデフォルトだと日本語が等幅で表示されません。

f:id:minus9d:20181222110013p:plain

そこで以下の手順により、日本語がある場合でも等幅で表示されるようにしました。

  1. 公式ページ から Myrica.ttc をダウンロードし、インストール
  2. Visual Studio CodeでCtrl + ,して設定を呼び出し、"font family"の欄に'Myrica M'を追加
    • f:id:minus9d:20181222110551p:plain

その結果、以下のようにいい感じに文字が表示されるようになりました。

f:id:minus9d:20181222110659p:plain

(2019/5/9追記) 最新のWindows 10にバンドルされているBIZ UDフォント（モリサワ、「BIZ UDフォント」の「Windows 10 October 2018 Update」採用を正式発表 - 窓の杜）を使うと、フォントのインストール不要で等幅フォントが使えます。"font family"の欄に'BIZ UDゴシック' と書けばOKです。

このフォントの表示例を以下に示します。

f:id:minus9d:20190509230144p:plain

中古ノートPC Dynabook R734 を買いました

gadget

外での活動用にノートPCがほしいなと思っていました。友人からDynabookの中古はいいと聞いていたのでDynabook決め打ちで検索をかけ、2014年モデルのモバイル用ノートであるDynabook R734/E26KRを楽天市場で購入しました。外側に傷こそ目立つものの、中は予想していたよりもきれいで、バッテリーも4時間程度は持つ個体が来ました。十分満足いく部類だと思います。

スペック

私の入手した個体の主なスペックは以下のとおりです。詳細は R734 2014年7月発表モデル｜ダイナブック(東芝) をご覧ください。

  • CPU: Core i5 4200M
    • PassMarkによるとスコアは4034。2017年発売のCore i3 7130Uのスコアが4033で、だいたい同じです。
  • メモリ: 4GB
    • スロット数は2で空きスロット数が1。追加で PC3L-12800(DDR3L-1600)規格の4GBのメモリ を購入して増設しました。8GBのメモリにするか迷いましたが、自分の使用頻度を考えるとオーバースペックかなと。
  • ストレージ: HDD 160GB
    • 手元のSSDで換装しました。
  • 大きさ・質量
    • 13.3型ディスプレイ、約1.5kg。光学ドライブがある分少し重いです。

長所

  • 増設の容易さ
    • 裏蓋のネジを4個外すだけで容易にメモリとストレージを交換できる設計なのが良いです。アップグレードを初心者でも自力で行えるのは魅力的です。アップグレードすれば、バリバリ開発するのでなければ今でも戦えるスペックになると思います。

短所

  • 画面解像度の低さ
    • 1,366×768は今の時代だと多少見劣りします。
  • 少し重い
    • MacBook Airなどと比べると少し重いですが、持ち運びの頻度の少なさを考えると完全に許容範囲です。
  • 旧世代のメモリが必要
    • 今から旧世代のメモリを買うのに少し抵抗がありました。中古もそれほど値段が落ちてないんですよね。

総評

本体17,000円 + メモリ3,000円 でそこそこのマシンを入手できて十分満足いく買い物ができました。

注意点

中古でノートPCを買う際の注意点です。運によるところも大きいですが、避けられるものは避けましょう。

  • バッテリー欠品、充電不可の個体があります。値段の安さにつられて誤って購入しないよう注意書きをよく読みましょう。
  • 同じ"R734”でも、CPU、メモリ、ストレージ、OSが異なった個体が大量に存在します。誤って自分の期待しない機種を買わないようスペックを確かめましょう。
  • R734の赤塗装は剥がれやすいようで、どの個体も傷が目立つものが多かったです。気になるなら写真をよく見るか、他機種を探しましょう。

Windows 10の環境構築

Windows 10がブルースクリーンを繰り返す事態に見舞われ、やむなく新しいSSD ( Samsung SSD 500GB 860EVO ) を調達してWindows 10を新規インストールしました。環境構築でやったことをメモします。 （最終更新 2021-10-15）

CapsをCtrlに

Ctrl2cap

インストーラで個別にインストール

基本アプリ

開発

ドライバ類

Chocolateyを使ってインストール

Chocolateyで大体のソフトが入ります。用心のため基本的に1万ダウンロードの実績があるものしか採用していません。cinst -y [アプリ名]とするとインストールの可否を問われることなくインストールされます。

次回に新規環境構築する際はwingetへの移行を検討したいです。

editor

  • pycharm-community
  • visualstudiocode

開発

一般アプリ

以下は経験上Chocolateyで入れないほうがよいソフトです

Windows Subsystem for Linux の環境構築

  • 最初に
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install emacs lv zsh build-essential

Cygwinの環境構築

  • Archive
    • unzip, zip
  • Devel
    • cmake, gcc-g++, gdb, git, make
  • Editors
  • Graphics
  • Python
    • ぜんぶ
  • Shells
  • Utils
    • lv, screen, time, tmux
  • Web

Topcoderの環境構築

TopCoderの環境構築メモ の通りに実行

各種設定