[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [pygame] fast sqrt? and profiling
The easy was is to make boxes and only look in the boxes that are near
the unit you are testing. Here is some code that does that. It is for
stars that don't move so you will need to optimize for moving objects
but it does give you the idea.
Also the question who is closer is different from how far is B1 from B2
Distance = square root (B1-B2)
But who is closer can be found by b1-b2
import random
import math
import time
from time import time
def gamma(n):
if n < 1: return 0
if n == 1: return 1
if n == 1.5: return math.sqrt(math.pi) / 2
return (n-1) * gamma(n-1)
def sphere_multiplier(n):
return math.pow(math.pi, n/2.0) / gamma(n/2.0 + 1)
class Star:
"Object representing a star"
def __init__(self):
self.coords = []
for i in range(dimensions):
self.coords.append(random.uniform(0, universe_size))
def wrap_diff(self, c1, c2):
return min(abs(c1 - c2), universe_size - abs(c1 - c2))
def get_distance(self, coords):
return math.sqrt(sum([ math.pow(self.wrap_diff(x, y), 2)
for x,y in zip(self.coords, coords)]))
class Grid:
"A spatial grid to make it faster to find nearby objects"
def __init__(self, step):
self.step = step
self.cells = {}
def make_key(self, coords):
return tuple([math.floor(x / self.step) for x in coords])
def add(self, obj):
key = self.make_key(obj.coords)
if self.cells.has_key(key):
self.cells[key].append(obj)
else:
self.cells[key] = [obj]
def remove(self, obj):
key = self.make_key(obj.coords)
self.cells[key].remove(obj)
if len(self.cells[key]) == 0:
del self.cells[key]
def _print(self):
for key in self.cells.keys():
print "Cell", [ x * self.step for x in key ]
for obj in self.cells[key]:
print " ", obj.coords
def is_empty(self):
return len(self.cells) == 0
def pop(self):
for key in self.cells.iterkeys():
cell = self.cells[key]
break
obj = cell[0]
self.remove(obj)
return obj
def get_near(self, centre):
keys = [ self.make_key(centre) ]
for i in xrange(0,dimensions):
new_keys = keys[:]
for key in keys:
new_key = list(key)
new_key[i] = key[i] - 1;
new_keys.append(tuple(new_key))
new_key = list(key)
new_key[i] = key[i] + 1;
new_keys.append(tuple(new_key))
keys = new_keys
neighbours = []
for key in keys:
if not self.cells.has_key(key): continue
neighbours += self.cells[key]
neighbours = [ star for star in neighbours if
star.get_distance(centre) <= self.step ]
return neighbours
def pop_near(self, centre):
neighbours = self.get_near(centre)
for star in neighbours: self.remove(star)
return neighbours
t1=time()
random.seed(3245)
#density, universe_size, dimensions = 0.33, 250, 2
density, universe_size, dimensions = 0.02, 80, 3
#density, universe_size, dimensions = 0.025, 30, 4
jump = 2
dist = jump + 0.5 # Make comparable to hex grids, which allow jumps
from center to outer edge
print "Average stars within range", sphere_multiplier(dimensions) *
math.pow(dist, dimensions) * density
# Find the actual number of stars (Poisson distribution)
num_stars = 0
vol_remaining = pow(universe_size, dimensions)
star_vol = random.expovariate(density) # Each item has exponential distribution
while vol_remaining >= star_vol:
num_stars += 1
vol_remaining -= star_vol
star_vol = random.expovariate(density)
# Generate random star positions
stars = []
for i in xrange(num_stars): stars.append(Star())
print "Generated", num_stars, "stars in universe size", universe_size,
"dimension", dimensions
# Make a grid to ease searching for nearest stars
grid = Grid(dist)
for star in stars: grid.add(star)
# Build up groups of stars reachable from each other by repeated jumps
groups = []
while not grid.is_empty():
seed = grid.pop()
# Find stars reachable from the seed, removing them from the grid
interior_stars = set()
border_stars = set([seed])
while len(border_stars) > 0:
origin = border_stars.pop()
interior_stars.add(origin)
border_stars |= set(grid.pop_near(origin.coords))
groups.append(interior_stars)
print "Found", len(groups), "groups of stars connected by jump", jump
reachability = sum([ len(group) * (len(group) - 1.0) for group in groups ])
print "Average reachability was", reachability / (num_stars * (num_stars - 1))
print "Largest group had", max([len(group) for group in groups]), "stars"
print "Run time:",time()-t1
On 1/21/09, Patrick Mullen <saluk64007@xxxxxxxxx> wrote:
> On Tue, Jan 20, 2009 at 10:21 PM, René Dudfield <renesd@xxxxxxxxx> wrote:
>> I forgot to mention this quadtree code too:
>> http://www.pygame.org/wiki/QuadTree
>>
>>
>> cu,
>>
>>
>> On Wed, Jan 21, 2009 at 5:06 PM, René Dudfield <renesd@xxxxxxxxx> wrote:
>>> hi,
>>>
>>> you'll want to use a spacial hash.
>>>
>>> Like this quadtree for example:
>>> http://www.pygame.org/project/752/
>>>
>>> cu!
>>>
>
>
> Those suggestions are good. Also, even in the original case, you
> probably don't need a squareroot at all. You can use the manhattan
> distance instead for relative distances. But even that will not scale
> well enough if your collection gets big enough. The real problem is
> comparing everything to everything else, which some kind of
> partitioning will help you avoid.
>
--
Douglas E Knapp
Amazon Gift Cards; let them choose!!
http://www.amazon.com/gp/product/B001078FFE?ie=UTF8&tag=seattlebujinkand&linkCode=as2&camp=1789&creative=9325&creativeASIN=B001078FFE