2014年2月アーカイブ

結論から先に。SMS付きSIMにすることで、セルスタンバイによる電池消費が全体の30%から20%に、電池の持ちは114%に(==8/7)、セルスタンバイによる消費量は58%に(==2/3 * 7/8)、なりました。

約半年前からIIMmioのDサービスでSIM契約してで中古端末買ってきてスマホライフを送ってるんですが、使っている Xperia acro HD はいわゆる「セルスタンバイ問題」を抱えてました。「セルスタンバイ問題」て簡単に説明すると、音声契約がついてないSIMを差しても端末(というかAndroid)が必死に音声接続できる基地局電波を捕まえようとしてしまって電池をムダに消費しちゃう問題です。Android上の「設定・電池」で「セルスタンバイ」という項目が電池消費割合で上位になってしまうことからこんな名前になってます。

この問題を解消する方法としては、Android本体にバイナリパッチを当てて直す方法なんかが広まってます。ただこれ、Root権限取って、その上で動くXposedというプラグイン施行のRootkitを入れて、そのXposedでAndroidのバグをバイナリパッチするんですね。どう考えても普通の人はやらない方がよいやり方です。というか、私的にはRoot取るのめんどかった・・・

で、普通の人はどうなるかというと、結局のところ音声契約ついてないのが悪いんだということで、各社がSMS機能付きのSIMの提供をオプションで始めました。何も背景を知らない人がこういうニュースを見ると「SMSのメールなんて誰が使うの？」と思いますが、これSMSを使うのが目的なんじゃなくて、セルスタンバイ問題を起こさないようにするのが目的なんですよね。てな経緯で、私も11月からSMS付きのSIMに変えてみました。

前置きが長かったですが本題はここから。Androidの設定の電池で確認する限り、セルスタンバイによる電池消費が、変更する前は約30%、変更したあとは約20%でした。なので割合の計算から、先に書いた結論のように、電池の持ちは114%、セルスタンバイによる消費量は58%に、なりました。

ちなみに私の使い方は、1回当たり10分程度のTwitterの使用(公式アプリ)を1日5回程度、自動同期とSIM通信は常時ON、無線LANは自宅にいるときのみ手動でON、それ以外は常にOFF(GPSとか音とかBluetoothとか)です。これで、変更前は2日は持って3日目半分行かずに電池切れだったのが、3日目ギリギリ持たず、になりました。うーん、私の場合は結局変えなくてもよかったんじゃね？というのが正直のところ・・・

実際に取り組んでたのが12月の頭頃、結果発表が1月の中旬と、なんだかずいぶんと時間がたってしまったpaizaオンラインハッカソンVol1ですが、この手のにしてはいつになくそれなりにがんばったおかげで無事C言語で1位タイ(rarul)取ることができました。運営側も他の参加者もお疲れさまでした。せっかくなので私なりにどうがんばったのかまとめておきます。

この手のは基本的にアルゴリズム部分が主になるので、そこは他の人たちがすでにたくさん解説してくれるだろうということで省きます。というか、正直私自身が、真剣にアルゴリズム部分を考える前に、友人のほぼ完成されたアルゴリズムの回答を見てしまったので、あんまり考えられてないんですよねぇ。ズルといわれても仕方ない。なので、アルゴリズムじゃないところを中心に語ります。とりあえず作ったパッケージをアップしときます(5MBくらい)。思ったよりでかかったのでソースコードだけ(6KB)のも。

まず、提出するコードが正解をはじき出さないと話にならないので、そこに取り組みます。ランダムデータ生成スクリプト(パッケージの中ではmakep.pl)等を使ってテストデータを作り、また作りかけのプログラムなどを駆使して正解データも作ります。で、作ったコードをコンパイル・実行・入力・出力・出力までにかかった時間・出力結果が正しいかを事前に用意した正解データと比較する、までをスクリプト一発で実行できるよう自動化します。パッケージの中では、make.sh, test.shあたりが自動実行、input[1-8].txtが入力データ、output[1-8].txtが出力データ(期待の正解データ)です。ここまでやるのは正直めんどいかと思いますが、本気で取り組むなら真っ先にやっとくべき箇所でしょう。

次は時間計測です。一般論として、0.1秒を0.01秒にするのと1秒を0.8秒にするのとでは、前者の方が大変で後者の方が楽だけど、前者の方が高速化効果が薄くて後者の方が高いです。つまり、相対的に時間のかかっている箇所をがんばって早くしないと、トータルでは意味がないのです。ということは、どこに時間がかかっているのかをはじき出さないとどこをがんばればいいのかがわかりません。というわけで、プログラムを細かく時間計測して、どこの処理にどのくらい時間がかかっているのかを出すことが大事になります。私は clock_gettime() で区間ごとの時刻を取りその差分で時間を計りましたが、精度よく時間が取れれば他の方法でもいいでしょう。

そこそこまともなアルゴリズムでプログラムを動かしてみるとわかりますが、今回の運営側の Case 3 を0.2秒程度で完走できるレベルになると、残りの高速化ポイントはテストデータを読み込む箇所であることがわかります。これまた一般論として、世の中で稼働してるプログラムはたいてい入出力に時間がかかってます。なぜ時間がかかるかというと、そもそも読みたいデータがまだ届いてなかったり(HDDやらネットワークからからの転送待ち)、読んだデータが期待通りのデータかを確かめないと危険だったり(操作ミスしてたりファイル壊れてたり)、おかしいときはそれなりのエラー処理をしないといけなかったり(ファイルを初期化するとかエラーダイアログ出すとか)、などなどです。今回の問題では標準入力(STDIN)から読み取り標準出力(STDOUT)に正解を書くという設定でしたが、そもそもSTDINから次々に読めるのかどうか、標準出力に次々に書けるのか、とかは一般的には考えないといけない要素でしょう。まぁさすがに今回のような問題だと、リダイレクトで読み書きさせることで、そこまで考えなくてもよいようにしてるでしょうけど。で、どうやって読込を高速化するかですが、今回の場合だとこんな感じでしょう。

scanfを使わない。運営が用意したサンプルはscanf使ってますがscanfなんて一般的に使っちゃダメです。セキュリティ面でも速度面でも。何を使うか迷うくらいなら、テキストを読むならfgets、バイナリを読むならfread、とまずは覚えときましょう。今回私はfgetsのコストも惜しかったのでfreadで読んで自前でパースしましたが、一般的にはfgetsで十分に高速です。極限まで極めたい場合のみ、システムコールのreadやmmapを使うことになると思います。まぁそこまで来たら「HTTPやファイルシステムなんておせーから自前で作ろうぜ」とかなるんでしょうけど。

atoiを使わない。厳密には読み込みじゃないですが入力処理の一環ということで。fgets等を使うと必然的にascii文字を数値に変換する必要がありますが、そんな場合は普通はatoi使います。が、計ってみるとわかりますが、atoiは結構マジメにエラー処理をしてくれる関数なため、結構時間かかります。今回みたいに'0'から'9'までとわかっている場合は自前で処理した方が早いです。

と、この辺までがんばると、もはや誤差とも言いたくなるほどの微妙な処理時間と戦うことになります。私もそこまで本格的に取り組んだことはないので胸を張っては言えなくなってきますが、たとえば、CPUの種類(周波数やらパイプライン処理やら分岐予測やら)、CPUキャッシュサイズ(CPUのL1,L2,L3サイズとアクセス速度)、を意識することになります。gcc拡張として用意されている __builtin_expect や __builtin_prefetch があるのでまずはこれを利用することとして、あとはランダムアクセスするときの配列の大きさやらループアンローリングやらパイプラインの乱れやらを意識したプログラムを作ります。このレベルになると、C言語レベルではなくて、コンパイルした結果のアセンブラコードを見た上で判断すべきですね。今回は運営側は gcc-4.7.2とは書いていますが、コンパイルオプションは書いてないですしCPUの種類も書いてないですし、正直何をターゲットに最適化したらいいか難しいです。gcc -O3で x86_64 で Ivy Bridge世代のXeonあたり、が実際のとこなんじゃないかと思いますが。といいつつ、私はテストはAtom N270なマシンでやっていましたが・・・

最後に、言うまでもないですがこの手のはアルゴリズムが大事です。テストの自動化と時間計測とを準備したら、まずはアルゴリズムを徹底して固めるのが先決です。あと、小手先高速はあんまりやらない方がいいです。特に、入力の高速化と称して標準の関数を使わずに自前で用意するとか、エラー処理をガン無視できる今回のような例だからこそ可能なだけで、一般的には徹底的にエラーチェックをすべきです。一般的には速度が求められるはまれです、もしあったとしてもピンポイントな箇所のみです、漠然と「高速化しろ」と言われてもきちんと時間計測して時間のかかっている箇所を特定してその箇所だけ努力すればいいのです。速度最優先なのは、数値計算などのごく一部の分野のみです。

ところで、景品の新人女子プログラマの野田さんがまだ送られてこないのですが、いつになるんでしょうか...