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