Как повысить производительность этого кода?
Благодаря некоторой помощи здешних людей я смог заставить свой код для головоломки с тасманскими верблюдами работать. Однако это ужасно медленно (я думаю. Я не уверен, потому что это моя первая программа на 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 минут : (). Я обновлю это, если и когда это завершится.
Что мне следует сделать, чтобы улучшить этот код? (В основном с точки зрения производительности, но также приветствуются любые другие предложения).
Переведено автоматически
Ответ 1
Сначала позвольте мне рассказать вам, как найти проблему. Затем я расскажу вам, в чем она заключается.:
Я даже не потрудился попытаться разобраться в вашем коде. Я просто запустил его и взял 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 call, или в put вызове. Вы могли бы узнать, можно ли разделить их на отдельные строки.
Итак, я надеюсь, что вы узнаете из этого быстрый и простой способ выяснить, в чем заключаются ваши проблемы с производительностью.
Ответ 2
Я тоже сталкивался с этим раньше. На самом деле узким местом здесь является if neighbor in closedlist.
Оператор in настолько прост в использовании, что вы забываете, что это линейный поиск, а когда вы выполняете линейный поиск по спискам, он может быстро складываться. Что вы можете сделать, так это преобразовать closedlist в set объект. При этом сохраняются хэши его элементов, поэтому in оператор намного эффективнее, чем для списков. Однако списки не являются элементами, которые можно хэшировать, поэтому вам придется преобразовать свои конфигурации в кортежи, а не в списки.
Если порядок closedlist имеет решающее значение для алгоритма, вы могли бы использовать set для in оператора и вести параллельный список для ваших результатов.
Я попробовал простую реализацию этого, включая трюк namedtuple от aaronasterling, и он был выполнен за 0,2 секунды для вашего первого примера и 2,1 секунды для вашего второго, но я не пробовал проверять результаты для второго, более длинного примера.
Ответ 3
tkerwin прав в том, что вы должны использовать set для closedlist , что значительно ускоряет работу, но это все еще немного медленно для 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 division) и равен ли индекс перед этим промежутку.
Ответ 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,891 мс [fCamel, fCamel, gap, bCamel, bCamel]. Результат тот же.
Очевидно, что это не поможет с какими-либо алгоритмическими проблемами, но что касается микрооптимизации, то это неплохо.
1 У меня были неправильные входные данные. Там было дополнительное fCamel, из-за которого он работал медленнее.