Как улучшить производительность этого кода? - PullRequest
Новая
       23

Как улучшить производительность этого кода?

37 голосов
/ 28 ноября 2010

Благодаря некоторой помощи от людей здесь я смог получить свой код для работы головоломки Tasmanian верблюдов. Тем не менее, это ужасно медленно (я думаю. Я не уверен, потому что это моя первая программа на Python). Пример выполнения в нижней части кода занимает много времени на моей машине: 

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 минут :(). Я обновлю его, если и когда он закончится.

Что я должен сделать, чтобы улучшить этот код? (В основном с точки зрения производительности, но приветствуются и любые другие предложения).

Ответы [ 7 ]

58 голосов
/ 29 ноября 2010

Сначала позвольте мне рассказать вам, как найти проблему. Тогда я скажу вам, где это:

Я даже не удосужился попытаться выяснить ваш код. Я просто запустил его и взял 3 образца стека случайного времени. Я сделал это, набрав control-C и просмотрев полученную трассировку стека.

Один из способов посмотреть на это: если оператор появляется на X% случайных трассировок стека, то он находится в стеке примерно в X% времени, так что именно за это он отвечает. Если бы вы могли избежать его выполнения, это то, сколько вы бы сэкономили.

ОК, я взял 3 образца стека. Вот они: 

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

File "camels.py", line 87, in <module>
  print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
  return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
  openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

Обратите внимание, в этом случае все образцы стеков идентичны. Другими словами, каждая из этих трех строк несет личную ответственность почти за все время. Посмотрите на них: 

line        87: print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
line solve: 85: return astar(formation, heuristic, solution, getneighbors)
line astar: 80: openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

Очевидно, что строка 87 - это не та, которую вы можете избежать, и, вероятно, тоже не 85. Это оставляет 80, openlist.put колл. Теперь вы не можете определить, связана ли проблема с оператором +, вызовом heuristicf, вызовом node или вызовом put. Вы можете узнать, можете ли вы разбить их на отдельные строки.

Так что я надеюсь, что вы воспользуетесь этим быстрым и простым способом выяснить, где ваши проблемы с производительностью.

38 голосов
/ 28 ноября 2010

Я тоже с этим сталкивался.Узкое место здесь на самом деле if neighbor in closedlist.

. Оператор in очень прост в использовании, вы забываете, что это линейный поиск, а когда вы выполняете линейный поиск по спискам, он может быстро складываться.То, что вы можете сделать, это преобразовать закрытый список в set объект.Это сохраняет хэши своих элементов, поэтому оператор in гораздо эффективнее, чем для списков.Однако списки не являются объектами, которые могут быть хешируемыми, поэтому вам придется менять конфигурации на кортежи вместо списков.

Если порядок closedlist имеет решающее значение для алгоритма, вы можете использовать набор для in оператор и держать параллельный список для ваших результатов.

Я попробовал простую реализацию этого, включая трюк с именованным набором aaronasterling, и он выполнил за 0,2 секунды для первого примера и 2,1 секунды для второго, но я нене пытался проверить результаты для второго более длинного.

9 голосов
/ 28 ноября 2010

tkerwin верно, что вы должны использовать набор для закрытого списка, который сильно ускоряет ход событий, но все еще довольно медленный для 4 верблюдов с каждой стороны.Следующая проблема заключается в том, что вы допускаете множество решений, которые невозможны, потому что вы позволяете fCamels двигаться назад, а bCamels - идти вперед.Чтобы это исправить, замените линии 

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)

на 

if(igap > 0 and formation[igap-1] == fCamel):
    genn(igap, igap-1)
if(igap > 1 and formation[igap-2] == fCamel):
    genn(igap, igap-2)
if (igap < len(formation) - 1) and formation[igap+1] == bCamel:
    genn(igap, igap+1)
if (igap < len(formation) - 2) and formation[igap + 2] == bCamel:
    genn(igap, igap+2)

, и я получу решение по 4 верблюдам на каждой стороне проблемы в течение 0,05 секунды, а не 10 секунд.Я также попробовал 5 верблюдов с каждой стороны, и это заняло 0,09 секунды.Я также использую набор для closedlist и heapq, а не Queue.

Дополнительное ускорение

Вы можете получить дополнительное ускорение, правильно используя свою эвристику.В настоящее время вы используете строку 

openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))

(или версию heapq), но вы должны изменить ее на 

openlist.put((heuristicf(neighbor), node(neighbor, current.g + 1, current)))

Это не учитывает количество ходов, которыебыл необходим, но это нормально.С этой головоломкой (и отсеиванием ходов, которые перемещают верблюдов в неправильном направлении), вам не нужно беспокоиться о количестве ходов, которые требуется - либо движение продвигает вас к решению, либо оно заходит в тупик,Другими словами, все возможные решения требуют одинакового количества ходов.Это одно изменение требует времени, чтобы найти решение для 12 верблюдов в каждом боковом случае, от более чем 13 секунд (даже используя heapq, установленный для closedlist и изменений, чтобы найти соседей выше) до 0,389 секунд.Это неплохо.

Кстати, лучший способ найти решение, найденное вами, - проверить, равен ли индекс первого fCamel длине формирования / 2 + 1 (с использованием деления int) ичто индекс до этого равен разрыву.

4 голосов
/ 28 ноября 2010

Замена 

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

с 

node = collections.namedtuple('node', 'arrangement, g, parent')

уменьшил время с 340-600 мсек до 11,4 1,89 1 мсек на входе [fCamel, fCamel, gap, bCamel, bCamel]. Это дало тот же результат.

Это, очевидно, не поможет с какими-либо алгоритмическими проблемами, но с точки зрения микрооптимизации это неплохо.

1 У меня неправильный ввод. Был дополнительный fCamel, который заставлял его работать медленнее.

3 голосов
/ 28 ноября 2010

Ну, я не могу точно сказать, где ваш алгоритм сбился с пути, но я просто пошел дальше и сделал свой собственный.Чтобы сделать простейшую вещь, которая могла бы работать, я использовал убогую версию алгоритма Дейкстры, где открытые узлы посещаются в произвольном порядке, без учета расстояния.Это означает, что мне не нужно придумывать эвристику. 

""" notation: a game state is a string containing angle
    brackets ('>' and '<') and blanks
 '>>> <<<'

 """

def get_moves(game):
    result = []
    lg = len(game)
    for i in range(lg):
        if game[i] == '>':
            if i < lg-1 and game[i+1] == ' ': # '> ' -> ' >'
                result.append(game[:i]+' >'+game[i+2:])
            if i < lg-2 and game[i+1] != ' ' and game[i+2] == ' ': # '>< ' -> ' <>'
                result.append(game[:i]+' '+game[i+1]+'>'+game[i+3:])
        if game[i] == '<':
            if i >= 1 and game[i-1] == ' ': # ' <' -> '< '
                result.append(game[:i-1]+'< '+game[i+1:])
            if i >= 2 and game[i-1] != ' ' and game[i-2] == ' ': # ' ><' -> '<> '
                result.append(game[:i-2]+'<'+game[i-1]+' '+game[i+1:])
    return result



def wander(start, stop):
    fringe = [start]
    paths = {}

    paths[start] = ()

    def visit(state):
      path = paths[state]
      moves = [move for move in get_moves(state) if move not in paths]
      for move in moves:
          paths[move] = paths[state] + (state,)
      fringe.extend(moves)

    while stop not in paths:
      visit(fringe.pop())

    print "still open: ", len(fringe)
    print "area covered: " , len(paths)
    return paths[stop] + (stop,)

if __name__ == "__main__":
    start = '>>>> <<<<'
    stop = '<<<< >>>>'
    print start, "   -->   ", stop
    pathway = wander(start,stop)
    print len(pathway), "moves: ", pathway
3 голосов
/ 28 ноября 2010

Код ниже использует менее 1 секунды, чтобы решить эту проблему: 

from itertools import permutations

GAP='G'
LEFT='F'
RIGHT='B'
BEGIN=('F','F','F','F','G','B','B','B','B')
END=('B','B','B','B','G','F','F','F','F')
LENGTH=len(BEGIN)

ALL=set(permutations(BEGIN))

def NextMove(seq):
    g=seq.index(GAP)
    ret = set()
    def swap(n):
        return seq[:n]+seq[n:n+2][::-1]+seq[n+2:]
    if g>0 and seq[g-1]==LEFT:
        ret.add(swap(g-1))
    if g<LENGTH-1 and seq[g+1]==RIGHT:
        ret.add(swap(g))
    if g<LENGTH-2 and seq[g+1]==LEFT and seq[g+2]==RIGHT:
        ret.add(seq[:g]+seq[g+2:g+3]+seq[g+1:g+2]+seq[g:g+1]+seq[g+3:])
    if g>1 and seq[g-1]==RIGHT and seq[g-2]==LEFT:
        ret.add(seq[:g-2]+seq[g:g+1]+seq[g-1:g]+seq[g-2:g-1]+seq[g+1:])

    return ret

AllMoves={state:NextMove(state) for state in ALL}

def Solve(now,target):
    if now==target:
        return True
    for state in AllMoves[now]:
        if Solve(state,target):
            print(now)
            return True
    return False

Solve(BEGIN,END)
0 голосов
/ 29 ноября 2010

Мой другой ответ довольно длинный, поэтому я решил перечислить его как отдельный ответ. Эта проблема действительно лучше подходит для поиска в глубину. Я создал решение поиска в глубину, и оно намного, намного быстрее, чем оптимизированный метод A-star, внесенный с изменениями, описанными в моем другом ответе (что намного, намного быстрее, чем код OP). Например, здесь приведены результаты для выполнения моей A-звезды и моих методов поиска в глубину для случая 17 верблюдов на сторону. 

A-star:  14.76 seconds
Depth-first search: 1.30 seconds

Вот код глубины первого метода, если вы заинтересованы: 

from sys import argv

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

def issolution(formlen):
    def solution(formation):
        if formation[formlen2] == gap:
            return formation.index(fCamel) == x
        return 0
    x = formlen/2 + 1
    formlen2 = formlen/2
    return solution

def solve(formation):
    def depthfirst(form, g):
        if checksolution(form):
            return [tuple(form)], g + 1
        else:
            igap = form.index(gap)
            if(igap > 1 and form[igap-2] == fCamel):
                form[igap-2],form[igap] = form[igap],form[igap-2]
                res = depthfirst(form,g+1)
                form[igap-2],form[igap] = form[igap],form[igap-2]
                if res != 0:
                    return [tuple(form)]+res[0],res[1]
            if (igap < flen - 2) and form[igap + 2] == bCamel:
                form[igap+2],form[igap] = form[igap],form[igap+2]
                res = depthfirst(form,g+1)
                form[igap+2],form[igap] = form[igap],form[igap+2]
                if res != 0:
                    return [tuple(form)]+res[0],res[1]
            if(igap > 0 and form[igap-1] == fCamel):                
                form[igap-1],form[igap] = form[igap],form[igap-1]
                res = depthfirst(form,g+1)
                form[igap-1],form[igap] = form[igap],form[igap-1]
                if res != 0:
                    return [tuple(form)]+res[0],res[1]               
            if (igap < flen - 1) and form[igap+1] == bCamel:
                form[igap+1],form[igap] = form[igap],form[igap+1]
                res = depthfirst(form,g+1)
                form[igap+1],form[igap] = form[igap],form[igap+1]
                if res != 0:
                    return [tuple(form)]+res[0],res[1]                
            return 0
    flen = len(formation)
    checksolution = issolution(flen)
    res = depthfirst(list(formation), 0)
    return res

L = lambda x: tuple([fCamel]*x + [gap] + [bCamel]*x)
print solve(L(int(argv[1])))
...