C에서 큰 데이터에 대한 루프 속도 향상 #

Question

0부터 n까지 세 개의 중첩 루프가 있습니다. n은 12000 번째 쯤되는 큰 수입니다. 2DList에서 작동하는이 세 개의 루프. 실제로 Floyd 알고리즘입니다. 이러한 대용량 데이터는 시간이 오래 걸립니다. 어떻게 향상시킬 지 조언 해 주시겠습니까?

List<List<int>> distance = new List<List<int>>(); 

... 

    for (int i = 0; i < n; i++) 

     for (int v = 0; v < n; v++) 

      for (int w = 0; w < n; w++) 
      { 
       if (distance[v][i] != int.MaxValue && 
        distance[i][w] != int.MaxValue) 
       { 
        int d = distance[v][i] + distance[i][w]; 
        if (distance[v][w] > d) 
         distance[v][w] = d; 
       } 

      } 

Answer 1

은 일반적으로 내가 병렬 Linq에를 사용하는 것이 좋습니다 것 (:) 내 영어 죄송합니다) 감사합니다 - 예를 들어 Ray Tracer 예를 들어, 그러나 이것은 당신이에 운영하고있는 항목이 독립적이라고 가정합니다. 귀하의 예에서는 이전 반복의 결과를 현재 사용하고 있으므로 병렬 처리가 불가능합니다.

코드가 매우 간단하고 실제로 오버 헤드가 없기 때문에 속도를 높이기 위해 할 수있는 일은 실제로 없습니다. 언급 한 바와 같이 목록을 배열로 전환 할 수 있습니다. 대상 시스템에서 Double 산술을 정수 산술과 비교할 수도 있습니다.

Answer 2

Floyd의 알고리즘은 변경할 수 없으며 복잡도는 고정되어 있습니다 (부정적인 가장자리 가중치가있는 그래프에서 모든 쌍 방향 최단 경로 거리를 찾는 일반적인 문제에 대한 가장 효율적인 해결책 일 수 있음).

문제를보다 구체적으로 또는 데이터 세트를 더 작게 만 설정하면 런타임을 향상시킬 수 있습니다. 일반적인 솔루션의 경우 보유하고있는 것에 매달 리게됩니다.

Answer 3

if 문 distance[v][i] != int.MaxValue의 첫 번째 부분은 일부 경우 오버 헤드를 줄이기 위해 w 이상의 반복에서 이동할 수 있습니다. 그러나 나는 당신의 값이 얼마나 자주 int에 있는지 모른다. MaxValue

Answer 4

다른 사람들이 언급했듯이 복잡성은 고정되어 있으므로 거기에 많은 옵션이 없다. 그러나 사용할 수 있습니다

• 가능한 경우 목록 대신 배열을 사용하십시오.
• pointersemantics가있는 "안전하지 않은"블록을 사용하면 배열 데이터에 액세스하는 데 필요한 시간이 단축됩니다.
• 알고리즘을 병렬 처리 할 수 ​​있는지 확인하십시오. 귀하의 경우 데이터의 여러 사본 (여러 복사본을 사용하여 동기화의 필요성을 제거 할 수 있음)과 여러 스레드가 작동 할 수 있습니다 (예 : 바깥 고리의 범위를 일부 하위 범위 (1-1000, 1001-2000 예를 들면). 코드에서 간단한 살펴 후

Answer 5

, 조건 검사를 차단 할 수 없을 것입니다 당신이하는 오버플로 향하고 수 있습니다 것으로 보인다. 코드에서

, 조건을 거리 [v] [i] + 거리 [i] [w]> Int가 될 수 있기 때문에 아래에 값을 추가하지 않습니다. .Max 값.

if (distance[v][i] != int.MaxValue && distance[i][w] != int.MaxValue)