1# hobu's latest results on his 2006-era machine
2
3# Stream load:
4# 293710.04 usec/pass
5#
6# One-at-a-time load:
7# 527883.95 usec/pass
8#
9#
10# 30000 points
11# Query box:  (1240000, 1010000, 1400000, 1390000)
12#
13#
14# Brute Force:
15# 46 hits
16# 13533.60 usec/pass
17#
18# Memory-based Rtree Intersection:
19# 46 hits
20# 7516.19 usec/pass
21#
22# Disk-based Rtree Intersection:
23# 46 hits
24# 7543.00 usec/pass
25#
26# Disk-based Rtree Intersection without Item() wrapper (objects='raw'):
27# 46 raw hits
28# 347.60 usec/pass
29
30import random
31import timeit
32
33try:
34    import pkg_resources
35    pkg_resources.require('Rtree')
36except:
37    pass
38
39from rtree import Rtree as _Rtree
40
41TEST_TIMES = 20
42
43
44# a very basic Geometry
45class Point(object):
46    def __init__(self, x, y):
47        self.x = x
48        self.y = y
49
50# Scatter points randomly in a 1x1 box
51
52
53class Rtree(_Rtree):
54    pickle_protocol = -1
55
56bounds = (0, 0, 6000000, 6000000)
57count = 30000
58points = []
59
60insert_object = None
61insert_object = {
62    'a': list(range(100)),
63    'b': 10,
64    'c': object(),
65    'd': dict(x=1),
66    'e': Point(2, 3),
67}
68
69index = Rtree()
70disk_index = Rtree('test', overwrite=1)
71
72coordinates = []
73for i in range(count):
74    x = random.randrange(bounds[0], bounds[2]) + random.random()
75    y = random.randrange(bounds[1], bounds[3]) + random.random()
76    point = Point(x, y)
77    points.append(point)
78
79    index.add(i, (x, y), insert_object)
80    disk_index.add(i, (x, y), insert_object)
81    coordinates.append((i, (x, y, x, y), insert_object))
82
83s = """
84bulk = Rtree(coordinates[:2000])
85"""
86t = timeit.Timer(
87    stmt=s, setup='from __main__ import coordinates, Rtree, insert_object')
88print("\nStream load:")
89print("%.2f usec/pass" % (1000000 * t.timeit(number=TEST_TIMES)/TEST_TIMES))
90
91s = """
92idx = Rtree()
93i = 0
94for point in points[:2000]:
95    idx.add(i, (point.x, point.y), insert_object)
96    i+=1
97"""
98t = timeit.Timer(
99    stmt=s, setup='from __main__ import points, Rtree, insert_object')
100print("\nOne-at-a-time load:")
101print("%.2f usec/pass\n\n"
102      % (1000000 * t.timeit(number=TEST_TIMES)/TEST_TIMES))
103
104
105bbox = (1240000, 1010000, 1400000, 1390000)
106print(count, "points")
107print("Query box: ", bbox)
108print("")
109
110# Brute force all points within a 0.1x0.1 box
111s = """
112hits = [p for p in points
113        if p.x >= bbox[0] and p.x <= bbox[2]
114        and p.y >= bbox[1] and p.y <= bbox[3]]
115"""
116t = timeit.Timer(stmt=s, setup='from __main__ import points, bbox')
117print("\nBrute Force:")
118print(len([p for p in points
119           if p.x >= bbox[0] and p.x <= bbox[2] and p.y >= bbox[1]
120           and p.y <= bbox[3]]), "hits")
121print("%.2f usec/pass" % (1000000 * t.timeit(number=TEST_TIMES)/TEST_TIMES))
122
123# 0.1x0.1 box using intersection
124
125if insert_object is None:
126    s = """
127    hits = [points[id] for id in index.intersection(bbox)]
128    """
129else:
130    s = """
131    hits = [p.object for p in index.intersection(bbox, objects=insert_object)]
132    """
133
134t = timeit.Timer(
135    stmt=s, setup='from __main__ import points, index, bbox, insert_object')
136print("\nMemory-based Rtree Intersection:")
137print(len([points[id] for id in index.intersection(bbox)]), "hits")
138print("%.2f usec/pass" % (1000000 * t.timeit(number=100)/100))
139
140
141# run same test on disk_index.
142s = s.replace("index.", "disk_index.")
143
144t = timeit.Timer(
145    stmt=s,
146    setup='from __main__ import points, disk_index, bbox, insert_object')
147print("\nDisk-based Rtree Intersection:")
148hits = list(disk_index.intersection(bbox))
149print(len(hits), "hits")
150print("%.2f usec/pass" % (1000000 * t.timeit(number=TEST_TIMES)/TEST_TIMES))
151
152
153if insert_object:
154    s = """
155        hits = disk_index.intersection(bbox, objects="raw")
156        """
157    t = timeit.Timer(
158        stmt=s,
159        setup='from __main__ import points, disk_index, bbox, insert_object')
160    print("\nDisk-based Rtree Intersection "
161          "without Item() wrapper (objects='raw'):")
162    result = list(disk_index.intersection(bbox, objects="raw"))
163    print(len(result), "raw hits")
164    print("%.2f usec/pass"
165          % (1000000 * t.timeit(number=TEST_TIMES)/TEST_TIMES))
166    assert 'a' in result[0], result[0]
167
168import os
169try:
170    os.remove('test.dat')
171    os.remove('test.idx')
172except:
173    pass
174