如何提高这段代码的性能? [英] How to improve performance of this code?

问题描述

多亏了这里的人的帮助，我才能够获得塔斯马尼亚骆驼拼图工作的代码.但是，这太慢了(我认为.我不确定，因为这是我的第一个Python程序).在代码底部运行的示例需要很长时间才能在我的机器上解决:

Thanks to some help from people here, I was able to get my code for Tasmanian camels puzzle working. However, it is horribly slow (I think. I'm not sure because this is my first program in Python). The example run in the bottom of the code takes a long time to be solved in my machine:

dumrat@dumrat:~/programming/python$ time python camels.py
[['F', 'F', 'F', 'G', 'B', 'B', 'B'], ['F', 'F', 'G', 'F', 'B', 'B', 'B'],
 ['F', 'F', 'B', 'F', 'G', 'B', 'B'], ['F', 'F', 'B', 'F', 'B', 'G', 'B'],
 ['F', 'F', 'B', 'G', 'B', 'F', 'B'], ['F', 'G', 'B', 'F', 'B', 'F', 'B'],
 ['G', 'F', 'B', 'F', 'B', 'F', 'B'], ['B', 'F', 'G', 'F', 'B', 'F', 'B'],
 ['B', 'F', 'B', 'F', 'G', 'F', 'B'], ['B', 'F', 'B', 'F', 'B', 'F', 'G'],
 ['B', 'F', 'B', 'F', 'B', 'G', 'F'], ['B', 'F', 'B', 'G', 'B', 'F', 'F'],
 ['B', 'G', 'B', 'F', 'B', 'F', 'F'], ['B', 'B', 'G', 'F', 'B', 'F', 'F'],
 ['B', 'B', 'B', 'F', 'G', 'F', 'F']]

real    0m20.883s
user    0m20.549s
sys    0m0.020s

代码如下:

import Queue

fCamel = 'F'
bCamel = 'B'
gap = 'G'

def solution(formation):
    return len([i for i in formation[formation.index(fCamel) + 1:]
                if i == bCamel]) == 0

def heuristic(formation):
    fCamels, score = 0, 0
    for i in formation:
        if i == fCamel:
            fCamels += 1;
        elif i == bCamel:
            score += fCamels;
        else:
            pass
    return score

def getneighbors (formation):
    igap = formation.index(gap)
    res = []
    # AB_CD --> A_BCD | ABC_D | B_ACD | ABD_C
    def genn(i,j):
        temp = list(formation)
        temp[i], temp[j] = temp[j], temp[i]
        res.append(temp)

    if(igap > 0):
        genn(igap, igap-1)
    if(igap > 1):
        genn(igap, igap-2)
    if igap < len(formation) - 1:
        genn(igap, igap+1)
    if igap < len(formation) - 2:
        genn(igap, igap+2)

    return res

class node:
    def __init__(self, a, g, p):
        self.arrangement = a
        self.g = g
        self.parent = p

def astar (formation, heuristicf, solutionf, genneighbors):

    openlist = Queue.PriorityQueue()
    openlist.put((heuristicf(formation), node(formation, 0, None)))
    closedlist = []

    while 1:
        try:
            f, current = openlist.get()
        except IndexError:
            current = None

        if current is None:
            print "No solution found"
            return None;

        if solutionf(current.arrangement):
            path = []
            cp = current
            while cp != None:
                path.append(cp.arrangement)
                cp = cp.parent
            path.reverse()
            return path

        #arr = current.arrangement
        closedlist.append(current)
        neighbors = genneighbors(current.arrangement)

        for neighbor in neighbors:
            if neighbor in closedlist:
                pass
            else:
                openlist.put((current.g + heuristicf(neighbor),
                             node(neighbor, current.g + 1, current)))

        #sorted(openlist, cmp = lambda x, y : x.f > y.f)

def solve(formation):
    return astar(formation, heuristic, solution, getneighbors)

print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
#print solve([fCamel, fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel, bCamel])

每只只供3只骆驼.我想至少这样做4次.该测试用例仍在运行(现在:()大约5分钟了.如果完成，我将对其进行更新.

That is just for 3 camels each. I wanted to do this for 4 at least. That test case is still running (It's been about 5 minutes now :(). I'll update this if and when it finishes.

我应该怎么做才能改善这段代码? (通常是性能方面的建议，但也欢迎提出其他建议).

What should I do to improve this code? (Mostly performance-wise, but any other suggestions are welcome also).

推荐答案

我以前也被这个绊倒了.这里的瓶颈实际上是if neighbor in closedlist.

I've been tripped up by this before too. The bottleneck here is actually if neighbor in closedlist.

in语句非常易于使用，您忘记了它是线性搜索，而当您在列表上进行线性搜索时，它可以快速加起来.您可以做的是将封闭列表转换为set对象.这样可以保留其项目的哈希值，因此in运算符的效率要比列表运算符的效率高得多.但是，列表不是可散列的项目，因此您必须将配置更改为元组而不是列表.

The in statement is so easy to use, you forget that it's linear search, and when you're doing linear searches on lists, it can add up fast. What you can do is convert closedlist into a set object. This keeps hashes of its items so the in operator is much more efficient than for lists. However, lists aren't hashable items, so you will have to change your configurations into tuples instead of lists.

如果closedlist的顺序对算法至关重要，则可以为in运算符使用一个集合，并为结果保留一个并行列表.

If the order of closedlist is crucial to the algorithm, you could use a set for the in operator and keep an parallel list around for your results.

我尝试了一个简单的实现，包括aaronasterling的namedtuple技巧，它在第一个示例中的执行时间为0.2秒，在第二个示例中的执行时间为2.1秒，但是我没有尝试验证第二个较长示例的结果.

I tried a simple implementation of this including aaronasterling's namedtuple trick and it performed in 0.2 sec for your first example and 2.1 sec for your second, but I haven't tried verifying the results for the second longer one.

这篇关于如何提高这段代码的性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！