An efficient method for determining location on a grid (array)
I am representing a grid with a 2D list box in python. I would like to select point (x, y) in the list and locate it ... right edge, top left corner, somewhere in the middle ...
I am currently checking like this:
# left column, not a corner
if x == 0 and y != 0 and y != self.dim_y - 1:
pass
# right column, not a corner
elif x == self.dim_x - 1 and y != 0 and y != self.dim_y - 1:
pass
# top row, not a corner
elif y == 0 and x != 0 and x != self.dim_x - 1:
pass
# bottom row, not a corner
elif y == self.dim_y - 1 and x != 0 and x != self.dim_x - 1:
pass
# top left corner
elif x == 0 and y == 0:
pass
# top right corner
elif x == self.dim_x - 1 and y == 0:
pass
# bottom left corner
elif x == 0 and y == self.dim_y - 1:
pass
# bottom right corner
elif x == self.dim_x - 1 and y == self.dim_y - 1:
pass
# somewhere in middle; not an edge
else:
pass
If I have some function, do something after locating
dim_x and dim_y are the sizes of the list.
Is there a better way to do this without so many if-else statements? Something efficient would be nice since this piece of logic is called a couple of million times ... it's for simulating annealing.
Thanks in advance. Also, what would be the best way to spell the name?
source to share
# initially:
method_list = [
bottom_left, bottom, bottom_right,
left, middle, right,
top_left, top, top_right,
]
# each time:
keyx = 0 if not x else (2 if x == self.dim_x - 1 else 1)
keyy = 0 if not y else (2 if y == self.dim_y - 1 else 1)
key = keyy * 3 + keyx
method_list[key](self, x, y, other_args)
Unconfirmed ... but the general idea should be cleared up.
Update after target messages have been abruptly moved to "Something effective would be nice, since this piece of logic is called a couple of million times ... it's for simulated annealing":
Initially, you didn't like the test chain and said that you call a function to handle each of the 8 cases. If you want fast (in Python): keep the test chain and handle each case inline instead of calling a function.
Can you use psyco? Also consider using Cython.
source to share
If I understand correctly, you have a collection of (x, y) coordinates living in a grid, and you would like to know, given any coordinate, whether it is inside the grid or on the edge.
The approach I would like to take is to normalize the grid before making the comparison so that its origin is (0,0) and the top right corner (1,1), then I would need to know the coordinate value to determine its location. Let me explain.
0) Let _max represent the maximum value and _min, for example, x_min the minimum value of the x coordinate; let_new represent a normalized value.
1) Given (x,y), compute: x_new = (x_max-x)/(x_max-x_min) and y_new=(y_max-y)/(y_max-y_min).
2) [this is pseudo code]
switch y_new:
case y_new==0: pos_y='bottom'
case y_new==1: pos_y='top'
otherwise: pos_y='%2.2f \% on y', 100*y_new
switch x_new:
case x_new==0: pos_x='left'
case x_new==1: pos_x='right'
otherwise: pos_x='%2.2f \% on x', 100*x_new
print pos_y, pos_x
It would print stuff like "bottom left" or "top right" or "32.58% on y 15.43% on x"
Hope that helps.
source to share
My guess is that if you really want to treat all of these cases in a completely different way, your solution is fine, as it is very explicit. A compact solution may look more elegant, but is likely to be more difficult to maintain. It really depends on what is going on inside the if-blocks.
Once the normal handling of, say, corners is happening, you might prefer to catch those cases with a single smart if statement.
source to share
Something like this might be more readable / maintainable. It will probably be much faster than your nested if statements as it only tests each condition once and sends it through a dictionary which is nice and fast.
class LocationThing:
def __init__(self, x, y):
self.dim_x = x
self.dim_y = y
def interior(self):
print "interior"
def left(self):
print "left"
def right(self):
print "right"
def top(self):
print "top"
def bottom(self):
print "bottom"
def top_left(self):
print "top_left"
def top_right(self):
print "top_right"
def bottom_left(self):
print "bottom_left"
def bottom_right(self):
print "bottom_right"
location_map = {
# (left, right, top, bottom)
( False, False, False, False ) : interior,
( True, False, False, False ) : left,
( False, True, False, False ) : right,
( False, False, True, False ) : top,
( False, False, False, True ) : bottom,
( True, False, True, False ) : top_left,
( False, True, True, False ) : top_right,
( True, False, False, True ) : bottom_left,
( False, True, False, True ) : bottom_right,
}
def location(self, x,y):
method = self.location_map[(x==0, x==self.dim_x-1, y==0, y==self.dim_y-1)]
return method(self)
l = LocationThing(10,10)
l.location(0,0)
l.location(0,1)
l.location(1,1)
l.location(9,9)
l.location(9,1)
l.location(1,9)
l.location(0,9)
l.location(9,0)
When you do the above, it prints
top_left
left
interior
bottom_right
right
bottom
bottom_left
top_right
source to share
For a quick inner loop function, you can just bite the bullet and do ugly: nested else statements with duplicate terms so that each comparison is only done once and it runs about twice as fast as an example of a cleaner answer (by mobrule):
import timeit
def f0(x, y, x_dim, y_dim):
if x!=0:
if x!=x_dim: # in the x interior
if y!=0:
if y!=y_dim: # y interior
return "interior"
else: # y==y_dim edge 'top'
return "interior-top"
else:
return "interior-bottom"
else: # x = x_dim, "right"
if y!=0:
if y!=y_dim: #
return "right-interior"
else: # y==y_dim edge 'top'
return "right-top"
else:
return "right-bottom"
else: # x=0 'left'
if y!=0:
if y!=y_dim: # y interior
return "left-interior"
else: # y==y_dim edge 'top'
return "left-top"
else:
return "left-bottom"
r_list = ["interior","top","bottom","left","top-left",
"bottom-left","right","top-right","bottom-right"]
def f1(x,y,dim_x,dim_y):
index = 1*(y==0) + 2*(y==dim_y-1) + 3*(x==0) + 6*(x==dim_x-1)
return r_list[index]
for x, y, x_dim, y_dim in [(4, 4, 5, 6), (0, 0, 5, 6)]:
t = timeit.Timer("f0(x, y, x_dim, y_dim)", "from __main__ import f0, f1, x, y, x_dim, y_dim, r_list")
print "f0", t.timeit(number=1000000)
t = timeit.Timer("f1(x, y, x_dim, y_dim)", "from __main__ import f0, f1, x, y, x_dim, y_dim, r_list")
print "f1", t.timeit(number=1000000)
What gives:
f0 0.729887008667 # nested if-else for interior point (no "else"s)
f1 1.4765329361
f0 0.622623920441 # nested if-else for left-bottom (all "else"s)
f1 1.49259114265
So, this is slightly better than twice as fast as mobrule's answer, which was the fastest code I knew would work when I posted this. (Also, I moved the list of strings from the list of functions, which sped up the result by 50%.) Speed over beauty?
If you want a concise and easy-to-read solution, I suggest:
def f1(x, y, x_dim, y_dim):
d_x = {0:"left", x_dim:"right"}
d_y = {0:"bottom", y_dim:"top"}
return d_x.get(x, "interior")+"-"+d_y.get(y, "interior")
which is as fast as others in my time.
source to share