Python 사전 액세스 코드 최적화
질문:
나는 내 파이썬 프로그램을 죽일 때까지 프로파일 링했으며 모든 것을 느리게하는 함수가 하나 있습니다. Python 사전을 많이 사용하므로 최선의 방법으로 사용하지 않았을 수 있습니다. 더 빨리 실행할 수 없으면 C ++로 다시 작성해야합니다. 파이썬에서 최적화하는 데 도움을 줄 수있는 사람이 있습니까?
올바른 종류의 설명을 제공하고 내 코드를 이해할 수 있기를 바랍니다. 도움을 주셔서 미리 감사드립니다.
내 코드 :
이것은 line_profiler 및 kernprof를 사용하여 프로파일 링 된 문제가되는 함수 입니다. Python 2.7을 실행하고 있습니다.
저는 특히 363, 389, 405 행과 같은 것에 당혹 스럽습니다. if두 변수를 비교 하는 문장은 너무 많은 시간이 걸리는 것 같습니다.
NumPy (희소 행렬을 사용하는 것처럼) 사용을 고려 했지만 다음과 같은 이유로 적절하지 않다고 생각합니다. (1) 정수를 사용하여 행렬을 인덱싱하지 않습니다 (객체 인스턴스를 사용하고 있습니다). (2) 행렬에 간단한 데이터 유형을 저장하지 않습니다 (float와 객체 인스턴스의 튜플을 저장하고 있습니다). 그러나 나는 NumPy에 대해 기꺼이 설득 할 의향이 있습니다. NumPy의 희소 행렬 성능과 Python의 해시 테이블에 대해 아는 사람이 있다면 관심이있을 것입니다.
죄송하지만 실행할 수있는 간단한 예제를 제공하지 않았지만이 함수는 훨씬 더 큰 프로젝트에 묶여 있으며 내 코드의 절반을주지 않고는 간단한 예제를 설정하여 테스트 할 수 없습니다. 베이스!
Timer unit: 3.33366e-10 s
File: routing_distances.py
Function: propagate_distances_node at line 328
Total time: 807.234 s
Line # Hits Time Per Hit % Time Line Contents
328 @profile
329 def propagate_distances_node(self, node_a, cutoff_distance=200):
330
331 # a makes sure its immediate neighbours are correctly in its distance table
332 # because its immediate neighbours may change as binds/folding change
333 737753 3733642341 5060.8 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
334 512120 2077788924 4057.2 0.1 use_neighbour_link = False
335
336 512120 2465798454 4814.9 0.1 if(node_b not in self.node_distances[node_a]): # a doesn't know distance to b
337 15857 66075687 4167.0 0.0 use_neighbour_link = True
338 else: # a does know distance to b
339 496263 2390534838 4817.1 0.1 (node_distance_b_a, next_node) = self.node_distances[node_a][node_b]
340 496263 2058112872 4147.2 0.1 if(node_distance_b_a > neighbour_distance_b_a): # neighbour distance is shorter
341 81 331794 4096.2 0.0 use_neighbour_link = True
342 496182 2665644192 5372.3 0.1 elif((None == next_node) and (float('+inf') == neighbour_distance_b_a)): # direct route that has just broken
343 75 313623 4181.6 0.0 use_neighbour_link = True
344
345 512120 1992514932 3890.7 0.1 if(use_neighbour_link):
346 16013 78149007 4880.3 0.0 self.node_distances[node_a][node_b] = (neighbour_distance_b_a, None)
347 16013 83489949 5213.9 0.0 self.nodes_changed.add(node_a)
348
349 ## Affinity distances update
350 16013 86020794 5371.9 0.0 if((node_a.type == Atom.BINDING_SITE) and (node_b.type == Atom.BINDING_SITE)):
351 164 3950487 24088.3 0.0 self.add_affinityDistance(node_a, node_b, self.chemistry.affinity(node_a.data, node_b.data))
352
353 # a sends its table to all its immediate neighbours
354 737753 3549685140 4811.5 0.1 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
355 512120 2129343210 4157.9 0.1 node_b_changed = False
356
357 # b integrates a's distance table with its own
358 512120 2203821081 4303.3 0.1 node_b_chemical = node_b.chemical
359 512120 2409257898 4704.5 0.1 node_b_distances = node_b_chemical.node_distances[node_b]
360
361 # For all b's routes (to c) that go to a first, update their distances
362 41756882 183992040153 4406.3 7.6 for node_c, (distance_b_c, node_after_b) in node_b_distances.iteritems(): # Think it's ok to modify items while iterating over them (just not insert/delete) (seems to work ok)
363 41244762 172425596985 4180.5 7.1 if(node_after_b == node_a):
364
365 16673654 64255631616 3853.7 2.7 try:
366 16673654 88781802534 5324.7 3.7 distance_b_a_c = neighbour_distance_b_a + self.node_distances[node_a][node_c][0]
367 187083 929898684 4970.5 0.0 except KeyError:
368 187083 1056787479 5648.8 0.0 distance_b_a_c = float('+inf')
369
370 16673654 69374705256 4160.7 2.9 if(distance_b_c != distance_b_a_c): # a's distance to c has changed
371 710083 3136751361 4417.4 0.1 node_b_distances[node_c] = (distance_b_a_c, node_a)
372 710083 2848845276 4012.0 0.1 node_b_changed = True
373
374 ## Affinity distances update
375 710083 3484577241 4907.3 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
376 99592 1591029009 15975.5 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
377
378 # If distance got longer, then ask b's neighbours to update
379 ## TODO: document this!
380 16673654 70998570837 4258.1 2.9 if(distance_b_a_c > distance_b_c):
381 #for (node, neighbour_distance) in node_b_chemical.neighbours[node_b].iteritems():
382 1702852 7413182064 4353.4 0.3 for node in node_b_chemical.neighbours[node_b]:
383 1204903 5912053272 4906.7 0.2 node.chemical.nodes_changed.add(node)
384
385 # Look for routes from a to c that are quicker than ones b knows already
386 42076729 184216680432 4378.1 7.6 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
387
388 41564609 171150289218 4117.7 7.1 node_b_update = False
389 41564609 172040284089 4139.1 7.1 if(node_c == node_b): # a-b path
390 512120 2040112548 3983.7 0.1 pass
391 41052489 169406668962 4126.6 7.0 elif(node_after_a == node_b): # a-b-a-b path
392 16251407 63918804600 3933.1 2.6 pass
393 24801082 101577038778 4095.7 4.2 elif(node_c in node_b_distances): # b can already get to c
394 24004846 103404357180 4307.6 4.3 (distance_b_c, node_after_b) = node_b_distances[node_c]
395 24004846 102717271836 4279.0 4.2 if(node_after_b != node_a): # b doesn't already go to a first
396 7518275 31858204500 4237.4 1.3 distance_b_a_c = neighbour_distance_b_a + distance_a_c
397 7518275 33470022717 4451.8 1.4 if(distance_b_a_c < distance_b_c): # quicker to go via a
398 225357 956440656 4244.1 0.0 node_b_update = True
399 else: # b can't already get to c
400 796236 3415455549 4289.5 0.1 distance_b_a_c = neighbour_distance_b_a + distance_a_c
401 796236 3412145520 4285.3 0.1 if(distance_b_a_c < cutoff_distance): # not too for to go
402 593352 2514800052 4238.3 0.1 node_b_update = True
403
404 ## Affinity distances update
405 41564609 164585250189 3959.7 6.8 if node_b_update:
406 818709 3933555120 4804.6 0.2 node_b_distances[node_c] = (distance_b_a_c, node_a)
407 818709 4151464335 5070.7 0.2 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
408 104293 1704446289 16342.9 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
409 818709 3557529531 4345.3 0.1 node_b_changed = True
410
411 # If any of node b's rows have exceeded the cutoff distance, then remove them
412 42350234 197075504439 4653.5 8.1 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can't use iteritems() here, as deleting from the dictionary
413 41838114 180297579789 4309.4 7.4 if(distance_b_c > cutoff_distance):
414 206296 894881754 4337.9 0.0 del node_b_distances[node_c]
415 206296 860508045 4171.2 0.0 node_b_changed = True
416
417 ## Affinity distances update
418 206296 4698692217 22776.5 0.2 node_b_chemical.del_affinityDistance(node_b, node_c)
419
420 # If we've modified node_b's distance table, tell its chemical to update accordingly
421 512120 2130466347 4160.1 0.1 if(node_b_changed):
422 217858 1201064454 5513.1 0.0 node_b_chemical.nodes_changed.add(node_b)
423
424 # Remove any neighbours that have infinite distance (have just unbound)
425 ## TODO: not sure what difference it makes to do this here rather than above (after updating self.node_distances for neighbours)
426 ## but doing it above seems to break the walker's movement
427 737753 3830386968 5192.0 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].items(): # Can't use iteritems() here, as deleting from the dictionary
428 512120 2249770068 4393.1 0.1 if(neighbour_distance_b_a > cutoff_distance):
429 150 747747 4985.0 0.0 del self.neighbours[node_a][node_b]
430
431 ## Affinity distances update
432 150 2148813 14325.4 0.0 self.del_affinityDistance(node_a, node_b)
내 코드에 대한 설명 :
이 함수는 (매우 큰) 네트워크의 노드 간 네트워크 거리 (가장 짧은 경로에있는 에지 가중치의 합)를 나타내는 희소 거리 매트릭스를 유지합니다. 전체 테이블로 작업하고 Floyd-Warshall 알고리즘을 사용하는 것은 매우 느립니다. (이것을 먼저 시도했는데 현재 버전보다 훨씬 더 느 렸습니다.) 그래서 내 코드는 스파 스 매트릭스를 사용하여 전체 거리 매트릭스의 임계 버전을 나타냅니다 (거리가 200 단위 이상인 모든 경로는 무시됩니다). 네트워크 토폴지는 시간이 지남에 따라 변하므로이 거리 행렬은 시간이 지남에 따라 업데이트되어야합니다. 이를 위해 거리 벡터 라우팅 프로토콜 의 대략적인 구현을 사용하고 있습니다.: 네트워크의 각 노드는 경로의 다른 노드와 다음 노드까지의 거리를 알고 있습니다. 토폴로지 변경이 발생하면이 변경과 관련된 노드가 그에 따라 거리 테이블을 업데이트하고 인접한 이웃에게 알립니다. 정보는 거리 테이블을 이웃에게 보내는 노드에 의해 네트워크를 통해 확산되며, 이들은 거리 테이블을 업데이트하고 이웃에게 전파합니다.
거리 행렬을 나타내는 객체가 있습니다 self.node_distances.. 이것은 라우팅 테이블에 노드를 매핑하는 사전입니다. 노드는 내가 정의한 객체입니다. 라우팅 테이블은 노드를 (distance, next_node)의 튜플에 매핑하는 사전입니다. 거리는 node_a에서 node_b까지의 그래프 거리이고 next_node는 node_a와 node_b 사이의 경로에서 먼저 가야하는 node_a의 이웃입니다. None의 next_node는 node_a 및 node_b가 그래프 이웃임을 나타냅니다. 예를 들어 거리 행렬의 샘플은 다음과 같습니다.
self.node_distances = { node_1 : { node_2 : (2.0, None),
node_3 : (5.7, node_2),
node_5 : (22.9, node_2) },
node_2 : { node_1 : (2.0, None),
node_3 : (3.7, None),
node_5 : (20.9, node_7)},
...etc...
토폴로지 변경으로 인해 멀리 떨어져 있거나 전혀 연결되지 않은 두 노드가 가까워 질 수 있습니다. 이 경우 항목이이 매트릭스에 추가됩니다. 임계 값으로 인해 두 노드가 너무 멀리 떨어져서 신경 쓰지 못할 수 있습니다. 이 경우 항목이이 매트릭스에서 삭제됩니다.
self.neighbours행렬은 비슷 self.node_distances하지만, 네트워크의 직접 링크 (에지)에 대한 정보를 포함한다. self.neighbours화학 반응에 의해이 기능에 대해 외부 적으로 지속적으로 수정되고 있습니다. 여기에서 네트워크 토폴로지 변경이 발생합니다.
내가 문제가있는 실제 기능 : 거리 벡터 라우팅 프로토콜propagate_distances_node() 의 한 단계를 수행 합니다 . 노드가 주어지면 node_a함수는 node_a의 이웃이 거리 행렬에 올바르게 있는지 확인합니다 (토폴로지 변경). 그런 다음이 함수는 node_a의 라우팅 테이블을 node_a네트워크에있는의 모든 인접 이웃에 보냅니다 . node_a의 라우팅 테이블을 각 이웃의 고유 라우팅 테이블과 통합 합니다.
내 프로그램의 나머지 부분에서는 propagate_distances_node()거리 행렬이 수렴 될 때까지 함수가 반복적으로 호출됩니다. self.nodes_changed마지막으로 업데이트 된 이후 라우팅 테이블을 변경 한 노드 의 집합 은 유지됩니다. 내 알고리즘의 모든 반복에서 이러한 노드의 임의의 하위 집합이 선택되어 propagate_distances_node()호출됩니다. 이것은 노드가 라우팅 테이블을 비동기 적으로 확률 적으로 분산한다는 것을 의미합니다. 이 알고리즘은 세트 self.nodes_changed가 비어 있을 때 실제 거리 행렬에 수렴합니다 .
"친 화성 거리"부분 ( add_affinityDistance및 del_affinityDistance)은 프로그램의 다른 부분에서 사용되는 거리 행렬의 (작은) 하위 행렬의 캐시입니다.
제가 이것을하는 이유는 제가 박사 과정의 일환으로 반응에 참여하는 화학 물질의 계산적 유사성을 시뮬레이션하고 있기 때문입니다. "화학 물질"은 "원자"(그래프의 노드) 그래프입니다. 함께 결합하는 두 화학 물질은 두 그래프가 새로운 모서리로 결합되는 것으로 시뮬레이션됩니다. 화학 반응이 발생하여 (여기서는 관련이없는 복잡한 프로세스에 의해) 그래프의 토폴로지가 변경됩니다. 그러나 반응에서 일어나는 일은 화학 물질을 구성하는 서로 다른 원자가 얼마나 멀리 떨어져 있는지에 달려 있습니다. 따라서 시뮬레이션의 각 원자에 대해 가까운 다른 원자를 알고 싶습니다. 희소 임계 거리 행렬은이 정보를 저장하는 가장 효율적인 방법입니다. 반응이 일어나면 네트워크의 토폴로지가 변하기 때문에 매트릭스를 업데이트해야합니다.이 작업을 할 수있는 가장 빠른 방법입니다. 라우팅 루프와 같은 일이 내 특정 애플리케이션에서 발생하지 않기 때문에 더 복잡한 라우팅 프로토콜이 필요하지 않습니다 (화학 물질이 어떻게 구조화되어 있기 때문에). 내가 확률 적으로하는 이유는 거리가 멀어지면서 화학 반응 과정을 개입시키고, 반응이 일어나면서 (즉석에서 모양이 바뀌지 않고) 시간이 지남에 따라 화학적으로 점차 모양이 변하는 것을 시뮬레이션 할 수 있기 때문입니다.
self이 함수는 화학을 나타내는 것을 목적으로한다. 의 노드 self.node_distances.keys()는 화학 물질을 구성하는 원자입니다. 의 노드 self.node_distances[node_x].keys()는 화학 물질의 노드이며 화학 물질이 결합되어 반응하는 모든 화학 물질의 노드입니다.
최신 정보:
모든 인스턴스 node_x == node_y를 node_x is node_y(@Sven Marnach의 의견에 따라)로 바꾸려고 시도했습니다.하지만 속도가 느려졌습니다! (나는 그것을 예상하지 못했습니다!) 내 원래 프로필을 실행하는 데 807.234 초가 걸렸지 만이 수정으로 895.895 초로 증가했습니다.죄송합니다. 프로파일 링을 잘못했습니다. 나는 (내 코드에서) 너무 많은 차이를 가지고있는 line_by_line을 사용하고 있었다 (약 90 초의 차이는 모두 소음에 있었다). 제대로 프로파일 링 할 때, isdetinitely보다 빠른입니다 ==. CProfile을 사용하면 내 코드 ==는 34.394 초가 걸렸지 만에서는 is33.535 초가 걸렸습니다 (내가 확인할 수있는 것은 소음이 없음).
업데이트 : 기존 라이브러리
내 요구 사항이 특이하기 때문에 원하는 작업을 수행 할 수있는 기존 라이브러리가 있는지 확실하지 않습니다. 가중, 무 방향 그래프에서 모든 노드 쌍 사이의 최단 경로 길이를 계산해야합니다. 임계 값보다 낮은 경로 길이에만 관심이 있습니다. 경로 길이를 계산 한 후 네트워크 토폴로지를 약간 변경 (에지 추가 또는 제거) 한 다음 경로 길이를 다시 계산하려고합니다. 내 그래프는 임계 값에 비해 크기가 크므로 (주어진 노드에서 대부분의 그래프가 임계 값보다 멀어짐) 토폴로지 변경은 대부분의 최단 경로 길이에 영향을주지 않습니다. 이것이 제가 라우팅 알고리즘을 사용하는 이유입니다. 이것은 그래프 구조를 통해 토폴로지 변경 정보를 퍼 뜨리기 때문에 임계 값보다 더 멀어지면 퍼지는 것을 멈출 수 있기 때문입니다. 즉, 매번 모든 경로를 다시 계산할 필요가 없습니다. 계산 속도를 높이기 위해 토폴로지 변경 전의 이전 경로 정보를 사용할 수 있습니다. 이것이 내 알고리즘이 최단 경로 알고리즘의 라이브러리 구현보다 빠르다고 생각하는 이유입니다. 물리적 네트워크를 통해 실제로 패킷을 라우팅하는 것 외에 사용되는 라우팅 알고리즘을 본 적이 없습니다 (하지만 누군가가 있다면 관심이있을 것입니다).
NetworkX 는 @Thomas K가 제안했습니다 . 최단 경로를 계산 하기 위한 많은 알고리즘 이 있습니다. 컷오프를 사용 하여 모든 쌍의 최단 경로 길이 를 계산하는 알고리즘이 있지만 (내가 원하는) 가중치가 적용되지 않은 그래프에서만 작동합니다 (내가 가중치가 적용됨). 불행히도 가중치 그래프에 대한 알고리즘 은 컷오프 사용을 허용하지 않습니다 (그래프에서 속도가 느려질 수 있음). 그리고 그 어떤 알고리즘도 매우 유사한 네트워크 (예 : 라우팅 항목)에서 미리 계산 된 경로의 사용을 지원하지 않는 것으로 보입니다.
igraph 는 내가 아는 또 다른 그래프 라이브러리이지만 문서를 보면 최단 경로에 대해 아무것도 찾을 수 없습니다. 그러나 나는 그것을 놓쳤을 수도 있습니다-그 문서는 그다지 포괄적이지 않은 것 같습니다.
@ 9000의 의견 덕분에 NumPy 가 가능할 수 있습니다. 노드의 각 인스턴스에 고유 한 정수를 할당하면 희소 행렬을 NumPy 배열에 저장할 수 있습니다. 그런 다음 노드 인스턴스 대신 정수로 NumPy 배열을 인덱싱 할 수 있습니다. 또한 두 개의 NumPy 배열이 필요합니다. 하나는 거리 용이고 다른 하나는 "next_node"참조 용입니다. 이것은 Python 사전을 사용하는 것보다 빠를 수 있습니다 (아직 모르겠습니다).
유용한 다른 라이브러리를 아는 사람이 있습니까?
업데이트 : 메모리 사용량
Windows (XP)를 실행 중이므로 여기에 Process Explorer의 메모리 사용량에 대한 정보가 있습니다. 듀얼 코어 머신이 있기 때문에 CPU 사용량이 50 %입니다.
내 프로그램은 RAM이 부족하지 않고 스왑을 시작합니다. 숫자와 IO 그래프에서 활동이없는 것을 볼 수 있습니다. IO 그래프의 스파이크는 프로그램이 화면에 인쇄하여 작동 상태를 나타내는 곳입니다.
그러나 내 프로그램은 시간이 지남에 따라 점점 더 많은 RAM을 사용하고 있으며 이는 아마도 좋은 일이 아닙니다 (그러나 전체적으로 많은 RAM을 사용하지 않기 때문에 지금까지 증가를 알아 차리지 못했습니다).
그리고 IO 그래프에서 스파이크 사이의 거리는 시간이 지남에 따라 증가합니다. 이것은 나쁘다-내 프로그램이 100,000 번 반복 될 때마다 화면에 인쇄되므로 시간이 지남에 따라 각 반복이 실행되는 데 시간이 더 오래 걸린다는 것을 의미합니다. 프로그램을 장기 실행하고 그 사이의 시간을 측정하여이를 확인했습니다. print 문 (프로그램의 각 10,000 회 반복 사이의 시간). 이것은 일정해야하지만 그래프에서 볼 수 있듯이 선형 적으로 증가합니다. (이 그래프의 노이즈는 내 프로그램이 많은 난수를 사용하기 때문에 각 반복에 대한 시간이 다양하기 때문입니다.)
내 프로그램을 오랫동안 실행 한 후 메모리 사용량은 다음과 같이 보입니다 (따라서 RAM이 부족하지 않습니다).
node_after_b == node_a전화를 시도합니다 node_after_b.__eq__(node_a):
>>> class B(object):
... def __eq__(self, other):
... print "B.__eq__()"
... return False
...
>>> class A(object):
... def __eq__(self, other):
... print "A.__eq__()"
... return False
...
>>> a = A()
>>> b = B()
>>> a == b
A.__eq__()
False
>>> b == a
B.__eq__()
False
>>>
Node.__eq__()C를 사용하기 전에 최적화 된 버전 으로 재정의하십시오 .
최신 정보
나는이 작은 실험을했다 (python 2.6.6) :
#!/usr/bin/env python
# test.py
class A(object):
def __init__(self, id):
self.id = id
class B(A):
def __eq__(self, other):
return self.id == other.id
@profile
def main():
list_a = []
list_b = []
for x in range(100000):
list_a.append(A(x))
list_b.append(B(x))
ob_a = A(1)
ob_b = B(1)
for ob in list_a:
if ob == ob_a:
x = True
if ob is ob_a:
x = True
if ob.id == ob_a.id:
x = True
if ob.id == 1:
x = True
for ob in list_b:
if ob == ob_b:
x = True
if ob is ob_b:
x = True
if ob.id == ob_b.id:
x = True
if ob.id == 1:
x = True
if __name__ == '__main__':
main()
결과 :
Timer unit: 1e-06 s
File: test.py Function: main at line 10 Total time: 5.52964 s
Line # Hits Time Per Hit % Time Line Contents
==============================================================
10 @profile
11 def main():
12 1 5 5.0 0.0 list_a = []
13 1 3 3.0 0.0 list_b = []
14 100001 360677 3.6 6.5 for x in range(100000):
15 100000 763593 7.6 13.8 list_a.append(A(x))
16 100000 924822 9.2 16.7 list_b.append(B(x))
17
18 1 14 14.0 0.0 ob_a = A(1)
19 1 5 5.0 0.0 ob_b = B(1)
20 100001 500454 5.0 9.1 for ob in list_a:
21 100000 267252 2.7 4.8 if ob == ob_a:
22 x = True
23 100000 259075 2.6 4.7 if ob is ob_a:
24 x = True
25 100000 539683 5.4 9.8 if ob.id == ob_a.id:
26 1 3 3.0 0.0 x = True
27 100000 271519 2.7 4.9 if ob.id == 1:
28 1 3 3.0 0.0 x = True
29 100001 296736 3.0 5.4 for ob in list_b:
30 100000 472204 4.7 8.5 if ob == ob_b:
31 1 4 4.0 0.0 x = True
32 100000 283165 2.8 5.1 if ob is ob_b:
33 x = True
34 100000 298839 3.0 5.4 if ob.id == ob_b.id:
35 1 3 3.0 0.0 x = True
36 100000 291576 2.9 5.3 if ob.id == 1:
37 1 3 3.0 0.0 x = True
나는 매우 놀랐습니다.
- "점"액세스 (ob.property)는 매우 비용이 많이 드는 것 같습니다 (25 행 대 27 행).
- 최소한 단순한 객체의 경우 is와 '=='사이에 큰 차이가 없었습니다.
그런 다음 더 복잡한 개체로 시도했고 결과는 첫 번째 실험과 일치합니다.
많이 바꾸 시나요? 데이터 세트가 너무 커서 사용 가능한 RAM에 맞지 않으면 가상 메모리 가져 오기와 관련된 일종의 I / O 경합이 발생할 수 있습니다.
Linux를 사용하고 있습니까? 그렇다면 프로그램을 실행하는 동안 컴퓨터의 vmstat를 게시 할 수 있습니까? 다음과 같은 결과를 보내주세요.
vmstat 10 100
행운을 빕니다!
업데이트 (OP의 의견에서)
나는 sys.setcheckinterval을 가지고 놀고 GC를 활성화 / 비활성화했습니다. 이론적 근거는이 특정 경우 (많은 인스턴스)의 경우 기본 GC 참조 카운트 검사가 다소 비싸고 기본 간격이 너무 자주 사용되지 않는다는 것입니다.
예, 이전에 sys.setcheckinterval을 사용했습니다. 기본값 인 100에서 1000으로 변경했지만 측정 가능한 차이는 없습니다. 가비지 컬렉션 비활성화가 도움이되었습니다. 감사합니다. 이것은 지금까지 가장 큰 속도 향상이었습니다. 약 20 % (전체 실행에 대해 171 분, 135 분까지)를 절약했습니다.-오차 막대가 무엇인지 확실하지 않지만 통계적으로 유의미한 증가입니다. – Adam Nellis 2 월 9 일 15:10
내 추측:
Python GC는 참조 횟수를 기반으로한다고 생각합니다. 때때로 모든 인스턴스에 대한 참조 횟수를 확인합니다. 이러한 거대한 인 메모리 구조를 순회하고 있기 때문에, 특별한 경우 GC 기본 주파수 (1000주기?)가 너무 자주 없어져서 엄청난 낭비입니다. – Yours Truly 2 월 10 일 2:06
파이썬을 C로 컴파일 한 다음 자동으로 .pyd로 컴파일하므로 많은 작업 없이도 속도가 상당히 빨라질 수 있습니다.
상당한 양의 작업이 필요하지만 ... GPU에서 실행되는 Floyd-Warshall을 사용하는 것이 좋습니다. Floyd-Warshall을 GPU에서 매우 효율적으로 실행하기 위해 많은 작업이 수행되었습니다. 빠른 Google 검색 결과 :
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://www.gpucomputing.net/?q=node/1203
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter43.html
Python으로 구현 된대로 Floyd-Warshall은 몇 배 더 느 렸지만 강력한 GPU의 우수한 GPU 버전은 여전히 새 Python 코드보다 성능이 훨씬 뛰어날 수 있습니다.
여기 일화가 있습니다. 나는 허프 축적과 비슷한 일을하는 짧고 단순하며 계산 집약적 인 코드를 가지고 있었다. 내가 얻을 수있는 한 최적화 된 Python에서는 빠른 i7에서 ~ 7 초가 걸렸습니다. 그런 다음 완전히 최적화되지 않은 GPU 버전을 작성했습니다. Nvidia GTX 480에서는 ~ 0.002 초가 걸렸습니다. YMMV,하지만 상당히 병렬적인 경우 GPU가 장기적으로 승자가 될 가능성이 높으며 잘 연구 된 알고리즘이므로 기존의 고도로 조정 된 코드를 활용할 수 있어야합니다. .
Python / GPU 브리지의 경우 PyCUDA 또는 PyOpenCL을 권장합니다.
성능과 관련하여 코드에 문제가없는 것을 알 수 있습니다 (알고리즘을 알아 내려고하지 않고), 당신은 단지 많은 수의 반복에 의해 타격을 받고 있습니다. 코드의 일부가 4 천만 번 실행 됩니다!
시간의 80 %가 코드의 20 %에서 얼마나 소비되는지 주목하세요. 그리고 이것은 2 천 4 백만 번 이상 실행되는 13 줄입니다. 그런데이 코드를 사용하면 파레토 원칙 (또는 "맥주를 마시는 사람의 20 %가 맥주의 80 %를 마신다")에 대한 훌륭한 예시를 제공 할 수 있습니다.
먼저 Psycho 를 사용해 보셨습니까 ? 이것은 코드의 속도를 크게 높일 수있는 JIT 컴파일러입니다.-많은 반복 횟수를 고려할 때-예를 들어 4x-5x의 비율로-그리고 (물론 다운로드 및 설치 후)이 스 니펫을 처음:
import psyco
psyco.full()
이것이 내가 Psycho를 좋아하고 GCJ에서도 사용했던 이유입니다. 시간이 매우 중요합니다. 코딩 할 것이없고, 잘못 될 것도없고, 2 줄에서 갑작스러운 부스트가 추가되었습니다.
nit-picking으로 돌아갑니다 ( 작은 % 시간 개선으로 인해 etc로 교체 ==하는 것과 같이 변경됨 is). 여기에 "오류가있는"13 줄이 있습니다.
Line # Hits Time Per Hit % Time Line Contents
412 42350234 197075504439 4653.5 8.1 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can't use iteritems() here, as deleting from the dictionary
386 42076729 184216680432 4378.1 7.6 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
362 41756882 183992040153 4406.3 7.6 for node_c, (distance_b_c, node_after_b) in node_b_distances.iteritems(): # Think it's ok to modify items while iterating over them (just not insert/delete) (seems to work ok)
413 41838114 180297579789 4309.4 7.4 if(distance_b_c > cutoff_distance):
363 41244762 172425596985 4180.5 7.1 if(node_after_b == node_a):
389 41564609 172040284089 4139.1 7.1 if(node_c == node_b): # a-b path
388 41564609 171150289218 4117.7 7.1 node_b_update = False
391 41052489 169406668962 4126.6 7 elif(node_after_a == node_b): # a-b-a-b path
405 41564609 164585250189 3959.7 6.8 if node_b_update:
394 24004846 103404357180 4307.6 4.3 (distance_b_c, node_after_b) = node_b_distances[node_c]
395 24004846 102717271836 4279 4.2 if(node_after_b != node_a): # b doesn't already go to a first
393 24801082 101577038778 4095.7 4.2 elif(node_c in node_b_distances): # b can already get to c
A) 당신이 언급 한 줄 외에도 # 388이 사소한 경우 상대적으로 시간이 많이 걸린다는 것을 알았습니다 node_b_update = False. 아, 잠깐만 요-실행될 때마다 False전역 범위에서 조회됩니다! 이를 방지하려면 F, T = False, True메서드의 시작 부분에 할당 하고 나중에 사용하는 False및 True을 로컬 F및 T. 이로 인해 전체 시간이 약간 줄어들지 만 (3 %?).
B) # 389의 조건이 512,120 회 (# 390의 실행 횟수 기준)와 # 391의 조건 (16,251,407)이 "만"발생한 것으로 나타났습니다. 종속성이 없기 때문에 이러한 검사의 순서를 반대로하는 것이 좋습니다. 초기 "컷"은 약간의 부스트 (2 %?)를 제공하기 때문입니다. pass모든 진술을 피하는 것이 도움이 되는지 확실 하지 않지만 가독성을 해치지 않는 경우 :
if (node_after_a is not node_b) and (node_c is not node_b):
# neither a-b-a-b nor a-b path
if (node_c in node_b_distances): # b can already get to c
(distance_b_c, node_after_b) = node_b_distances[node_c]
if (node_after_b is not node_a): # b doesn't already go to a first
distance_b_a_c = neighbour_distance_b_a + distance_a_c
if (distance_b_a_c < distance_b_c): # quicker to go via a
node_b_update = T
else: # b can't already get to c
distance_b_a_c = neighbour_distance_b_a + distance_a_c
if (distance_b_a_c < cutoff_distance): # not too for to go
node_b_update = T
C) 방금 사용 try-except하고있는 경우 (# 365-367) 사전에서 기본값이 필요하다는 것을 알았 .get(key, defaultVal)습니다 collections.defaultdict(itertools.repeat(float('+inf'))). 대신 사용 하거나 . try-except를 사용하면 가격이 책정됩니다. # 365는 3.5 %의 시간을보고하며 스택 프레임 등을 설정합니다.
D) 가능한 경우 색인화 된 액세스 (obj .필드 또는 obj [idx 사용 ])를 피하십시오. 예를 들어 내가 사용보고 self.node_distances[node_a]회 (에 한 번 사용할 때마다 사용 인덱싱하기위한 수단 여러 위치 (# 336, 339, 346, 366, 386)에서 .한 번에 []그 비싼 얻고 수십 배의 수백만의 실행시 -) . 나에게 당신은 방법 시작 부분에서 할 수 있고 그것을 node_a_distances = self.node_distances[node_a]더 사용할 수 있습니다.
나는 이것을 내 질문에 대한 업데이트로 게시했지만 Stack Overflow는 질문에 30000 자만 허용하므로 답변으로 게시하고 있습니다.
업데이트 : 지금까지 최고의 최적화
저는 사람들의 제안을 받아 들였고 이제 제 코드가 이전보다 약 21 % 더 빠르게 실행됩니다. 좋습니다. 모두에게 감사합니다!
이것은 내가 지금까지 할 수 있었던 것 중 최고입니다. @Nas Banov의 제안에 따라 모든 ==테스트 is를 노드 용으로 교체하고 가비지 수집을 비활성화하고 if388 행에 큰 문 부분을 다시 작성했습니다 . try/except테스트를 피하는 잘 알려진 트릭을 추가했습니다 (390 행-테스트 제거 node_c in node_b_distances). 예외를 거의 던지지 않기 때문에로드에 도움이되었습니다. 391 번과 392 번 줄을 바꾸고 node_b_distances[node_c]변수에 할당 해 보았지만이 방법이 가장 빠릅니다.
그러나 아직 메모리 누수를 추적하지 못했습니다 (제 질문의 그래프 참조). 그러나 이것이 내 코드의 다른 부분에있을 수 있다고 생각합니다 (여기에 게시하지 않은 부분). 메모리 누수를 고칠 수 있다면이 프로그램은 제가 사용할 수있을만큼 빠르게 실행될 것입니다. :)
Timer unit: 3.33366e-10 s
File: routing_distances.py
Function: propagate_distances_node at line 328
Total time: 760.74 s
Line # Hits Time Per Hit % Time Line Contents
328 @profile
329 def propagate_distances_node(self, node_a, cutoff_distance=200):
330
331 # a makes sure its immediate neighbours are correctly in its distance table
332 # because its immediate neighbours may change as binds/folding change
333 791349 4158169713 5254.5 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
334 550522 2331886050 4235.8 0.1 use_neighbour_link = False
335
336 550522 2935995237 5333.1 0.1 if(node_b not in self.node_distances[node_a]): # a doesn't know distance to b
337 15931 68829156 4320.5 0.0 use_neighbour_link = True
338 else: # a does know distance to b
339 534591 2728134153 5103.2 0.1 (node_distance_b_a, next_node) = self.node_distances[node_a][node_b]
340 534591 2376374859 4445.2 0.1 if(node_distance_b_a > neighbour_distance_b_a): # neighbour distance is shorter
341 78 347355 4453.3 0.0 use_neighbour_link = True
342 534513 3145889079 5885.5 0.1 elif((None is next_node) and (float('+inf') == neighbour_distance_b_a)): # direct route that has just broken
343 74 327600 4427.0 0.0 use_neighbour_link = True
344
345 550522 2414669022 4386.1 0.1 if(use_neighbour_link):
346 16083 81850626 5089.3 0.0 self.node_distances[node_a][node_b] = (neighbour_distance_b_a, None)
347 16083 87064200 5413.4 0.0 self.nodes_changed.add(node_a)
348
349 ## Affinity distances update
350 16083 86580603 5383.4 0.0 if((node_a.type == Atom.BINDING_SITE) and (node_b.type == Atom.BINDING_SITE)):
351 234 6656868 28448.2 0.0 self.add_affinityDistance(node_a, node_b, self.chemistry.affinity(node_a.data, node_b.data))
352
353 # a sends its table to all its immediate neighbours
354 791349 4034651958 5098.4 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
355 550522 2392248546 4345.4 0.1 node_b_changed = False
356
357 # b integrates a's distance table with its own
358 550522 2520330696 4578.1 0.1 node_b_chemical = node_b.chemical
359 550522 2734341975 4966.8 0.1 node_b_distances = node_b_chemical.node_distances[node_b]
360
361 # For all b's routes (to c) that go to a first, update their distances
362 46679347 222161837193 4759.3 9.7 for node_c, (distance_b_c, node_after_b) in node_b_distances.iteritems(): # Think it's ok to modify items while iterating over them (just not insert/delete) (seems to work ok)
363 46128825 211963639122 4595.0 9.3 if(node_after_b is node_a):
364
365 18677439 79225517916 4241.8 3.5 try:
366 18677439 101527287264 5435.8 4.4 distance_b_a_c = neighbour_distance_b_a + self.node_distances[node_a][node_c][0]
367 181510 985441680 5429.1 0.0 except KeyError:
368 181510 1166118921 6424.5 0.1 distance_b_a_c = float('+inf')
369
370 18677439 89626381965 4798.6 3.9 if(distance_b_c != distance_b_a_c): # a's distance to c has changed
371 692131 3352970709 4844.4 0.1 node_b_distances[node_c] = (distance_b_a_c, node_a)
372 692131 3066946866 4431.2 0.1 node_b_changed = True
373
374 ## Affinity distances update
375 692131 3808548270 5502.6 0.2 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
376 96794 1655818011 17106.6 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
377
378 # If distance got longer, then ask b's neighbours to update
379 ## TODO: document this!
380 18677439 88838493705 4756.5 3.9 if(distance_b_a_c > distance_b_c):
381 #for (node, neighbour_distance) in node_b_chemical.neighbours[node_b].iteritems():
382 1656796 7949850642 4798.3 0.3 for node in node_b_chemical.neighbours[node_b]:
383 1172486 6307264854 5379.4 0.3 node.chemical.nodes_changed.add(node)
384
385 # Look for routes from a to c that are quicker than ones b knows already
386 46999631 227198060532 4834.0 10.0 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
387
388 46449109 218024862372 4693.8 9.6 if((node_after_a is not node_b) and # not a-b-a-b path
389 28049321 126269403795 4501.7 5.5 (node_c is not node_b)): # not a-b path
390 27768341 121588366824 4378.7 5.3 try: # Assume node_c in node_b_distances ('try' block will raise KeyError if not)
391 27768341 159413637753 5740.8 7.0 if((node_b_distances[node_c][1] is not node_a) and # b doesn't already go to a first
392 8462467 51890478453 6131.8 2.3 ((neighbour_distance_b_a + distance_a_c) < node_b_distances[node_c][0])):
393
394 # Found a route
395 224593 1168129548 5201.1 0.1 node_b_distances[node_c] = (neighbour_distance_b_a + distance_a_c, node_a)
396 ## Affinity distances update
397 224593 1274631354 5675.3 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
398 32108 551523249 17177.1 0.0 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
399 224593 1165878108 5191.1 0.1 node_b_changed = True
400
401 809945 4449080808 5493.1 0.2 except KeyError:
402 # b can't already get to c (node_c not in node_b_distances)
403 809945 4208032422 5195.5 0.2 if((neighbour_distance_b_a + distance_a_c) < cutoff_distance): # not too for to go
404
405 # These lines of code copied, for efficiency
406 # (most of the time, the 'try' block succeeds, so don't bother testing for (node_c in node_b_distances))
407 # Found a route
408 587726 3162939543 5381.7 0.1 node_b_distances[node_c] = (neighbour_distance_b_a + distance_a_c, node_a)
409 ## Affinity distances update
410 587726 3363869061 5723.5 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
411 71659 1258910784 17568.1 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
412 587726 2706161481 4604.5 0.1 node_b_changed = True
413
414
415
416 # If any of node b's rows have exceeded the cutoff distance, then remove them
417 47267073 239847142446 5074.3 10.5 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can't use iteritems() here, as deleting from the dictionary
418 46716551 242694352980 5195.0 10.6 if(distance_b_c > cutoff_distance):
419 200755 967443975 4819.0 0.0 del node_b_distances[node_c]
420 200755 930470616 4634.9 0.0 node_b_changed = True
421
422 ## Affinity distances update
423 200755 4717125063 23496.9 0.2 node_b_chemical.del_affinityDistance(node_b, node_c)
424
425 # If we've modified node_b's distance table, tell its chemical to update accordingly
426 550522 2684634615 4876.5 0.1 if(node_b_changed):
427 235034 1383213780 5885.2 0.1 node_b_chemical.nodes_changed.add(node_b)
428
429 # Remove any neighbours that have infinite distance (have just unbound)
430 ## TODO: not sure what difference it makes to do this here rather than above (after updating self.node_distances for neighbours)
431 ## but doing it above seems to break the walker's movement
432 791349 4367879451 5519.5 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].items(): # Can't use iteritems() here, as deleting from the dictionary
433 550522 2968919613 5392.9 0.1 if(neighbour_distance_b_a > cutoff_distance):
434 148 775638 5240.8 0.0 del self.neighbours[node_a][node_b]
435
436 ## Affinity distances update
437 148 2096343 14164.5 0.0 self.del_affinityDistance(node_a, node_b)
참고 URL : https://stackoverflow.com/questions/4900747/optimising-python-dictionary-access-code
'development' 카테고리의 다른 글
| TaskScheduler.Current가 기본 TaskScheduler 인 이유는 무엇입니까? (0) | 2020.12.09 |
|---|---|
| typescript 파일에서 정의 파일없이 js 라이브러리를 가져 오는 방법 (0) | 2020.12.09 |
| Xcode 작업 공간에서 프로젝트 간의 종속성을 어떻게 관리해야합니까? (0) | 2020.12.09 |
| 메모리 주문 "획득"과 "소비"는 어떻게 다르며 언제 "소비"가 선호됩니까? (0) | 2020.12.09 |
| 문제 : Bob의 판매 (0) | 2020.12.09 |