QuadTreeと最大余空間とOpenLayers3メモ

ご存知の通りQuadTreeはただの4分木だが、どういうわけか私のまわりでは「効率が悪い方の空間木」という不名誉な語られ方をすることが多い(効率が良い方の空間木はR-Tree)。効率が悪いのは探索木としてQuadTreeを使おうとするからであって、QuadTreeの使い方は探索木以外にもある。その例として「最大余空間を得る」というものがある。

「最大余空間」というのは私の造語で、意味は「確実に中身が存在しないことが判明している空間の中でも最大のもの」である。たぶん私以外には誰も使ってないと思うし、ひょっとしたらアカデミックな分野にはこれと同値な別の単語があるのかもしれない。

例えば「地球上に存在する日本語の列車駅」のインデックスを作るとする。(私の知っている限り)日本語の列車駅は南半球には存在しないので、例えばGoogle Mapsなどを利用する「列車駅の位置をマーカーで表示する」ようなアプリを作った際、アプリの地図領域内に南半球のエリアしかない状態であれば、(日本語の列車駅は確実に存在しないので)そもそも駅の位置などをサーバにfetchする必要が無い。地図上において南半球エリアは極めて広大な領域だが、これが広ズームのタイル1枚でマスキングすることによって、サーバ負荷を低減することができる。

Chrome上のJavaScript処理系でマルチコア+αの処理能力を生かす手法に対する私の思い込み

註: 以下の内容は、あくまで私の思い込みである。間違っていても責任は取れない。気が向いたら加筆する。

Google Chromeやnode.jsの処理系は、単純なwhile(1)などの重い処理を書いても、CPUが1個100%になるだけである。昨今の計算機には複数のCPUが搭載されており、環境によってはGPUなども搭載されているだろうが、古風なJavaScriptではCPUコアを1つまでしか使用できない。コアを8基搭載した計算機でも、Webブラウザ上ではその12.5%までしか使用できないわけである。

尤もマルチスレッドに代表される並列処理は、シングルスレッドの場合と比較して難易度が圧倒的に高いため、下手に口を用意しない方が余計な混乱を避けられるので良かったのかもしれない。しかし、今後は単位CPUあたりの処理能力の向上はあまり見込めない以上、よりリッチなWebアプリを作成するには、マルチコア対応は避けては通れぬ道となるであろう。

実は現時点で既に、Webブラウザ上で並列処理を行う手法が、何点か存在する。それぞれについて解説する。

  1. Web Workers
  2. WebGLによるGPGPU
  3. WebCL

Web Workers

http://dev.w3.org/html5/workers/

JavaScriptで記述した処理を並列処理したい場合に使用する。並列処理したい内容を別の.jsファイルに記述して、オリジナルのjsファイルから呼び出す。

WebGLによるGPGPU

WebGLOpenGLWebブラウザ版である。OpenGLGPGPUできるのであれば、WebGLでもできる。

有名なthree.jsによるデモ: http://threejs.org/examples/#webgl_gpgpu_birds

WebCL

OpenGLWebブラウザ版がWebGLであったように、OpenCLWebブラウザ版がWebCLである。

2014年12月現在、WebCLがデフォルトで動く環境は無い。パンピー向けのサービスで使用するべきではない。

OpenLayers3におけるタイルの原点の位置について備忘録

(これは2013年12月15日時点での情報です。)

OpenLayers3は既存のOpenLayersフルスクラッチで書き直したもので、OpenStreetMapやBing mapsなどのタイルを並べてGoogle MapsのようなUXを実現する。

ユーザが地図をドラッグすると、表示位置がスクロールするたびにOpenLayers3は「現在必要なタイルの一覧」を計算し、それらをOSMなどの情報源から取得して並べる処理を行う。

OSMとBing mapsではタイルを要求する際のURLが異なるが、利用者がその差異を気にせずサービスを利用できるのは、OSMが内部で使用しているタイル座標をOSMやBing Mapsに適切に変換する関数が用意されているからである。OpenLayers3はこれを実現するために、内部での処理には汎用的な形式でタイルの座標を保持している。

内部専用タイル座標は普段目にすることは無いが、OpenLayers3はデバッグ用にタイル座標可視化用タイルを用意している。以下のURLは、デバッグ用タイルを使用したデモである。
http://ol3js.org/en/master/examples/canvas-tiles.html

最初に表示される「10/511/-341」は、z座標(奥行き=ズームレベル)が10、x座標(経度)が511、y座標(緯度)が-341であることを示している。

x座標の511が「左から511番目のタイル」という意味であり、y座標の-341が「下から-341番目のタイル」という意味であることは、上記デモサイトからおよそ推測できる。また、ズームレベルを1減らす(1段階広域表示にする)と10/511/-341のタイルは9/255/-171の右上タイルに含まれること、255は511のおよそ半分、-171は-341のおよそ半分であることから、ズームレベルが1増えるとx座標・y座標が倍ずつ増えていくことも推測できる。

このことから、地図上のどこかに、「どれだけズームレベルを変化させてもx座標・y座標が変化しない点がある」のではないかと予測される。それは以下の図の点である。

この地点は、要するに北極点(ただし経度はグリニッジ天文台の正反対)である。

注目するべきはy座標である。実際に地図が描かれているy座標は0ではなく-1である。そしてy座標はズームレベルが1増えると最低でも2倍に増える。つまり、地球上のどの地点においてもy座標は負の値なのである。

また、この地点の経度はグリニッジ天文台の正反対である。したがって、グリニッジ天文台の経度を原点とするタイル座標系をOpenLayers3で使用する場合、適切な変換が必要である。

OpenIndianaでMySQLのデータ格納ディレクトリを変更する

度々やってるのでメモ。

ibdataとかib_logfile0/1とかを置くディレクトリを/to/this/pathに設定したい場合

# svcadm disable mysql
# svccfg export application/database/mysql > mysql.tmp.xml
# vi mysql.tmp.xml



  
:
        
         # この行を
         # こんな感じに変更
        
:
  

# svccfg import mysql.tmp.xml
# svcadm enable mysql

Apacheモジュールを作るなら

mod_example.cのソースコードを読みましょう。

mod_example.cはApacheソースコードの中にありまして、中身はApacheモジュール開発のチュートリアルと言うべきソースコードです。そんじゃそこらの解説書(私のつたない日本語で書かれた解説も含む)なんかより、よっぽど正確かつ有用かつ明瞭です。

Apacheモジュールでやりたいことは、だいたい、このソースコードをコピペすればできます。解説は英語で書かれていますが、まぁ、技術者たるもの英語くらいできて当然なので問題ないでしょう。

「.soファイルが見つからないよ」と言われたら

作ったApacheモジュールをインストールしてApacheを再起動しようとしたら、Apacheモジュールであるところのsoファイルの中で参照しているlibmarisa.so (marisa-trieを-fPIC付きでコンパイルした結果)が見つからないと言われてしまった。/etc/ld.so.cacheにlibmarisa.soの記述が無いのが原因である。こんな時は、以下の手段で認識させる。

1. marisaのディレクトリにて $ make install
2. libmarisa.so.0が/lib とか /usr/lib とか /usr/local/lib に存在することを確認する (どこにあればいいのかって? /etc/ld.so.confに書いてあるパスならどれでもOKだよ〜ん)
3. # /sbin/ldconfig
4. # /sbin/ldconfig -p で、libmarisa.soがリストに存在することを確認する

既存のライブラリを-fPICつけてコンパイルする方法

オープンソースのライブラリは大体automakeの各種ファイルが付属しているが、それらを使って./configure→makeしてもlibxxx.aとかlibxxx.soまでしか作らない。悲しいことに、Apache moduleに組み込もうと思ってlibxxx.aやlibxxx.soを渡しても、apxs(apxs2)は文句を垂れる。なぜなら、Apache moduleは-fPICオプションをつけてコンパイルしたlibxxx.laしか受け付けておらず(参考 : http://httpd.apache.org/docs/2.0/programs/apxs.html)、公開されているライブラリほぼ確実に-fPICオプションなんかつけていないからである。

以下の方法でlibxxx.laを作れば宜しい。

1. libtool-devをインストール
2. ライブラリのconfigure.acを軽く見渡して、「AC_PROG_...」と書かれた行がたくさんあるブロックに

AC_PROG_LIBTOOL

と追記 (AC_PROG_LIBTOOLがDeprecatedと言われたら、代わりに「LT_INIT」と追記)
3. /usr/share/libtool/ 以下からconfig.sub, config.guess, ltmain.shをln-s
4. Makefile.amに

lib_LTLIBRARIES=libxxx.la
libxxx_la_SOURCES=xxx.c yyy.c

と追記 (ただし.aと.laは同時にMakeできないので、Makefile.amに.aのルール(lib_LIBRARIES=libxxx.a)が記述されている場合は消す)
5. ./configure
6. make