* pythonで[[RTree:http://pypi.python.org/pypi/Rtree/]]を使う。 [#f7e78721]

pythonで、[[RTree:http://pypi.python.org/pypi/Rtree/]]を使う。主なたとえば、ある座標内にいるユーザーを、調べるとか、スグ近くにいるユーザーを調べる等の使い方をする。MMOで言えば、近くのささやくとか、周りに人に何かを言うとかの判定に使う。

使い方は以下のようになる。

 >>> from rtree import Rtree
 >>> idx = Rtree()
 >>> idx.add(id=id, bounds=(left, bottom, right, top))
 >>> [n for n in idx.intersection((left, bottom, right, top))]
 [id]

 left,bottom,right,top内にいるIDを返す。

* ubuntu9.10にインストール [#z87ac44c]
**spatialindex-1.4.0のインストール [#r0e1ed3f]

[[spatialindex:http://trac.gispython.org/spatialindex/wiki/Releases]]からspatialindex-1.4.0.tar.gzをダウンロード

ubuntuの場合は、g++等を入れるためには、
 sudo aptitude install build-essencial
でg++,make等をインストール。

ダウンロード後、
 ./configure;make;sudo make install
でインストールを行う。

makeで,
 Exhaustive.cc: In function ‘int main(int, char**)’:
 Exhaustive.cc:111: error: ‘uint32_t’ was not declared in this scope
 Exhaustive.cc:111: error: expected ‘;’ before ‘queryType’
 Exhaustive.cc:113: error: ‘queryType’ was not declared in this scope
 Exhaustive.cc:114: error: ‘queryType’ was not declared in this scope
 Exhaustive.cc:130: error: expected ‘;’ before ‘op’
 Exhaustive.cc:135: error: ‘op’ was not declared in this scope
のようなエラーが出る場合は、インクルードすべきライブラリが足りてないので、<stdint.h>ライブラリを追加する(svnのtrunkでは治っているようです)。
./spatialindex-1.4.0/regressiontest/mvrtree/Exhaustive.ccの行頭で、

 #include <assert.h>
 #include <iostream>
 #include <fstream>
 #include <map>
 #include <queue>
 #include <cmath>
 #include <cstring>
 #include <limits>
 #include <stdint.h> <-このstdint.hをインクルードする。
そうするとmakeが通るようになる。sudo make insttallで/usr/local/libに以下のライブラリが出来る。
 shibacow@ubuntu:~$ ls /usr/local/lib/
 libspatialindex.a   libspatialindex.so    libspatialindex.so.1.0.0
 libspatialindex.la  libspatialindex.so.1  python2.6

** LDCONFIGの設定 [#sb6733ec]
+ /etc/ld.conf.d以下に以下のように設定。
 /usr/local/lib
** easy_installでRTreeのインストール [#p660fc4f]
easy_installのインストール
 sudo apt-get install python-setuptools
その後、
 #easy_instlal Rtree
でRtreeのインストールを行う。
しかし、そのままでは、
 python 
 import rtree
でlibsidx.soが無いと言われる。そのため、再び、ldconfigで動的リンクを通す。
 /etc/ld.so.conf.d/librtree.conf
 ::::::::::::::
 # rtree default configuration
 /usr/local/lib/python2.6/dist-packages/Rtree-0.5.0-py2.6-linux-i686.egg
と書いて、その後、sudo ldconfigを実行。
Rtree用に、libsidx.soへのPathを通す。
そうすると、
 shibacow@ubuntu:~/pkg/Rtree-0.5.0/tests$ python
 Python 2.6.4rc2 (r264rc2:75497, Oct 20 2009, 02:55:11)
 [GCC 4.4.1] on linux2
 Type "help", "copyright", "credits" or "license" for more information.
 >>> from rtree import Rtree
が通るようになる。

**RTreeのベンチマーク [#tb478b22]
[[Rtree:http://pypi.python.org/pypi/Rtree/]]のサイトから、Rtree-0.5.0.tar.gzをダウンロード。Rtree-0.5.0/tests以下に、benchmark.pyがあるので試す。

 shibacow@ubuntu:~/pkg/Rtree-0.5.0/tests$ python benchmarks.py
 50000 points box(0,0,6000000,6000000)
 Query box:  (240000, 130000, 400000, 350000)
  
 Brute Force:
 469 hits
 19177.70 usec/pass(19ms)
 
 Memory-based Rtree Intersection:
 469 hits
 663.52 usec/pass(0.66ms)
 
 Disk-based Rtree Intersection:
 469 hits
 713.57 usec/pass(0.71ms)

Rtreeを使わず、配列をなめる方式だと、19177マイクロ秒、RTreeをOnMemoryで使うと、663マイクロ秒。19177/663は約28。つまり、Rtreeを使うと、Rtreeを使わない場合に比べて、28倍程度早い。

MMOとかで使う場合、プレイヤーが良く動くので、pointの頻繁なアップデートが不可欠その場合の速度を量って見たいところ。
トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS