On 7 Jul., 19:32, Ethan Furman <et...@stoneleaf.us> wrote:
> Nobody wrote:
> > On Wed, 07 Jul 2010 15:08:07 +0200, Thomas Jollans wrote:
>
> >> you should never rely on a floating-point number to have exactly a
> >> certain value.
>
> > "Never" is an overstatement. There are situations where you can rely
> > upon a floating-point number having exactly a certain value.
>
> It's not much of an overstatement. How many areas are there where you
> need the number
> 0.100000000000000005551115123125782702118158340454101562500000000000?
>
> If I'm looking for 0.1, I will *never* (except by accident ;) say
>
> if var == 0.1:
>
> it'll either be <= or >=.
The following is an implementation of a well-known algorithm.
Why would you want to replace the floating point comparisons? With
what?
(This is toy-code.)
#####
from random import random
def min_cost_path(cost_right, cost_up):
""" return minimal cost and its path in a rectangle - going up and
right only """
cost = dict()
size_x, size_y = max(cost_right)
#compute minimal cost
cost[0, 0] = 0.0
for x in range(size_x):
cost[x + 1, 0] = cost[x, 0] + cost_right[x, 0]
for y in range(size_y):
cost[0, y + 1] = cost[0, y] + cost_up[0, y]
for x in range(size_x):
cost[x + 1, y + 1] = min(cost[x, y + 1] + cost_right[x, y
+ 1],
cost[x + 1, y] + cost_up[x + 1,
y])
#compute path (reversed)
x = size_x
y = size_y
path = []
while x != 0 and y != 0:
if x == 0:
y -= 1
path.append("u")
elif y == 0:
x -= 1
path.append("r")
elif cost[x - 1, y] + cost_right[x - 1, y] == cost[x, y]: # fp
compare
x -= 1
path.append("r")
elif cost[x, y - 1] + cost_up[x, y - 1] == cost[x, y]: # fp
compare
y -= 1
path.append("u")
else:
raise ValueError
return cost[size_x, size_y], "".join(reversed(path))
if __name__ == "__main__":
size = 100
cost_right = dict(((x, y), random()) for x in range(size) for y in
range(size))
cost_up = dict(((x, y), random()) for x in range(size) for y in
range(size))
print min_cost_path(cost_right, cost_up)
--
http://mail.python.org/mailman/listinfo/python-list
