Проблема Привет, ребята. Я ищу несколько советов по производительности Python. Немного предыстории моей проблемы:
Дано:
- A
(x,y) сетка узлов, каждый со значением (0...255), начиная с 0
- Список
N входных координат, каждая в указанном месте в диапазоне (0...x, 0...y)
- Значение
Z, которое определяет «соседство» в количестве узлов
Увеличить значение узла на входной координате и соседей узла. Соседи за краем сетки игнорируются. (Без упаковки)
BASE CASE: Сетка размером 1024x1024 узлов с 400 входными координатами и диапазоном Z из 75 узлов.
Обработка должна быть O(x*y*Z*N). Я ожидаю, что x, y и Z останутся примерно в пределах значений в базовом случае, но число входных координат N может увеличиться до 100 000. Моя цель - минимизировать время обработки.
Текущие результаты Между моим началом и комментариями ниже у нас есть несколько реализаций.
Скорость работы на моем Intel Core 2 Duo 2,26 ГГц с Python 2.6.1:
f1: 2.819s
f2: 1.567s
f3: 1.593s
f: 1.579s
f3b: 1.526s
f4: 0.978s
f1 - исходная наивная реализация: три вложенных for цикла.
f2 заменяет внутренний цикл for на понимание списка.
f3 основан на предложении Андрея в комментариях и заменяет внешний for на map()
f это предложение Криса в ответах ниже
f3b - это взгляд Крисса на f3
f4 это вклад Алекса.
Код включен ниже для вашего прочтения.
Вопрос Как еще сократить время обработки? Я бы предпочел sub-1.0s для параметров теста.
Пожалуйста, оставьте рекомендации для нативного Python. Я знаю, что могу перейти к сторонним пакетам, таким как numpy , но я стараюсь избегать любых сторонних пакетов. Кроме того, я сгенерировал случайные входные координаты и упростил определение обновлений значения узла, чтобы наше обсуждение было простым. Специфика должна немного измениться и выходит за рамки моего вопроса.
спасибо большое!
f1 - начальная наивная реализация: три вложенных for цикла.
def f1(x,y,n,z):
rows = [[0]*x for i in xrange(y)]
for i in range(n):
inputX, inputY = (int(x*random.random()), int(y*random.random()))
topleft = (inputX - z, inputY - z)
for i in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
for j in xrange(max(0, topleft[1]), min(topleft[1]+(z*2), y)):
if rows[i][j] <= 255: rows[i][j] += 1
f2 заменяет внутренний цикл for на понимание списка.
def f2(x,y,n,z):
rows = [[0]*x for i in xrange(y)]
for i in range(n):
inputX, inputY = (int(x*random.random()), int(y*random.random()))
topleft = (inputX - z, inputY - z)
for i in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
l = max(0, topleft[1])
r = min(topleft[1]+(z*2), y)
rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]
ОБНОВЛЕНИЕ: f3 основано на предложении Андрея в комментариях и заменяет внешний for на map(). Мой первый взлом на это требует нескольких поисков вне локальной области, в частности рекомендуется против по Гвидо: поиск локальных переменных намного быстрее, чем поиск глобальных или встроенных переменных Я жестко закодирован все, кроме ссылки на основную структуру данных, чтобы минимизировать эти издержки.
rows = [[0]*x for i in xrange(y)]
def f3(x,y,n,z):
inputs = [(int(x*random.random()), int(y*random.random())) for i in range(n)]
rows = map(g, inputs)
def g(input):
inputX, inputY = input
topleft = (inputX - 75, inputY - 75)
for i in xrange(max(0, topleft[0]), min(topleft[0]+(75*2), 1024)):
l = max(0, topleft[1])
r = min(topleft[1]+(75*2), 1024)
rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]
UPDATE3: ChristopeD также указал на пару улучшений.
def f(x,y,n,z):
rows = [[0] * y for i in xrange(x)]
rn = random.random
for i in xrange(n):
topleft = (int(x*rn()) - z, int(y*rn()) - z)
l = max(0, topleft[1])
r = min(topleft[1]+(z*2), y)
for u in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
rows[u][l:r] = [j+(j<255) for j in rows[u][l:r]]
UPDATE4: kriss добавил несколько улучшений в f3, заменив min / max новым синтаксисом троичного оператора.
def f3b(x,y,n,z):
rn = random.random
rows = [g1(x, y, z) for x, y in [(int(x*rn()), int(y*rn())) for i in xrange(n)]]
def g1(x, y, z):
l = y - z if y - z > 0 else 0
r = y + z if y + z < 1024 else 1024
for i in xrange(x - z if x - z > 0 else 0, x + z if x + z < 1024 else 1024 ):
rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]
UPDATE5: Alex взвесил его ревизию по существу, добавив отдельную операцию map() для ограничения значений на 255 и удалив все поиски не в локальной области. Различия перфорированы нетривиальны.
def f4(x,y,n,z):
rows = [[0]*y for i in range(x)]
rr = random.randrange
inc = (1).__add__
sat = (0xff).__and__
for i in range(n):
inputX, inputY = rr(x), rr(y)
b = max(0, inputX - z)
t = min(inputX + z, x)
l = max(0, inputY - z)
r = min(inputY + z, y)
for i in range(b, t):
rows[i][l:r] = map(inc, rows[i][l:r])
for i in range(x):
rows[i] = map(sat, rows[i])
Кроме того, поскольку все мы, кажется, разбираемся с вариациями, вот мой тестовый набор для сравнения скоростей: (улучшено ChristopheD)
def timing(f,x,y,z,n):
fn = "%s(%d,%d,%d,%d)" % (f.__name__, x, y, z, n)
ctx = "from __main__ import %s" % f.__name__
results = timeit.Timer(fn, ctx).timeit(10)
return "%4.4s: %.3f" % (f.__name__, results / 10.0)
if __name__ == "__main__":
print timing(f, 1024, 1024, 400, 75)
#add more here.