読者です 読者をやめる 読者になる 読者になる

なにも わからぬ

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

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年はちびちび細かくやったことを記事にしていきたい。

Majestouch Convertible 2 Tenkeyless黒軸を買ってやや後悔してる話

f:id:htkb:20161204042836j:plain

Majestouch Convertible 2赤軸とMinila Air赤軸をメインに使ってきたが、Convertible 2 Tenkeylessが出たこともありかねてから気になっていたTenkeyless黒軸を購入してみた。まだ使い始めだけど、正直なところ満足していないし後悔している。ただネットを見ていると赤軸/黒軸に対して誤解が多いように思うので、こちらも素人ながら簡単な説明とともに使用感を記してみる。

ざっくりとしたCherry MXスイッチの種類と特徴

現在、一般的にメカニカルキーボードと呼ばれているもののほとんどはキースイッチにCherry MXスイッチが採用されており、Cherry MXスイッチの中にも様々な種類があり色で区別される。代表的なものが茶軸・青軸・赤軸・黒軸で、茶軸/青軸と赤軸/黒軸ではその性質が大きく異なる。特に赤軸/黒軸のいわゆるリニア軸は他の一般的なキーボードとも使い勝手が大きく異なるため、安物のキーボードの上位互換的なものを期待して初メカニカルに赤軸/黒軸を購入すると期待を大きく裏切られ、メカニカルキーボードアンチにその身を堕としてしまう人もいるとかいないとか……。

茶軸と青軸は押下圧(押し下げるために必要な力)のピークが1mm程度押し下げた辺りにあり、このピークを越えると急激に押下圧が下がるため、「スコン」と底まで自然にキーを落とす形(底打ち)になる。このように底打ちしやすく、かつ底打ちしたときのクリック音によるタイピング時の爽快さが人気の秘密。キーボードを叩くに当たっての特別なコツなども必要なく扱いやすい。

一方で赤軸と黒軸はリニア(直線的)軸と言うとおり、押し下げれば押し下げるほど直線的に押下圧が高まっていく。底に至る地点がもっとも押下圧が高くなるため、普通のキーボードの感覚で底打ちさせようとすると重く感じる。特に黒軸は赤軸の重いバージョンなので、これを1タイプ1タイプ底打ちさせていったのでは腱鞘炎になってしまう。ネットでの口コミも黒軸は重くて手を痛める的なものが多く、そういう人は普通のキーボード感覚で底打ちさせているのだろう……と思っていた。

じゃあどうするのかというと、キー入力を受け付けるポイントは底よりもかなり浅い位置にあるため、キー入力ポイントを大体指で覚えてその辺りで押し込むのをやめ、反発力に任せて指を上げて次の運指に移行する……という、撫で打ち(浅打ち・半打ち・etc)が基本になる。別に赤軸・黒軸で底打ちしてはいけないというわけではないが、赤軸・黒軸のメリットが何もない上に黒軸だと重くて指を痛めてしまうだろう。逆に撫で打ちの際には黒軸の強い反発力が次の運指への推進力を生み、快適な高速タイピングが可能になる……はずだった。

なんで赤軸持ちが黒軸買ったの?

赤軸は軽すぎて、意識して撫で打ちしても結構底打ちが出てしまう。丸3年使ってこれなので赤軸で底打ちを無くすのは不可能と判断した。赤軸なら底打ちになっても十分軽いし特に困ってるわけではないけど、黒軸の反発力に任せて底打ちを減らしスムーズな運指が可能になると思った。ついカッとなって買った。キーボードなら何でもよかった。今は反省している

で、どうだったの?

重すぎる。撫で打ちを意識すると入力抜けが出る(キー受付の深さまで達してない)。特に右手小指のpや-(ハイフン)を2回以上重ねるときにものすごく抜ける。かといって力を入れると底打ちになってしまい、「底打ちしないが確実に入力は受け付けてもらえる」という微妙な力加減ができない。触ってる感じも重たくて右手が疲れる。慣れの問題ではないような感じがする……。その一方で押し下げるときの重たさは感じても反発力で指が浮かされるような感触は得られず、タイピングも押し下げが重くなった分遅くなっただけ。

f:id:htkb:20161204041137j:plain 赤軸でも500行かないくらいだけどね……。

赤軸に慣れきったからこう感じるのかもしれないし、しばらく使ってみようとは思うけど、駄目ならConvertible2の赤軸スイッチをTenkeylessに移植手術しちゃおうかなぁ。スイッチの問題はともかくテンキーレスは非常に良いよ。テンキーあるとマウスがかなり右側にずれることになるし相対する画面に対してキーボードの中心も右側にずれるの気持ち悪い。

kotlinで複数回献血クラブのスクレイピングライブラリ&Serializableでハマった話

例のごとく初心者が書いた記事です。突っ込み歓迎します

kotlinで書いた複数回献血クラブ用のスクレイピングライブラリが一応動く形になったので、キリもないしgistに貼って一旦公開してみる。ほんとは献血クラブ非公式クライアントとしてサクッとアプリにして公開したかったけど、Android固有の知識がいろいろ求められてしんどい。自分以外誰得な内容だし習作のテーマ間違った気がする……!!

今のところ

val scraper = Scraper(ID, PASS1, PASS2)

インスタンスを作るとログイン後の1ページ分(最大10回分)の献血データをダウンロードしscraper.recordIndexscraper.bloodDataに書き込まれ、2ページ目以降のデータも取得したければscraper.next()を繰り返す……だけのもの。自分以外使わないだろうけど少しずつ修正していきます。

長いのでリンクのみ
A scraper for www.kenketsu.jp

Serializableやtransientでハマった話

AndroidのActivityをまたいでデータをやりとりするにはintent.putExtra()を使うようだけど、文字列型や整数型などのプリミティブ型以外の自作クラスのインスタンスなどを送る場合は、バイト列などに変換できることを保証するSerializableであることを示さなければならないそう。Serializableはメソッドも何もないマーカークラスというやつで、これを継承しているクラスのみがSerializeできるものとしてActivityをまたぐことができ、インスタンス変数なども含めてSerializableを継承していないクラスが混じっているものをまたがせようとするとエラーが出る。

で、自作クラスには全部Serializableをおまじないのように継承させたが、外部ライブラリであるOkHttpは継承クラスを作ろうとしてもなんかうまく行かず?どーすっぺと適当にぐぐっていたら見つけた@transientを頭に付けてインスタンス変数を宣言すればいい、というのを意味もわからず実行した。

class Scraper(...) : Serializable {
    @transient var client:OkHttpClient

そのときのコードは、Activityをまたぐ前にclientを使ったメソッドを実行し、またいだ後にインスタンス変数の一部を参照するだけだったので問題が露呈しなかったが、作り続けていくうちに当然Activityをまたいだ先でもメソッドを実行させるようになり、そこでclientへのアクセスがあったときにNullPointerExceptionが起こるようになった。困っていろいろググったところ、transientはSerializeの対象外にするという宣言であり、Serializeしてデータを送るときにtransientの宣言されたデータは送られない=nullとなる?というようなことがわかった。

参考:Java直列化メモ(Hishidama's Java Serializable Memo)
【Java】Serializableの基本(シリアライズ・直列化) - TASK NOTES

あーやっちまった全部作り直しかーと思っていたら、static変数はもともとSerializeの対象外であり、kotlinではcompanion objectの中に突っ込むことで実現できるとわかった。

class Scraper(...) : Serializable {
    companion object {
        lateinit var client:OkHttpClient
    }

これでthis.clientScraper.clientに変わったくらいで事なきを得た。HTTPライブラリのインスタンスをクラス変数に持たせるのはどうなのよと思うし、そもそもインターネットアクセスを全部外に出すべきなんじゃ、とも思うのだけど……。