DjangoBB LoFi version

Начало » Python для новичков » По логике Python'a

Duck-Pagan

Май 2, 2012 08:56:38

Есть вопрос по написанию определенного кода в локаничном стиле Python.
Реализую некоторый модифицированный алгоритм А* (трассировка пути).

import random
#есть некоторый открытый список вершин
opendot = [(random.randint(0,2),random.randint(0,2)) for j in range(30)]
#есть закрытый список, со стартовой точкой. При этом этот список не изменяется, как это следует в 
#механике алгоритма А*
closedot = [(0,0)]
#есть "шаг" точки. Т.е. лист с вариантами движения, для проверки соседних вершин
tdot = [(-1,0),(1,0),(0,-1),(0,1)]

Собственно задача - локанично написать проверку: есть ли соседнии вершины((-1,0), (1,0),(0,-1),(0,1)) в открытом списке?
В лоб эта задача решается довольно большим куском кода, что грубо. Есть соблазн использовать лямбду с суммой элементов списка для проверки. Но пока идея туманна и возникает вопрос производительности этой функции в питоне.
Можете предложить вариаты проверки, возможно, структурные?

fata1ex

Май 2, 2012 13:13:34

Задаваться вопросом производительности до написания кода - дурной тон. Напишите для начала в лоб, это будет проще (как для понимания, так и для написания) и, возможно, будет устраивать по скорости. Если не будет, надо тогда уже смотреть, что можно оптимизировать.

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

Duck-Pagan

Май 2, 2012 18:18:59

fata1ex
Задаваться вопросом производительности до написания кода - дурной тон. Напишите для начала в лоб, это будет проще (как для понимания, так и для написания) и, возможно, будет устраивать по скорости. Если не будет, надо тогда уже смотреть, что можно оптимизировать.

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

Мне кажется, что это нормально: думать как из Python'a выжать скорость Си (хотя, наверное, кто-то и не согласиться). Погулял, к вечеру задачу решил таким образом(уже не в лоб, но где-то по почкам):

import random
opendot = [(random.randint(0,2),random.randint(0,2)) for j in range(30)]
closedot = [(0,0)]
tdot = [(-1,0),(1,0),(0,-1),(0,1)]
nrdot = [(x[0] + y[0], x[1] + y[1]) for x in closedot for y in tdot if (x[0] + y[0], x[1] + y[1]) in opendot]
#если использовать set и insubset() - то можно получить True\False - ну и расписать эту строчку в 
#несколько строк
#в результате получаем nrdot - список соседних вершине( <= четырех) точек, которые присутствуют в
#открытом списке.

Скорость нормальная, но опять же витает чувство, что и эту запись:

(x[0] + y[0], x[1] + y[1])

- можно как-то красивее оформить. Хотя.. .

fata1ex

Май 2, 2012 18:59:18

Я говорил не об оптимизации вцелом, а о преждевременной оптимизации. Нет смысла думать, как бы сделать код быстрее, пока самого кода еще нет.

Насчет “записи”:

>>> a = [1,2]
>>> b = [3,4]
>>> zip(a,b)
[(1, 3), (2, 4)]
>>> [ sum(pair) for pair in zip(a,b) ]
[4, 6]

PS. Кстати, вместо двух for в comprehension я бы тоже использовал zip.

Duck-Pagan

Май 3, 2012 04:18:58

fata1ex, спасибо! zip(), map() - совсем вылетели из головы!

“Нет смысла думать, как бы сделать код быстрее, пока самого кода еще нет.”
По этому поводу мысль вот какая: задача определяет парадигму для ее решения, а думать как сделать код быстрее определяет методы используемой парадигмы. Впрочем, это просто зависит от образа мышления.

В любом случае, за совет - благодарю.

sp3

Май 3, 2012 11:55:01

Duck-Pagan
задача определяет парадигму для ее решения, а думать как сделать код быстрее определяет методы используемой парадигмы.

Эээ …. завис.

1.пишите понятный код
2.профайлер
3.переписываете тормознутую часть
4.профайлер
5.переписываете тормознутую часть на си
6.профайлер
7.получаете +5% скорости при ужасном непонятном коде
8.исползуете понятный код из п1

fata1ex

Май 3, 2012 13:09:47

Duck-Pagan, не надо думать, что это моя мысль про преждевременную оптимизацию :) Это говорят десятки талантливейших людей, начиная от Кнута и заканчивая Макконнеллом. Можно, конечно, придраться и сказать, что в 5% случаев нужно заранее продумать стратегию построения и архитектуру приложения с учетом последующей оптимизации, но в общем случае, а тем более в вашем, оптимизировать надо “опосля”.