勝手に採点 (Re: 自分ならこう書く - pythonでA*)

自分ならこう書く - pythonでA* - ラシウラより

def astar(init, goal, nexts,
          distance=lambda path: len(path),
          heuristic=lambda pos: 0):
    import heapq
    queue = []
    checked = [init]
    heapq.heappush(queue, (distance([init]) + heuristic(init), [init]))
    while len(queue) > 0:
        score, path = heapq.heappop(queue)
        last = path[-1]
        if last == goal: return path
        for pos in nexts(last):
            if pos in checked: continue
            checked.append(pos)
            newpath = path + [pos]
            heapq.heappush(queue,
                           (distance(newpath) + heuristic(pos), newpath))
            pass
        pass
    return None

とてもPythonicな設計だしコードも十分綺麗だけど、気になった点が:

distanceのデフォルト値がlambdaである必要性が無い
heapq の関数に毎回属性アクセスしている。
checked が配列なので pos in checked が遅い。
while len(queue) > 0 は while queue で表現でき、後者のほうが速い可能性がある。
pass を使ってるのはインデント解除用？

直したらこんな感じ。

def astar(init, goal, nexts,
          distance=len,
          heuristic=lambda pos: 0):
    import heapq
    hpush = heapq.heappush
    hpop = heapq.heappop
    queue = []
    checked = set([init])
    hpush(queue, (distance([init]) + heuristic(init), [init]))
    while queue:
        score, path = hpop(queue)
        last = path[-1]
        if last == goal:
            return path
        for pos in nexts(last):
            if pos in checked:
                continue
            checked.add(pos)
            newpath = path + [pos]
            hpush(queue, (distance(newpath) + heuristic(pos), newpath))

大きい問題なら結構差がつくかも。特に checked がモロに計算量に影響するので。