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

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

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

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

Спасибо.

Ответ 1

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

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

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

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

Ответ 2

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

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

Один из способов взглянуть на это: если выражение появляется на 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. Вы могли бы узнать, можете ли вы разбить их на отдельные строки.

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

Ответ 3

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 верблюдов с каждой стороны проблемы, как .05 секунд, а не 10 секунд. Я также попробовал 5 верблюдов с каждой стороны, и это заняло 0,09 секунды. Я также использую набор для закрытого списка и 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, установить для закрытого списка и изменения, чтобы найти соседей выше) до 0,389 секунды. Это неплохо.

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

Ответ 4

Замена

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 ¹ msecs на входе [fCamel, fCamel, gap, bCamel, bCamel]. Это дало тот же результат.

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

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

Ответ 5

Приведенный ниже код с использованием менее 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)

Ответ 6

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

""" 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

Ответ 7

Мой другой ответ довольно длинный, поэтому я решил перечислить это как отдельный ответ. Эта проблема действительно лучше подходит для выполнения поиска по глубине. Я сделал решение поиска по глубине, и это намного быстрее, чем оптимизированный метод A-звезды, сделанный с изменениями, изложенными в моем другом ответе (что намного, намного быстрее, чем 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])))