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

なにも わからぬ

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

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

Python3

昨日の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を扱うのが重いのかな?

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

Java

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アプリ開発 Java

個人的に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 Androidアプリ開発

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

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ライブラリのインスタンスをクラス変数に持たせるのはどうなのよと思うし、そもそもインターネットアクセスを全部外に出すべきなんじゃ、とも思うのだけど……。

【KotlinでAndroid】 ガチ初心者がネットワークアクセスで四苦八苦

Kotlin Androidアプリ開発

始めたばかりのガチ初心者が書いた記事なのでコードの品質は保証できません。参考にする場合は自分で調べ直してください。突っ込みを頂けたら追記・訂正します

ようやくAndroid Studioに手を出してみた。JavaもKotlinもAndroid開発もなにもかも未経験だったので、メインスレッドでネットワーク通信すると例外とか別スレッドでUIいじろうとすると例外とか、おそらく先人がみな経験したような地雷を丁寧に一つずつ踏み抜いていくことになった。ので調べたことをメモしていくことにする。

はじめの一歩

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)
    }
}

5行目のsetContentView()activity_main.xmlの内容が表示される、と同時にここで初めてviewの内容にコード側からアクセスできるようになる。javascriptで言えばここでhtmlを展開するからそれより前でDOMノード取得しようとしてもできないようなもんね。ここでsetContentViewより前でfindViewById()しようとして
f:id:htkb:20161106221157j:plain
となって悩んだ。

ネットワーク通信

setContentView()の後ろにtextview.setText("hogehoge")などとして(kotlin-android-extensions使用)viewの内容が書き換えられるのを確認後、OkHttpライブラリを使いhtmlをgetし表示しようと試みる。まずネットワークの権限がないとエラーが出るので事前にAndroidManifest.xml<manifest...の下の行に<uses-permission android:name="android.permission.INTERNET" />を追加しておく。んで

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)

        setContentView(R.layout.activity_main)
        textview.setText(getHtml())
    }
}

fun getHtml(): String {
    val client = OkHttpClient()
    val req = Request.Builder().url("http://www.google.co.jp").get().build()
    val resp = client.newCall(req).execute()
    return if(resp != null && resp.body() != null) resp.body().string() else "error"
}

とすると
f:id:htkb:20161106221157j:plain
ときたもんだ。Android Monitorを見るとandroid.os.NetworkOnMainThreadExceptionとのこと、これは超頻出問題らしく、ネットワーク通信はメインスレッドで行ってはならず非同期通信しなければならないらしい。で、この非同期通信のための最小コードがよくわからずぐぬぬぬしていたのだが、とりあえず問題なく動いたっぽいのが以下:

open class MyAsyncTask : AsyncTask<Void, Void, String>() {

    override fun doInBackground(vararg params: Void): String? {
        return null
    }
}

を頭に追加し、

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)

        setContentView(R.layout.activity_main)

        object : MyAsyncTask() {
            override fun doInBackground(vararg params: Void): String? {
                return getHtml()
            }
        }.execute()
    }
}

とする。AsyncTaskを継承したMyAsynkTaskを即時実効しているようで、doInBackground()メソッドが実際に裏で動くタスクのよう?
参照:Kotlinを使ってみよう!(2) : OkHttp編 - Takahiro Octopress Blog

非同期スレッドでUIはいじれない

以上のコードはdoInBackground()がhtmlを返しているだけなのでまだ画面に反映されない。そこでreturnするまえにtextview.setText(getHtml())などとやってみると、
f:id:htkb:20161106221157j:plain
でログにはCaused by: android.view.ViewRootImpl$CalledFromWrongThreadException: Only the original thread that created a view hierarchy can touch its views.と出る。でググってみるとやはり頻出のようで、整合性などの問題のためメインスレッド以外からUIの要素を変更したりできないようだ。そのかわり、AsyncTaskonPostExecute()メソッドはdoInBackground()が終わった後に返り値を受け取って自動的に呼ばれるようで、onPostExecute()ではUIの変更が可能なよう。そこで最終的に

open class MyAsyncTask : AsyncTask<Void, Void, String>() {

    override fun doInBackground(vararg params: Void): String? {
        return null
    }

    override fun onPostExecute(text: String) {}
}

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)

        setContentView(R.layout.activity_main)

        object : MyAsyncTask() {
            override fun doInBackground(vararg params: Void): String? {
                return getHtml()
            }
            override fun onPostExecute(text: String) {
                textview.setText(text)
            }
        }.execute()
    }
}

fun getHtml(): String {
    val client = OkHttpClient()
    val req = Request.Builder().url("http://www.google.co.jp").get().build()
    val resp = client.newCall(req).execute()
    return if(resp != null && resp.body() != null) resp.body().string() else "error"
}

こうなってようやく、
f:id:htkb:20161106224347j:plain
生のhtmlをtextviewに垂れ流すまでに至った。ここまできてようやくkotlinでロジックを書き始められそう。難しいぜAndroid