特集記事

ランタイムから迫るAndroidアプリのパフォーマンスチューニング～ Dalvik/ART/NDKでの性能計測・比較・改善

2014/12/16 14:00

ポスト

ダウンロード Java SE 向けサンプルコード（slidesolver_java.zip） (107.0 KB)
ダウンロード Dalvik/ART/NDK 向けサンプルコード（slidesolver_android.zip） (788.5 KB)

　アプリを開発していると、パフォーマンスが問題になることがよくあります。ボトルネックの原因は様々ですが、Android環境はCPUやメモリリソースがPCに比べて限られているため、ちょっとした処理でもCPUがボトルネックになってしまいます。そこで本稿では、Dalvik/ARTで行える最適化やNDKの導入などによるアプリの高速化手法を紹介します。

ポスト

対象読者

Androidアプリ開発者
アプリのCPU/メモリ負荷によるパフォーマンスを改善したい方

題材とするスライドパズルのルール

　まずは「スライドパズルってなに？」という方向けの説明です。

　スライドパズルとは4×4などのマス目上に1から15の数値と空き枠があり、左上から右下へ向かって数字順に並べることをゴールとしたパズルゲームです。DevQuizの課題はスライドパズルを元にサイズを縦横3～6マスの可変として、さらに壁という独自ルールを加えて拡張したもので、探索アルゴリズムの難易度は高くなっています。

　事前に与えられたルールは次のとおりです。

幅3～6、高さ3～6マスのボードが与えられる
ボードの各マスは、パネル、壁、空白のいずれか
パネルは「1～9」および「A～Z」、壁は「=」、空白は「0」で示される
空白は上下左右のパネルと入れ替えられるが、壁とは入れ替えられない
空白を上下左右のパネルと入れ替えることを、それぞれ「U」「D」「L」「R」で示す
与えられた初期配置からゴール配置まで導く解を、「U」「D」「L」「R」を並べた文字列で示す
ゴール配置は、左上から右下に向かって「1→Z」のパネルが順番に並び、右下隅が「0」となる
解答に使える「U」「D」「L」「R」それぞれの総数には上限がある

　また、パズルの問題は次のような内容のファイルで提供されています。

問題ファイル

72187 81749 72303 81778             ← 1行目　　 : 手数制限 L R U D
5000                                ← 2行目　　 : 問題数
5,6,12=E4D9HIF8=GN576LOABMTPKQSR0J  ← 3行目以降 : 幅,高さ,左上から右方向に順番に配置
6,5,238=I67E9MBC1AF05HJKRLNGPDQSTO
4,6,94827601A3BCD5JGMEFNHLKI
6,5,82935=174ABCD=RHTNJKFLI0PQSOGM
…
…
…

パズルの探索エンジンに使用したアルゴリズム

　パズルの探索エンジンは、本稿用にフルスクラッチで作成しました。使用しているアルゴリズムは、幅優先探索を基本に、A*アルゴリズムや双方向探索を組み合わせた独自のアルゴリズムです。ただし、解答のためのアルゴリズム自体は本稿の主旨ではないので、ここではそのさわりだけ解説します。

　図1は全体の探索フローを表しています。「3,3,120743586」は盤面が3マス×3マスのスライドパズルを表しており、これを入力として与えられたエンジンがその解答を探索しています。

図1：幅優先探索、枝刈り、双方向探索、A*

　ルールでは0が空きセルで、そこを起点として上下左右に移動可能です。そこで、幅優先探索をベースとして、図1のSTARTと書かれている初期配置から移動可能な左方向と下方向へ0を進めます。

　各盤面の右上の吹き出しは盤面の「評価関数」の結果を表し、この数値が少ないほどゴールに近いと判断されます。評価関数は、0を除く各マスが本来あるべき場所からずれているマス数の合計としています。初期配置では3、4、6、7がそれぞれ本来の位置から1マスずれ、5が2マスずれているため、評価関数の結果はこれらを合計した6となります。この数値のことをマンハッタン距離と呼んでいます。マンハッタン距離が0になると、各マスがすべてあるべき位置にいることになり、ゴールに到達したことになります。

　ただし、単純に幅優先探索を行うと、盤面パターンが極端に増加してCPU負荷・メモリ消費ともに不足するため、適時「枝刈り」という処理を行います。図1の例では、赤い×印の付いた盤面はマンハッタン距離が増加しているため、ゴールにたどり着く可能性が低いと判断して以降の探索を打ち切っています。

　また、スライドパズルはゴール時の盤面が決まっているので、ゴールからスタートに向けての逆方向探索も可能です。スタートとゴールの両方から探索し、同じ盤面が現れたらゴールにたどり着いたことになるのですが、これには計算量を減らせるという利点があります。スタートからゴールの移動距離をd、各盤面から枝分かれが2経路ずつあり、枝刈りを行わないとすると、順方向でゴールまで探索した場合の計算量は O(2^d) となりますが、双方向探索では O(2^d/2 + 2^d/2) となって計算量が削減されます。

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内