なにも わからぬ

パソコンとプログラミング関係をメモっていきたい

Pythonで内包表記芸/内包表記でフィボナッチ第999999項

Pythonといえば内包表記芸、何でもかんでも内包表記で書けば宝くじに当たるわ身長は10km伸びるわ彼女ができて札束風呂でウハウハです(※個人の感想です)。が、今までlist.__setitem__等のメソッドを知らず内包表記をしゃぶりつくせていなかったことが判明したため、自分の理解のためにまとめてみる。

内包表記芸で使うテクニック

内包表記内ローカル変数

[i+a[i] for a in [[0,2,4,6,8]] for i in range(5)] # [0, 3, 6, 9, 12]

for文でiterableを回すと、そのfor文のブロック内で変数として使えるってだけの話なんだけど、内包表記芸ではこれを多用する。

内包表記内変数への書き込み

これがキモ。内包表記内ではn = 1のような代入式を書くことができない(と思う)が、a.append(1)は書くことができる(そして戻り値のNoneが値として評価される)。さらにa.__setitem__(0, 1)a[0] = 1と等価)やa.__delitem__(0)del(a[0])と等価)なども使えるため、リストならばほぼ自由にアクセスできると言っていい。数値や文字列の変数もoperatorモジュールのiadd()などで操作できそうに思えるが、数値や文字列はイミュータブルのため、これらのメソッドによる再代入はできない。

詳しくは 10.3. operator — 関数形式の標準演算子 — Python 3.6.1 ドキュメント

後置ifの悪用

内包表記内では後置ifっぽいのが書け、条件が真でないと以降のコードは読まれないし、リストへの要素追加も行われない。

[i for i in range(10) if i%2==0] # [0, 2, 4, 6, 8]

そしてif文に与えられた条件式は値が確定しない限り評価されるため、条件式として上記のa.__setitem__()などを書くと、要素追加は行わずに変数操作のみを行うということができる。

[a[0] for a in [[0]] for i in range(1, 11) if a.__setitem__(0, a[0]+i) or i==10] # [55]

このコードは本体リストへの要素追加の前にa.__setitem__(0, a[0]+i) or i==10を評価する。a.__setitem__(0, a[0]+i)の戻り値は常にNoneのため条件式に影響は及ぼさないが、リストaへのアクセスは毎回行われる。そして条件式が真となり本体のリストへの要素追加が起こるのはi==10のときのみ。このテクニックを使わないと、内包表記内変数へのアクセスのたびに本体の要素数が増えてしまうため重要。

内包表記でフィボナッチ数

フィボナッチ数列は漸化式で定義され、n番目のフィボナッチ数を覚えておいてn+1番目とn+2番目を求めるために使う必要があり、内包表記内では自分自身へのアクセスができないため内包表記では求められなさそうに見える。そこで内包表記内の変数としてリストを持っておき、そっちへappendすることで自分自身へのアクセスの代わりとする。

# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
[i if i<2 else (a.append(sum(a[-2:])), a[-1])[1] for a in [[0,1]] for i in range(10)]

上のコードでは0項目・1項目だけ場合分けして、あとはリストaに計算したフィボナッチ数をappendしていき、その最後の要素a[-1]を追加していくリスト内包表記となっている。a.append(sum(a[-2:]))の戻り値はNoneなので、(None, a[-1])[1]としてa[-1]のみをリストに追加している。

このコードの動作を考えるとわかる通り、内部で二重にリストを保持して無駄だし遅いしメモリも食うので、常にaの要素数が次のフィボナッチ数を計算するために必要な2個だけになるようにしてみる。

# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
[i if i<2 else (a.append(sum(a[-2:])), a.__delitem__(0), a[-1])[2] for a in [[0,1]] for i in range(10)]

要素を追加した後にindex=0の要素を消している。このコードのaが確かに要素数2個になっているかは、a[-1]の部分をa[:]にしてみるとわかる。

[0, 1, [1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 13], [13, 21], [21, 34]]

これでフィボナッチ数列をまるまる求めるコードはできたけど、結局数列を全てリストで保持しているため数が多くなるとメモリをバカ食いして死ぬことになる。

f:id:htkb:20170619222930j:plain

そこで999999番目のフィボナッチ数だけを求めてみる。ここで前述の後置ifの悪用が役立つ。

追記:999999項目と言いながら1000001項目を求めるコードだったので修正しました。ご指摘感謝します。修正ここから

if a.append(i if i<2 else (sum(a[-2:]), a.__delitem__(0))[0]) or i==999999

これはaへのappend(及びi<2ならば__delitem__も)は毎回行われるが、i==999999にならないと本体のリストへの追加を行わない。aの要素数はループが何回回っても2個に保たれるため、メモリ消費量が少ないまま内包表記でFib999999を求められる。

 [a[-1] for a in [[]] for i in range(1000000) if a.append(i if i<2 else (sum(a[-2:]), a.__delitem__(0))[0]) or i==999999]

f:id:htkb:20170622213102j:plain

修正ここまで

合ってるのか合ってないのかは知らないけど、メモリ消費量も特に増えることなく数秒後に数字がどばっと表示された。めでたしめでたし。

内包表記内で多次元リストを持ち、list.__setitem__()で値を書き込んだりすれば、内包表記内でDP(動的計画法)のテーブルを回すこともできる。

Submission #1365750 - Typical DP Contest | AtCoder

いやー夢が広がりまくりだと思いませんか!!Zen of Python?知らん!!

Ubuntu on ChromebookのSearch keyをCtrlにするなど

f:id:htkb:20170501211823j:plain 数カ月前にChromebook C302CAをAmazon.comから購入し、まあそこそこクラウドIDEなどを活用しながら使っていたけれど、補完がいまいちなIDEを使い続けるうちにピロリ菌にn年間食われ続けた俺の胃はもう限界だ!となってLubuntuをchrx経由で入れてデュアルブートにした。入れるまでの情報は腐るほどあるけどその後の情報はあまり見当たらなかったので、必要になった設定などをメモっておく。あとピロリ菌は見つけたら確実に殺しておこうな。

タッチパッドの設定

まずChrome OS上ではうまいことチューニングされていたタッチパッドの感度が異常に悪いとかタイピング時にフォーカスが飛ぶなどの問題があったため、~/.xsessionrcに以下を追加(暫定)。最適値は端末によって違うので参考程度に。

# タッチ終了を検出するしきい値
synclient FingerLow=10
# タッチ開始を検出するしきい値
synclient FingerHigh=15
# タイピング中に反応しないように両端500はタッチ開始しない
AreaLeftEdge=500
AreaRightEdge=2707
# 3本指タップで中クリック
TapButton3=2

AreaLeftEdge, AreaRightEdgeで除外された領域ではタッチイベントが開始されないけれど、タッチを開始したまま端へと指を滑らせていく分には途切れずに反応するため非常に便利。なお、タイピング中の反応を防ぐには本当はPalmDetectなどを使うようだけど今の設定で困ってないので試してない。

Synaptics タッチパッド - ArchWiki

SearchキーをCtrlキーに

ChromebookでAの左の特等席に居座るのは虫眼鏡アイコンのSearchキーで、Chrome OSでは設定でCtrlと交換できるもののLubuntuではそうもいかない。んでUbuntu 16.04以降ではxmodmapで簡単に任意のキーを交換ともいかなくなったようなのでさらにめんどくさい。

このSearchキーはUbuntu上では左Winキー(Super_L)扱いのようで、左Ctrlと交換してあげることで目的を達成できる。

qiita.com

を参考に、/usr/share/X11/xkb/symbols/pc

key <LCTL> { [ Control_L ] };
key <LWIN> { [ Super_L   ] };

となっているのを

key <LCTL> { [ Super_L   ] };
key <LWIN> { [ Control_L ] };

と中身をひっくり返してやったらうまくいった。両方ともControl_Lにしても両方Ctrlにはならなかった。リンク先でも書いてあるがこんな場所のファイルを直接書き換える方法はどうなの感が漂うのでアレだけど、これ以上調べるのはめんどくさいのでそのうちぼくは考えるのを止めた。

申し訳程度のChromebook感想

Android作ってるGoogle作のOSなので、ちょびっと開発できるモバイル機+ベッドサイドではタブレット代わりに使えるよくばりマシンになるかなと期待したけれど、タッチ操作はWindows10より若干マシ程度でAndroidタブレットには遠く及ばない。結局タッチパッドでポインタ合わせる前提のUIを指でちまちま操作する苦しみはWindows10+タッチパネルとあまり変わらず、タブレット的には全然ダメっぽい。んで純ノートとして使うと、やっぱり性能いいIDEが欲しいなと……。ブラウザで完結する作業なら使い勝手はそれなりだったし、クラウドIDEにしてもCloud9など環境を作っては捨て作っては捨てできたりするのはそれはそれで便利だったので、それなりに使い続けてはいるけれど。

ちなみにAndroidアプリも動くけどデレステなど音ゲーはだいぶ厳しそうなのでまだまだタブレット持ち運びの呪縛からは開放されなさそう。

そもそもタブレットとしてはデカすぎ&重すぎなことを身をもって実感したので、そういう使い方はそろそろ出ると噂されている↓の後継機種に期待するのがいいと思いまうす。

pythonでlru_cacheでメモ化?

例えばフィボナッチ数を求める関数

import sys
a = int(sys.argv[1])
def fib(n):
    return fib(n-1)+fib(n-2) if n>1 else n

print(fib(a))

こんなどう見たって再起しまくるのを回すと

$ time python test.py 40
102334155

real    1m39.927s
user    1m39.884s
sys     0m0.012s

とアホみたいに時間がかかるわけで、こういうのはdp[]を用意してメモ化するわけだけど、頭にlru_cacheのデコレータを付けるだけで勝手にメモ化してくれるとか。

import sys
from functools import lru_cache
a = int(sys.argv[1])
@lru_cache(None)
def fib(n):
    return fib(n-1)+fib(n-2) if n>1 else n

print(fib(a))

結果は

$ time python test.py 40
102334155

real    0m0.105s
user    0m0.100s
sys     0m0.004s

うぉーすげー!ところが上の例だとfib(333)以上を求めようとするとmaximum recursion depth exceeded in comparisonが出てしまう。普通にdpテーブルを作ると

import sys
a = int(sys.argv[1])

dp = [None for i in range(a+1)]
def fib(n):
    if dp[n] == None:
        dp[n] = fib(n-1)+fib(n-2) if n>1 else n
    return dp[n]

print(fib(a))
$ time python test.py 998
166027476624520970495418004728977018349480511983848280623585530919185737177011702010655101855958986051040947369
18879278462233015981029522997836311232618760539199036765399799926731433239718860373345088375054249

real    0m0.085s
user    0m0.060s
sys     0m0.020s

998まで出る(999以上はエラー)。こっちのが早いっぽいし、内部でどのようにメモ化してるのかわからないけどあんまり上手いことやってくれてるわけではなさそうなので、普通に自分でメモ化したほうが良さそうな気がする。

pythonのリスト操作にかかる時間

昨日のAtCoderにpython3で参加したものの、B問題でTLE連打し1完という大失態を演じ、さらには終了直後に余裕でACしてしまい悲しみに暮れたのでリスト操作にかかる時間をまとめてみた。

昨日の問題では結論から言うとループ内でlist.count(n)をしていた(リスト内に同じ数字が複数あった場合、まとめて処理すればループ回数が減らせるかなと……)のが敗因で、よくよく考えてみればlist.count(n)は処理の内容上リストを全走査しているのは明白であり、普通の競プロerならば犬のウンコを自然に避けるように判断できるのだろうけど、まだ自分の場合は「わー!なにこれー!?おもしろーい!(ふみふみ」としておきながら「うわくっせ!なんなんだよ汚えー!えーん(泣)」となってしまうレベルなので、実際に確かめてみるの大事。

環境

前提

  • リストの中身は0..n-1([i for i in range(0, n)])
  • for i in range(len(a)): の中に処理内容を入れ、ループ前後でtime.time()を取って計測
  • 少し待って結果が出ないのはクソ遅いとする
  • 最小値付近を適当に記録(省電力機能で結果が暴れるため)

結果

単位は全て秒

ループ内のコード 10^4 10^5 10^7 備考
a[i] 0.0006 0.005 0.49 n=a[i]としてもほぼ同じ
a.append(i) 0.0008 0.009 0.96
a.insert(0, i) 0.09 10.5 先頭に挿入(禁じ手)
a.remove(i) 0.02 2.1
a.pop() 0.001 0.012 1.2
a.pop(0) 0.2 2.1 先頭を削除(禁じ手)
a.index(i) 0.8 クソ遅い
a.count(i) 1.5 クソ遅い
a.sort() 1.5 クソ遅い
sorted(a) 1.9 クソ遅い
len(a) 0.001 0.008 0.8
all(a) 0.001 0.011 1.07
any(a) 0.001 0.012 1.17
sum(a) 0.8 86 コーヒーいれてたら結果出てた
max(a) 2.1 クソ遅い
min(a) 1.8 クソ遅い

リストの先頭への挿入・削除は遅いので、そのような操作を繰り返す必要があるならば先頭でも末尾でも端へのアクセスが早いcollections.dequeの使用を考える。 x1.inkenkun.com

リストでも速い末尾の削除もdequeならさらに少し速いよう。ただし、真ん中あたりへのアクセスにはめっぽう弱いのでなんでもかんでもdeque使えばいいってもんでもない。

10^5 10^6 10^7
a.pop() 0.01 0.12 1.2
q.pop() 0.008 0.08 0.83
a[int(len(a)/2)] 0.03 0.30 3.1
q[int(len(q)/2)] 0.58 110 うんこ

len()にかかる時間はどっちも同じ。


一般的に競プロでは計算量10^8がTLEのボーダーだが定数倍が軽ければ通る、ということになっているようだけど、10^8のループでa[i]をしただけで11秒、1+1passであっても2.5〜3秒もかかってしまう。pythonでは10^8のループを回した時点で死ぬし、10^7でも最適化に努めなければならないということを肝に銘じておく。大きなrangeを扱うのが重いのかな?

仙台の地下鉄が高いのでプログラミングの練習

f:id:htkb:20170130181032j:plain ようやくAtCoderのビギナーの問題が全部解けたので競プロ始めました。これから過去問でアルゴリズムと高校数学の復習をしながら早く人間になれるように頑張ります。

でなんかグラフ探索を身近な例で試してみたいと思い、遅いくせに高い仙台市営地下鉄とJRを使った運賃による重み付きグラフ探索とかどうかなと思いついたんだけど、全然グラフ探索なんかする必要のないクソ問題になってしまったので晒します。

f:id:htkb:20170130181023j:plain

N町から仙台までは電車で1駅、地下鉄は仙台までにN町駅を含めてB個駅がある。それぞれの地下鉄駅周辺の住人は「徒歩」「地下鉄」「電車(N町以外からはN町まで歩いて)」のいずれかでできるだけ安く仙台に行きたいと考えている。ただし人類は衰退したので、地下鉄1駅分歩くたびにC円の清涼飲料水を飲まなければならない。N町から仙台の電車賃がA円のとき、地下鉄の各駅において住人に利用される最大の仙台駅までの運賃を、N町駅から順に改行を入れて出力せよ。

標準入力
A B C
条件
A > 0, B > 1, C > 0
コード例
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int trainFare = sc.nextInt();
        int subwayCount = sc.nextInt();
        int drink = sc.nextInt();

        for (int i = 0; i < subwayCount; i++) {
            System.out.println(Math.min(drink*(subwayCount-i), trainFare+drink*i) - 1);
        }

    }
}
入力例 1
190 5 100
出力例 1
189
289
299
199
99

アカンこれABCの2問目未満の内容や……!次は普通に迷路でも作ってルート探索しよう……。

今さらXperia Z2を6.0でroot化など

あらすじ

  1. Xperia AX SO-01Eのテザリングを802.11a/nの5Ghzにする方法: wakunotoのブログを見てroot化→設定ファイルをいじることで5GHzテザリングが可能になることを知る
  2. 何故か手持ちのZ2でも同様に可能であると思い込む(Z2はAndroid6.0から実装の5GHzテザリングができない)
  3. すげーroot化に手間取って泣きそうになる
  4. root化に成功したのに該当ファイルが存在せずむせび泣く
  5. 無駄骨すぎて悲しいのでroot化手順だけでもブログ記事の種にする

root化手順

超大雑把な説明:Z2はlolipop以降でroot取るにはprerootedしたROMってのを焼かなきゃならん→prerooted焼くにはカスタムリカバリを焼かなきゃならん→カスタムリカバリ焼くにはroot取らにゃならん→root取るには国内版kitkatから始めにゃならん

  1. Xperia FTF からAndroid4.xのROMをDLし、flashtoolで焼く
  2. キューブ実験室:【Xperia】各機種ワンクリックroot取得【Z/Z1/Z2/Z3 等】のワンクリrootkitでrootを取得する
  3. -=- [NUT]'s XDADevelopers downloads -=-XZDualRecovery x.y.zZ2-lockeddualrecovery...をダウンロードしリカバリ入れる(install.bat→1を選択)
  4. xdaの該当スレの指示に従い "Checklist for the things you need" の 2 と 3 のリンク先をダウンロード→本体にコピーし、"Installing Guide using Sonys Official ROM (Easy and Safe Version)" を見てリカバリから適切な順番で焼く
  5. このままでは3G/LTEの通信バンドも他国ROMに上書きされ電波を全くつかまないので、flashtoolで 1. の手順で使った国内版ROMのAMSS_FSG,AMSS_FS_1,AMSS_FS_2だけ焼く

おまけ

続きを読む

AndroidのWebViewをちょっとだけ自動操縦

個人的にAndroidアプリでやりたいことと言えばネットワークサービスへのアクセスが多いのだけど、銀行系やクレカなどのネットサービスへのアクセスとなると、HTTPライブラリでゴリゴリやったりするには環境変数やクッキーを完全にうまくやらないと不正アクセスを疑われかねず怖い。例えば毎月クレカの明細からxlsxファイルを作って管理しているが、ネットワークアクセスまで自動化するのは怖いため、手動でログインし明細テーブルを選択してコピー→クリップボード内のデータを編集するPythonスクリプト実行→xlsxファイルにペーストというちょっとイケてない手順を踏んでいる。こういう定型処理を手動でやり続けるのは恥だし役にも立たないため、とりあえずネットワークアクセスからどうにかしていこう。

ログインフォームを埋めてボタンやアンカーをたどる程度ならば、実際にブラウザを利用するのが確実。フォームを埋めるのもアンカーをたどるのも全てJavaScriptを流し込むだけでできるため、WebView.loadUrl()で該当URLを読み込ませ、WebViewClientを継承したクラス内でonPageFinishedメソッド(ページ読み込み完了時に呼ばれるメソッド)をoverrideし、引数として与えられる現在のURLで処理を振り分けjavascriptを流し込めば良いようだ。

以下はMyはてなにアクセスし、ログインURLへ飛ばされたらユーザー名とパスワードを入力してsubmitボタンを押すデモ(ユーザー名とパスワードはもちろんダミー)。しかし今は素のJavaScriptにdocument.querySelector()なんて便利なもんがあるんだなあ……!

実行すると自動的にログイン処理を行い以下のようにログイン状態でmyはてなに。 f:id:htkb:20161231230805j:plain

こんな感じで2017年はちびちび細かくやったことを記事にしていきたい。