Hatena::ブログ(Diary)

yukobaのブログ このページをアンテナに追加 RSSフィード Twitter

2014年06月28日 動的計画法の問題を機械的に解く方法

動的計画法問題機械的に解く方法

情報オリンピックという中高生向けの競技プログラミング大会があります国内予選・選抜が3回あり、最後世界大会があります。アルゴリズムの問題が出題されます。予選の毎年のパターンは問1, 2は問題文をコードに起すだけの問題で、問3はアルゴリズムの問題だったり、中学受験的な算数の問題だったりします。問4はいつも動的計画法の問題が出ます。競技プログラミングでは動的計画法が一番の入門であり、これがスタートラインです。これが解けないと始まりません。動的計画法の問題、機械的に解けるのかなと思い色々と考えたのですが、できそうなので、このブログ記事にまとめます。

動的計画法

動的計画法ですが、やはり一番しっかり書かれているのが、書籍「アルゴリズムイントロダクション」 http://www.amazon.co.jp/dp/476490408X です。動的計画法の章は熟読に値すると思います。「動的計画法」という言葉定義は若干人によってブレがあるのですが、アルゴリズムイントロダクションの定義に従いますと、以下の2つを行うアルゴリズムの総称です。

  1. 部分問題を解いて、その計算結果を利用して、全体問題を解く。
  2. 部分問題の計算結果を再利用して計算量を減らす。メモ化

なお、トップダウン(全体問題を解いてから部分問題を解く)とボトムアップ(部分問題を解いてから全体問題を解く)という2つの実装方法があるのですが、これは、あくまでも実装方法の話であり、トップダウンをボトムアップに置き換えるのは機械的な作業であり、本ブログ記事ではトップダウンで記事を書きます。トップダウンはメモ化再帰とも呼ばれます。

そして、このように定義は広いにもかかわらず、実際に出題されるのは、もっと狭い範囲で出題されます。問題文はこのパターンばかりです。

デカルト冪(リスト, N).filter(list ->
    問題文の条件に合うリストを絞り込む
).mapToInt(list ->
    list を整数に変換
).集約関数()

上記を含め、以下、Java 8 風の擬似コードを使います。なお、1..3 という表記は [1, 2, 3] のリストという表記です。rangeClosed(1, 3) の事です。あと、記事の書きやすさの都合上、リストの添え字は 1 から始まると言うことにさせてください。

デカルト冪の定義は 直積集合 - Wikipedia に書いてありますが、例えば、デカルト冪(1..2, 3) == [ [1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2] ] です。リストのリストです。

集約関数max(), min(), sum() のどれかです。場合の数を数える問題も良く出ますが、その際は mapToInt(list -> 1).sum() にすると、統一的にこの表記になります。

解法の手順

解法の手順は以下の通りです。詳しくは具体例で説明していきます。

  1. リスト末尾 k 個を定数化します(k は通常 1〜3 です)。filter 内の定数をまとめ、mapToInt 内の定数は集約関数の外に出します。
  2. ループ1つ前のリスト末尾 k - 1 個を定数化します。
  3. 1 と 2を比較して、代入します。

定数化するというのは場合分けをするという意味です。以下、読んでいくとその意味が分かると思います。また、出題パターンとして、部分問題に分ける際は、N を 1 と N - 1 に分ける問題ばっかりです。

0-1ナップサック問題

動的計画法の一番基本的な問題は、0-1ナップサック問題です。これの派生形で出題されます。問題文は ナップサック問題 - Wikipedia を読んでください。これを擬似コードにおこすと以下のようになります。

答え(N) = デカルト冪(0..1, N).filter(list ->
    (1..N).mapToInt(i -> c[i] * list[i]).sum() <= C
).mapToInt(list ->
    (1..N).mapToInt(i -> p[i] * list[i]).sum()
).max()

配列 c や p は問題から与えられる定数配列です。N や C も int 定数。

では、解法。この問題では、リストの末尾1つを定数化します。X = list[N] と置きます。すると、こう変形できます。

f1(N, X) = デカルト冪(0..1, N - 1).filter(list ->
    (1..(N - 1)).mapToInt(i -> c[i] * list[i]).sum() + c[N] * X <= C
).mapToInt(list ->
    (1..(N - 1)).mapToInt(i -> p[i] * list[i]).sum() + p[N] * X
).max()

ここで、c[N] * X も p[N] * X も定数です。filter において、C が定数なので、引き算して一つにまとめます。また、mapToInt の方は、定数の足し算を集約関数の外に出すことができます。この手順も、毎回毎回行うパターンです。この変形を行うと、以下のようになります。

f1(N, X) = デカルト冪(0..1, N - 1).filter(list ->
    (1..(N - 1)).mapToInt(i -> c[i] * list[i]).sum() <= C - c[N] * X
).mapToInt(list ->
    (1..(N - 1)).mapToInt(i -> p[i] * list[i]).sum()
).max() + p[N] * X

次に、ループ回数を一つ減らした物を考えます。上記で、リスト末尾 k 個を定数化したときは、こちらでは k - 1 個を定数化する必要あるのですが、ここでは、k = 1 だったので、一つも定数化しません。 k >= 2 の例はこの先、別な問題でやります。

答え(N - 1) = デカルト冪(0..1, N - 1).filter(list ->
    (1..(N - 1)).mapToInt(i -> c[i] * list[i]).sum() <= C
).mapToInt(list ->
    (1..(N - 1)).mapToInt(i -> p[i] * list[i]).sum()
).max()

で、この2つの擬似コードを比べると、ほとんど同じ形です。C と C - c[N] * X の違いがあるので、この部分を変数 y と置きます。

f2(N - 1, y) = デカルト冪(0..1, N - 1).filter(list ->
    (1..(N - 1)).mapToInt(i -> c[i] * list[i]).sum() <= y
).mapToInt(list ->
    (1..(N - 1)).mapToInt(i -> p[i] * list[i]).sum()
).max()

f1 の方も、C を引数に入れちゃいます。

f1(N, X, C) = デカルト冪(0..1, N - 1).filter(list ->
    (1..(N - 1)).mapToInt(i -> c[i] * list[i]).sum() <= C - c[N] * X
).mapToInt(list ->
    (1..(N - 1)).mapToInt(i -> p[i] * list[i]).sum()
).max() + p[N] * X

すると、

f1(N, X, C) = f2(N - 1, C - c[N] * X) + p[N] * X 

になります。また、答え(N - 1) = f2(N - 1, C) つまり 答え(N) = f2(N, C) です。

そして、X = list[N] は末尾1つを定数化して作った物なので、以下の等式が成立します。

答え(N) = (0..1).mapToInt(x -> f1(N, x, C)).max()

まとめると、以下の式ができました。

答え(N) = f2(N, C) = (0..1).mapToInt(x -> f1(N, x, C)).max()
f1(N, x, C) = f2(N - 1, C - c[N] * x) + p[N] * x

下の式を上の式に代入して、以下の通りです。

答え(N) = f2(N, C) = (0..1).mapToInt(x -> f2(N - 1, C - c[N] * x) + p[N] * x).max()

f2 の N が1ずつ減っていくループになっています。

ただし、ループの最後、f2(1, ?) は、省略してしまったのですが、別扱いで書いてください。最初の問題文に N = 1 を代入すると出ます。

答え(1) = デカルト冪(0..1, 1).filter(list ->
    (1..1).mapToInt(i -> c[i] * list[i]).sum() <= C
).mapToInt(list ->
    (1..1).mapToInt(i -> p[i] * list[i]).sum()
).max()

整理すると、以下のようになります。

答え(1) = デカルト冪(0..1, 1).filter(list ->
    c[1] * list[1] <= C
).mapToInt(list ->
    p[1] * list[1]
).max()

もっと整理すると、以下のようになります。-∞は詰められないパターンです。空リスト.max() == -∞ としました。

答え(1) = c[1] <= C ? p[1] : (0 <= C ? 0 : -∞)

そして、あとは、f2 の引数が同じなら、返り値は常に一緒なので、メモ化すればOKです。ボトムアップなら配列に書けば良いです。ここから更に整理したり高速化したり少々できますが枝葉末節なので省略します。

JOI 2014年予選問4

さて、2013年12月に開催された、2014年予選問4です。問題文は http://www.ioi-jp.org/joi/2013/2014-yo/2014-yo-t4/2014-yo-t4.html 。擬似コードにおこすと以下の通りです。allMatch() メソッドは全て true の時に true になるという Java 8 のメソッドです。問題文は鍵に関する部分があるのですがその部分は連続同じ人が出席する必要があるという形で整理済みです。

答え(N) = デカルト冪(0..7, N).filter(list ->
    (list[1] & 1 != 0) && 
    (2..N).allMatch(i -> list[i] & list[i - 1] != 0) &&
    (1..N).allMatch(i -> list[i] & P[i] != 0)
).mapToInt(list ->
    1
).sum()

このように、list[i] & list[i - 1] のように配列の2つの要素にアクセスしているときは、定数化すべきは 2 個になります。全く同じ手順ですすめますね。リスト末尾2つを定数化し、X1 = list[N], X2 = list[N - 1] とします。

f1(N, X1, X2) = デカルト冪(0..7, N - 2).filter(list ->
    (list[1] & 1 != 0) &&

    (2..(N - 2)).allMatch(i -> list[i] & list[i - 1] != 0) &&
    (X2 & list[N - 2] != 0) &&
    (X1 & X2 != 0) &&

    (1..(N - 2)).allMatch(i -> list[i] & P[i] != 0) && 
    (X2 & P[N - 1] != 0) &&
    (X1 & P[N] != 0)
).mapToInt(list ->
    1
).sum()

ループの1つ前にリスト末尾1つ、つまり、X2 = list[N - 1] だけを定数化した物はこのようになります。

f2(N - 1, X2) = デカルト冪(0..7, N - 2).filter(list ->
    (list[1] & 1 != 0) && 

    (2..(N - 2)).allMatch(i -> list[i] & list[i - 1] != 0) && 
    (X2 & list[N - 2] != 0) &&

    (1..(N - 2)).allMatch(i -> list[i] & P[i] != 0) && 
    (X2 & P[N - 1] != 0)
).mapToInt(list ->
    1
).sum()

記事の都合上、N を具体化していないのですが、3 とか 4 とか具体的な数字を入れて取り扱うと、より分かりやすく、簡単になります。

で、いつも通り、この2つを比較すると、(X1 & X2 != 0) と (X1 & P[N] != 0) という定数が増えていて、かつ、これらが false だと、filter のクロージャが常に false になり、全体が 0 になるので、

f1(N, X1, X2) = (X1 & X2 != 0) && (X1 & P[N] != 0) ? f2(N - 1, X2) : 0 

と分かります。

また、末尾定数化により、答えやf2は以下の形で表現できます。

答え(N) = (0..7).mapToInt(x1 -> f2(N - 1, x1)).sum()
f2(N - 1, x1) = (0..7).mapToInt(x2 -> f1(N - 1, x1, x2)).sum()

あとは、さっきの式で f1 が f2 より求まり、f1, f2, f1, f2 と行ったり来たりするループが出来上がります。そして、ループの最後は、答え(2) を整理すればOKです。加えてメモ化をします。

JOI 2013年予選問4

本当にワンパターンですが、一応軽く2012年12月の2013年予選4も触れます。問題文は http://www.ioi-jp.org/joi/2012/2013-yo/2013-yo-t4/2013-yo-t4.html 。擬似コードにおこすと以下の通りです。

答え(D) = デカルト冪(1..N, D).filter(list ->
    (1..D).allMatch(i -> A[list[i]] <= T[i] && T[i] <= B[list[i]])
).mapToInt(list ->
    (2..D).mapToInt(i-> abs(C[list[i - 1]] - C[list[i]])).sum()
).max()

今回はループ変数は D です。そして、list[i - 1] と list[i] を使ってるので、定数化は2個です。

f1(D, X1, X2) = デカルト冪(1..N, D - 2).filter(list ->
    (1..(D - 2)).allMatch(i -> A[list[i]] <= T[i] && T[i] <= B[list[i]]) &&
    A[X2] <= T[D - 1] && T[D - 1] <= B[X2] &&
    A[X1] <= T[D] && T[D] <= B[X1]
).mapToInt(list ->
    (2..(D - 2)).mapToInt(i -> abs(C[list[i - 1]] - C[list[i]])).sum() +
    abs(C[list[D - 2]] - C[X2]) +
    abs(C[X2] - C[X1])
).max()

mapToInt の中の定数 abs(C[X2] - C[X1]) は集約関数 max の外出しです。で、ループ1つ前の末尾1つだけ定数化したのは、

f2(D - 1, X2) = デカルト冪(1..N, D - 2).filter(list ->
    (1..(D - 2)).allMatch(i -> A[list[i]] <= T[i] && T[i] <= B[list[i]]) &&
    A[X2] <= T[D - 1] && T[D - 1] <= B[X2]
).mapToInt(list ->
    (2..(D - 2)).mapToInt(i -> abs(C[list[i - 1]] - C[list[i]])).sum() +
    abs(C[list[D - 2]] - C[X2])
).max()

代入すると、以下の通りです。空リスト.max() == -∞ としました。

f1(D, X1, X2) = A[X1] <= T[D] && T[D] <= B[X1] ? f2(D - 1, X2) + abs(C[X2] - C[X1]) : -∞

末尾定数化したと言うことより、

答え(D) = (1..N).mapToInt(x1 -> f2(D - 1, x1)).max()
f2(D - 1, x1) = (1..N).mapToInt(x2 -> f1(D - 1, x1, x2)).max()

と同じ話が続き、ループの最後の 答え(2) は別枠で整理したらメモ化して完成です。

2012年予選4も2011年予選4も同じ解法で解くことができます。

トラックバック - http://d.hatena.ne.jp/yukoba/20140628

2013年07月17日 QEMUでARM版Ubuntuの動作方法

QEMUARMUbuntuの動作方法

QEMUでARM版Ubuntuの動作させるとこんな感じで動きます。速度的に、2コアのノートパソコン第3世代Core i5で動かして、たぶんPentium 3くらいの感じになります。キーボードマウスもマウスホイールネットワークも問題ないです。gccapt-getインストールできます。

f:id:yukoba:20130717165636p:image

Ubuntu 側でやる作業

VMware 上の Ubuntu 12.04 で行いました。SDカードイメージダウンロードして展開しているだけです。yukoba:yukoba になっているところは適当に変えてください。

wget http://releases.linaro.org/13.06/ubuntu/vexpress/vexpress-raring_alip_20130625-379.img.gz
gunzip vexpress-raring_alip_20130625-379.img.gz

sudo mkdir /mnt/mnt
(IMG=vexpress-raring_alip_20130625-379.img ; if [ -e "$IMG" ] ; then sudo mount -o loop,offset="$(file "$IMG" | awk 'BEGIN { RS=";"; } /partition 2/ { print $7*512; }')" -t auto "$IMG" /mnt/mnt; else echo "$IMG not found"; fi )

sudo cp -vr /mnt/mnt/boot .
sudo chown -R yukoba:yukoba boot
sudo umount /mnt/mnt
mv vexpress-raring_alip_20130625-379.img boot/

Windows 側でやる作業

上記の boot フォルダを Windows 側にコピーしてください。そして、http://lassauge.free.fr/qemu/ (QEMU on Windows) から QEMU をダウンロードして、C:\Program Files\Qemu-windows-1.5.1 とかに展開します。

boot フォルダに移動して、以下のコマンドで実行できます。

"C:\Program Files\Qemu-windows-1.5.1\qemu-system-armw.exe" -kernel vmlinuz-3.10.0-1-linaro-vexpress -M vexpress-a9 -cpu cortex-a9 -serial stdio -m 1024 -initrd initrd.img-3.10.0-1-linaro-vexpress -append "root=/dev/mmcblk0p2 rw mem=1024M raid=noautodetect console=ttyAMA0,38400n8 rootwait vmalloc=256MB devtmpfs.mount=0" -sd vexpress-raring_alip_20130625-379.img

以上のやり方は、https://wiki.linaro.org/PeterMaydell/QemuVersatileExpress より修正。

トラックバック - http://d.hatena.ne.jp/yukoba/20130717

2013年02月17日 海外航空券の値段の比較

海外航空券の値段の比較

海外航空券の値段を調べてみました。東京サンフランシスコ 往復(月曜日出発、執筆時は日曜日)。

    明日or明後日 1週間後 2週間後
HIS   111,200 90,680 75,670
JTB 117,550 97,950 74,650
ANA 110,000 99,000 99,000
楽天       99,675
KAYAK 103,880
Expedia 105,000
デルタ航空 110,150 126,150 105,150
スカイゲート113,825 110,465 108,825
阪急交通 123,420 102,330
JAL 331,210 119,210
ユナイテッド航空 120,790

全て、燃油・諸税込。

Yahoo, トラベルコ, AB-ROAD はわけ分からないので除外。KAYAK は米ドルから日本円に換算(カード決済だともっと高くなるはず)。

スカイゲート, JTB 1週間後、非直行 です。

他の地域でも、おおむね、HIS が、だいたい最安です。

トラックバック - http://d.hatena.ne.jp/yukoba/20130217

2012年11月26日 JNAをAndroidで使う方法

JNA を Android で使う方法

C言語ライブラリJava から使うときに便利な https://github.com/twall/jna (JNA) を Android で使う方法のメモです。(追記:JNA 4.0.0 に合わせて大幅に書き換えました)

JNA は 4.0.0 現在、Android に対応していますが、ドキュメントがないです。3.4.0 当時、Android 対応をしようとして、中途半端になっていて、3.5.1 でその残骸が残っていましたが、4.0.0 ではちゃんと対応しています。

手順

  1. https://github.com/twall/jna/raw/master/dist/android-arm.jarダウンロードして、解凍して、libjnidispatch.so を取り出します。
  2. libjnidispatch.so を自分の Android アプリプロジェクトフォルダの libs/armeabi に置きます。

注意点

注意点は、下記のように Structure にはフィールドの順番を指定しないといけないです。(追記:昔のJNAはこれが必須ではなかったのですが、JNA 3.5.0 からそもそも必須です。)

@Override
protected List getFieldOrder() {
    return Arrays.asList("x", "y");
}

JP tanaJP tana 2013/05/17 17:27 有難うございます。大変、参考になりました。

2012年10月12日 AndroidでC言語のライブラリのビルド方法のまとめ

AndroidC言語ライブラリビルド方法のまとめ

Android は Linux の一種でもあり、ARM で動く Linux 向けのC言語で書かれたライブラリの多くが動きます。(多少違うので、動かない場合もあり)。ただし、ビルド方法が暗黙の了解事項になってたりして、Android NDK にちゃんと書かれていなかったりするので、ここにまとめます!

以下、架空の libhoge をビルドすることとします。

ビルド対象は一般的に静的ライブラリ (.a) ファイルにしておくと吉です。自分で使う際は、自分の Android.mk に以下の物を追加します。

  • LOCAL_CFLAGS に -Ihoge-1.0/include みたいのを追加
  • LOCAL_LDLIBS に -Lhoge-1.0-android-build/$(TARGET_ARCH_ABI) と -l hoge を追加

ライブラリをビルドしてできた libhoge.a はこのフォルダに置いておきます。

  • hoge-1.0-android-build/armeabi
  • hoge-1.0-android-build/armeabi-v7a
  • hoge-1.0-android-build/x86

必要な物:

手順は以下の順番で検討していくと良いです。

1.Android でのビルド方法がライブラリに明示されている場合

当然、このケースは、ライブラリに従うとビルドできるはずです。

2.Android.mk だけが用意されている場合

export NDK_ROOT=~/android-ndk-r9c
cd ~/hoge-1.0
$NDK_ROOT/ndk-build NDK_PROJECT_PATH=. APP_BUILD_SCRIPT=./Android.mk APP_ABI=armeabi obj/local/armeabi/libhoge.a
$NDK_ROOT/ndk-build NDK_PROJECT_PATH=. APP_BUILD_SCRIPT=./Android.mk APP_ABI=armeabi-v7a obj/local/armeabi-v7a/libhoge.a
$NDK_ROOT/ndk-build NDK_PROJECT_PATH=. APP_BUILD_SCRIPT=./Android.mk APP_ABI=x86 obj/local/x86/libhoge.a

obj/local にできたやつがコンパイル結果です。

3.なにもなくて、gcc の標準のビルドスタイルの場合

./configure → make → make install のパターンの場合です。

まず、スタンドアローンツールチェインをインストールする必要があります。Android NDK の docs/STANDALONE-TOOLCHAIN.html に説明が書いてあります。以下、android-9 にしたので、Android 2.3 用です。

export NDK_ROOT=~/android-ndk-r9c
$NDK_ROOT/build/tools/make-standalone-toolchain.sh --platform=android-9 --toolchain=arm-linux-androideabi-4.6 --install-dir=$HOME/android-toolchain-arm-4.6
$NDK_ROOT/build/tools/make-standalone-toolchain.sh --platform=android-9 --toolchain=x86-4.6 --install-dir=$HOME/android-toolchain-x86-4.6

さて、ビルド方法。以下、configure が置いてある元のソースフォルダを汚さないように別のフォルダを作ってビルドします。ソースは ~/hoge-1.0 とかに展開してあるとします。

export ANDROID_TOOLCHAIN=~/android-toolchain-arm-4.6
export BUILD_HOST=arm-linux-androideabi

export PATH=$ANDROID_TOOLCHAIN/bin:$PATH
export CC=$BUILD_HOST-gcc
export CFLAGS="-mthumb -march=armv7-a -mfloat-abi=softfp -I$ANDROID_TOOLCHAIN/include"
export LDFLAGS="-Wl,--fix-cortex-a8"

mkdir ~/hoge-1.0-android
cd ~/hoge-1.0-android
../hoge-1.0/configure --host=$BUILD_HOST --prefix=$PWD/build-result
make -j 4
make install

すると、~/hoge-1.0-android/build-result にビルド結果が作られるので、lib/libhoge.a を探してください。

上記の方法は、armeabi-v7a の方で Cortex-A シリーズしか動かなく、このようにすると、armeabi になり、全ての Android で動くようになります。

export CFLAGS="-mthumb -march=armv5te -I$ANDROID_TOOLCHAIN/include"

また、NEON (Advanced SIMD) を有効にするには、このようにします。NVIDIA Tegra 2 で動かなくなります。

export CFLAGS="-mthumb -march=armv7-a -mfloat-abi=softfp -mfpu=neon -I$ANDROID_TOOLCHAIN/include"

ちなみに、configure の --host、arm-linux-androideabi ($BUILD_HOST) ですが、arm-linux にして Android であることを隠してしまうとうまくいく場合もあったりなかったりします。Android NDK r8b 現在、Elf32_auxv_t が未定義だったり、微妙に Android は Linux と差があるんですが…

次に Android x86。

export ANDROID_TOOLCHAIN=~/android-toolchain-x86-4.6
export BUILD_HOST=i686-linux-android

export PATH=$ANDROID_TOOLCHAIN/bin:$PATH
export CC=$BUILD_HOST-gcc
export CFLAGS="-I$ANDROID_TOOLCHAIN/include"
export LDFLAGS=""

mkdir ~/hoge-1.0-android-x86
cd ~/hoge-1.0-android-x86
../hoge-1.0/configure --host=$BUILD_HOST --prefix=$PWD/build-result
make -j 4
make install

同じく、~/hoge-1.0-android-x86/build-result にビルド結果が作られるので、lib/libhoge.a を探してください。

2012年09月30日 GMOクラウド Public APIのJavaクライアント

GMOクラウド Public APIJavaクライアント

GMOクラウド Public APIのJavaクライアントを作りました

https://github.com/yukoba/GmoCloudAPI

使い方

GmoCloud gmoCloud = new GmoCloud(ACCESS_KEY_ID, SECRET_KEY, "jp002");
String json = gmoCloud.listNodesJson();
トラックバック - http://d.hatena.ne.jp/yukoba/20120930

2012年04月11日 AndroidでPOCO C++ Librariesの実行方法

AndroidでPOCO C++ Librariesの実行方法

http://pocoproject.org/ ですが、1.4.2 から Android 対応しているのですが、マニュアルドキュメント不足でいまいちわからなかったので、ここにメモしておきます。

ライブラリ自体のコンパイル方法

http://pocoproject.org/docs/99300-AndroidPlatformNotes.html どおりです。Ubuntu 12.04 (x64) でも MinGW でもどちらでもコンパイルできました。Ubuntu x64 の場合aptitude install ia32 する必要があります。

こんな感じで、my-android-toolchain を作って、

export NDK=$HOME/android-ndk-r7c
$NDK/build/tools/make-standalone-toolchain.sh --platform=android-8 --install-dir=$HOME/my-android-toolchain
export PATH=$HOME/my-android-toolchain/bin:$PATH

こんな感じでコンパイルできます。

cd poco-1.4.3p1
./configure --config=Android --no-samples --no-tests
make -s -j4
make -s -j4 ANDROID_ABI=armeabi-v7a

そして、--platform=android-8 を --arch=x86 に変え、ANDROID_ABI=x86 にすると、x86 Android でも動作します。エミュレータで高速に動作するようになります。

ndk-build との併用方法

この部分がドキュメント不足でした。

まず、Application.mk に

APP_STL      := gnustl_static

gnustl_static でも gnustl_shared でもどちらでも動作しますが、gnustl_shared の場合、Java 側から、System.loadLibrary("gnustl_shared"); する必要があります。

Android.mk に

LOCAL_CPP_FEATURES += exceptions rtti

を追加し、更に、

  • LOCAL_CFLAGS には -Ipoco-1.4.3p1/Foundation/include -Ipoco-1.4.3p1/Net/include -Ipoco-1.4.3p1/Xml/include -Ipoco-1.4.3p1/Util/include を追加します。
  • LOCAL_LDLIBS の先頭に、-Lpoco-1.4.3p1/lib/Android/armeabi-v7a -lPocoNet -lPocoXml -lPocoUtil -lPocoFoundation を追加します。
  • LOCAL_STATIC_LIBRARIES に、libgnustl_static を追加します。

poco-1.4.3p1 へのパスは適切に変えてください。exceptions rtti は動作させるのに必須です。それ故、APP_STL は gnustl を使わないとダメです。

NativeActivity を使っているのですが、AndroidManifest.xml は例えば、こんな感じにします。

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="com.example.hoge"
      android:versionCode="1"
      android:versionName="1.0">

    <uses-permission android:name="android.permission.INTERNET" />
    <uses-sdk android:minSdkVersion="10" />

    <application android:label="@string/app_name" android:hasCode="true" android:debuggable="true">
        <activity android:name="android.app.NativeActivity" android:label="@string/app_name">
            <meta-data android:name="android.app.lib_name" android:value="hoge" />
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>
</manifest> 

HTTP 通信とか、StringTokenizer とかがちゃんと動作するところまで確認しました。

ただし、POCO の Thread.start() が Android NDK r7c + POCO 1.4.3p1 の組み合わせでは正常に動作しませんでした。原因不明。自分で Pthread を使う分には問題無いです。

(追記)最初にこのブログを書いた際、大幅に間違いを含んでいたので色々修正しました。

トラックバック - http://d.hatena.ne.jp/yukoba/20120411