我正在用Python编写Astar算法的实现,在某些时候我想选择open_set
中具有最低f_score value
的元素:
# current is the node in open_set having the lowest f_score value
current = min_f_score(open_set, f_score)
open_set
是一个元组的列表(x, y)
,表示二维中一个点的坐标,f_score
是一个字典{(x, y): score}
,它给每个元组(x, y)
分配f_score
的值。
我的第一个min_f_score
实现如下:
def min_f_score(open_set, f_score):
# First we initialize min_score_element and min_score
min_score_element = open_set[0]
min_score = f_score[open_set[0]]
# Then we look for the element from f_score keys with the lowest value
for element in open_set:
if element in f_score.keys() and f_score[element] < min_score:
min_score = f_score[element]
min_score_element = element
return min_score_element
它工作得很好,但我想知道我是否能想出一些更精简,更python化的代码。经过一番研究,我想出了另外两个实现:
def min_f_score(open_set, f_score):
# We filter the elements from open_set and then find the min f_score value
return min(filter(lambda k: k in open_set, f_score), key=(lambda k: f_score[k]))
:
def min_f_score(open_set, f_score):
# We look for the min while assigning inf value to elements not in open_set
return min(f_score, key=(lambda k: f_score[k] if k in open_set else float("inf")))
两者似乎都可以工作,并给我相同的结果,但明显比第一个实现慢。
出于好奇,我想知道是否有更好的方法来实现min_f_score
?
编辑:根据@azro(谢谢)的建议,我正在添加一个执行代码示例:
open_set = [(1, 2), (1, 3), (2, 1), (2, 2), (3, 1), (1, 4), (4, 1), (1, 5), (5, 0), (5, 1), (0, 6), (1, 6)]
f_score = {(0, 0): 486.0, (0, 1): 308.0, (1, 0): 308.0, (1, 1): 265.0, (0, 2): 265.0, (1, 2): 338.0, (0, 3): 284.0, (1, 3): 450.0, (2, 0): 265.0, (2, 1): 338.0, (2, 2): 629.0, (3, 0): 284.0, (3, 1): 450.0, (0, 4): 310.0, (1, 4): 550.0, (4, 0): 310.0, (4, 1): 564.0, (0, 5): 316.0, (1, 5): 588.0, (5, 0): 316.0, (5, 1): 606.0, (0, 6): 298.0, (1, 6): 534.0}
min_f_score(open_set, f_score)
输出:(0, 6)
V1
有dict.get()
的版本比你的2个min()
版本快得多(慢10倍以上),但一直是大约2倍慢
def min_f_score_d(open_set, f_score):
inf = float("inf")
return min(open_set, key=lambda k: f_score.get(k, inf))
V2由@stefan-pochmann建议,这个比经典迭代稍微慢一点
def min_f_score(open_set, f_score):
return min(f_score.keys() & open_set, key=f_score.get)
注意
if element in f_score and f_score[element] < min_score:
# if faster than
if element in f_score.keys() and f_score[element] < min_score:
<<BK_HR>工作台代码/h3>from timeit import timeit
A = """
def min_f_score(open_set, f_score):
min_score_element, min_score = open_set[0], f_score[open_set[0]]
for element in open_set:
if element in f_score and f_score[element] < min_score:
min_score = f_score[element]
min_score_element = element
return min_score_element
"""
B = """
def min_f_score(open_set, f_score):
inf = float("inf")
return min(open_set, key=lambda k: f_score.get(k, inf))
"""
C = """
def min_f_score(open_set, f_score):
return min(f_score.keys() & open_set, key=f_score.get)
"""
SETUP = """
from random import randrange
open_set = [(randrange(1000), randrange(1000)) for _ in range(1000)]
f_score = {pair: randrange(1000) for pair in open_set[:len(open_set) // 2]}
"""
NB = 20_000
print(timeit(setup=SETUP + A, stmt="min_f_score(open_set, f_score)", number=NB)) # ~2.7
print(timeit(setup=SETUP + B, stmt="min_f_score(open_set, f_score)", number=NB)) # ~4.8
print(timeit(setup=SETUP + C, stmt="min_f_score(open_set, f_score)", number=NB)) # ~3.1
from timeit import timeit
A = """
def min_f_score(open_set, f_score):
min_score_element, min_score = open_set[0], f_score[open_set[0]]
for element in open_set:
if element in f_score and f_score[element] < min_score:
min_score = f_score[element]
min_score_element = element
return min_score_element
"""
B = """
def min_f_score(open_set, f_score):
inf = float("inf")
return min(open_set, key=lambda k: f_score.get(k, inf))
"""
C = """
def min_f_score(open_set, f_score):
return min(f_score.keys() & open_set, key=f_score.get)
"""
SETUP = """
from random import randrange
open_set = [(randrange(1000), randrange(1000)) for _ in range(1000)]
f_score = {pair: randrange(1000) for pair in open_set[:len(open_set) // 2]}
"""
NB = 20_000
print(timeit(setup=SETUP + A, stmt="min_f_score(open_set, f_score)", number=NB)) # ~2.7
print(timeit(setup=SETUP + B, stmt="min_f_score(open_set, f_score)", number=NB)) # ~4.8
print(timeit(setup=SETUP + C, stmt="min_f_score(open_set, f_score)", number=NB)) # ~3.1