2
다음 문제의 파이썬 순환 오버 헤드에 대한 도움이 필요합니다. 2D Numpy 배열에서 고전적인 동적 프로그래밍 알고리즘 인 픽셀 흐름 알고리즘을 계산하는 함수를 작성하고 있습니다. 그것은 필요 같이 적어도 한번 상기 어레이의 모든 요소를 방문numpy로 동적 프로그래밍을 할 때 Python 루프 오버 헤드를 피할 수 있습니까?
1)
for x in range(xsize):
for y in range(ysize):
updateDistance(x,y)
2) 잠재적 보이는 요소의 이웃의 값에 따라 소자의 경로를 따라 이
while len(workingList) > 0:
x,y = workingList.pop()
#if any neighbors of x,y need calculation, push x,y and neighbors on workingList
#else, calculate flow on pixels as a sum of flow on neighboring pixels
은 불행히도, 난 updateDistance에 대한 호출이 pass 경우에도 # 1에 파이썬 루프 오버 헤드를 많이 받고있는 것으로 보인다. 나는이 알고리즘이 파이썬에서 루핑 오버 헤드를 피할 수있는 좋은 접근 방식이어야한다는 고전적인 충분한 알고리즘이라고 생각한다. 나는 # 1을 고칠 수 있다면 # 2의 루프에서 파열 될 것이라고 걱정한다.
2D numpy 배열의 요소를 신속하게 반복하고 해당 배열의 요소 체인을 잠재적으로 업데이트하는 방법에 대한 제안 사항이 있습니까?
편집 : # 2
의 자세한 내용을 비우기 내가 아마도 np.meshgrid 전화를 벡터화와 함께 첫 번째 루프를 벡터화 할 수있을 것 같다.
루프의 일부는 약간 복잡하지만 여기서는 단순화 된 버전입니다. 루프와 이웃 요소에 대한 색인 생성에 대해 걱정하고 있습니다.
#A is a 2d cost matrix
workingList = [(x,y)]
while len(workingList) > 0:
x,y = workingList.pop()
neighborsToCalculate = []
for n in neighborsThatNeedCalculation(x,y): #indexes A to check neighbors of (x,y)
neighborsToCalculate.append(n)
if len(neighborstToCalculate) != 0:
workingList.append((x,y))
workingList.extend(neighborsToCalculate)
else:
for xn,yn in neighbors(x,y):
A[x,y] += 1+A[xn,yn]
이것은 일반적인 너비 우선 검색 문제입니다. 이것이 병렬화 될 수 있다면 좋을 것입니다. 그것은 경로를 따르기 때문에 아마도 현재 형태로는 될 수 없지만, 나는 제안을 기뻐할 것입니다.
두 번째 루프에 대한 자세한 내용을 게시 할 수 있습니까? – Simon
@Simon 예, 저는 그것을 좀 더 구체화 시켰습니다. – Rich