source: TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/tests/benchmarks.py @ 2194

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/tests/benchmarks.py@2194
Revision 2194, 2.1 KB checked in by lawrence, 13 years ago (diff)

Adding various specs and 3rd party code of interest for the CSML
services development.

Line 
1
2import random
3import timeit
4
5try:
6    import pkg_resources
7    pkg_resources.require('Quadtree')
8except:
9    pass
10
11from quadtree import Quadtree
12
13# a very basic Geometry
14class Point(object):
15    def __init__(self, x, y):
16        self.x = x
17        self.y = y
18
19# Scatter points randomly in a 1x1 box
20count = 50000
21index_extent = (-180, -90, 180, 90)
22points = []
23index = Quadtree(index_extent)
24for i in xrange(count):
25    x = 360.0*(random.random()-0.5)
26    y = 180.0*(random.random()-0.5)
27    points.append(Point(x, y))
28    index.add(i, (x, y))
29
30bbox = (0.0, 50.0, 5.0, 55.0)
31
32print count, "points"
33print "Index extent: ", index_extent
34print "Query box: ", bbox
35print ""
36
37# Brute force all points within a 0.1x0.1 box
38s = """
39hits = [p for p in points if p.x >= bbox[0] and p.x <= bbox[2] and p.y >= bbox[1] and p.y <= bbox[3]]
40"""
41t = timeit.Timer(stmt=s, setup='from __main__ import points, bbox')
42print "\nBrute Force:"
43print len([p for p in points if p.x >= bbox[0] and p.x <= bbox[2] and p.y >= bbox[1] and p.y <= bbox[3]]), "hits"
44print "%.2f usec/pass" % (1000000 * t.timeit(number=100)/100)
45
46# 0.1x0.1 box using likely_intersection
47
48s = """
49hits = [points[id] for id in index.likely_intersection(bbox)]
50"""
51t = timeit.Timer(stmt=s, setup='from __main__ import points, index, bbox')
52print "\nLikely Intersection:"
53print len([points[id] for id in index.likely_intersection(bbox)]), "hits"
54print "%.2f usec/pass" % (1000000 * t.timeit(number=100)/100)
55
56# 0.1x0.1 box using likely_intersection, and a final brute force pass
57# over hits to eliminate false positives.
58
59s = """
60likelies = [points[id] for id in index.likely_intersection(bbox)]
61hits = [p for p in likelies if p.x >= bbox[0] and p.x <= bbox[2] and p.y >= bbox[1] and p.y <= bbox[3]]
62"""
63t = timeit.Timer(stmt=s, setup='from __main__ import points, index, bbox')
64print "\nLikely Intersection with false positive mop-up:"
65likelies = [points[id] for id in index.likely_intersection(bbox)]
66print len([p for p in likelies if p.x >= bbox[0] and p.x <= bbox[2] and p.y >= bbox[1] and p.y <= bbox[3]]), "hits"
67print "%.2f usec/pass" % (1000000 * t.timeit(number=100)/100)
68
69
Note: See TracBrowser for help on using the repository browser.