prog/python/rtree

pythonでRTreeを使う。 †

pythonで、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にインストール †

↑

spatialindex-1.4.0のインストール †

spatialindexから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の設定 †

/etc/ld.conf.d以下に以下のように設定。
```
/usr/local/lib
```

↑

easy_installでRTreeのインストール †

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のベンチマーク †

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の頻繁なアップデートが不可欠その場合の速度を量って見たいところ。