목록의 항목을 수정하십시오 <T> 빨리

이 코드를 Parallel.ForEach 및 ConcurrentBag를 사용하여 더 빠르게 수행하려고했지만 여전히 길게 실행 중입니다 (특히 내 시나리오에서 1.000.000 ++ 일 수 있음).) :목록의 항목을 수정하십시오 <T> 빨리

List<Point> points = new List<Point>(); 
for(int i = 0; i<100000;i++) { 
    Point point = new Point {X = i-50000, Y = i+50000, CanDelete = false}; 
    points.Add(point); 
} 

foreach (Point point in points) { 
    foreach (Point innerPoint in points) { 
     if (innerPoint.CanDelete == false && (point.X - innerPoint.X) < 2) { 
      innerPoint.Y = point.Y; 
      point.CanDelete = true; 
     } 
    } 
}

출처

2011-04-30 Alexander Zeitler

달성하려는 내용을 기술하십시오. O (N^2)는 'N> = 20000'일 때 너무 깁니다. –

컬렉션에있는 항목이 100 만 개가 넘는 경우 중첩 루프보다 더 나은 검색 알고리즘을 살펴 보는 것이 좋습니다. 병렬화 여부에 상관없이 몇 가지 코어에 퍼뜨릴 지 여부는 계속됩니다. 10^12 반복이 될 것입니다. 많은 점이 있습니다 (예를 들어 얼마나 오랫동안 포인트가 삭제 되더라도 포인트가 서로 충분히 가깝기 만하면 삭제됩니다). –

각 _X_에 최대 _Y_가있는 _points_의 모든 점을 가져와야하고 _X_은 x1-x2 <허용차와 구별 할 수 있어야합니다. 내 가치는 데모 데이터에 불과합니다. 실제 값은 다르지만 목록 크기는 비슷합니다. –

해당 코드는 데이터 액세스 패턴으로 인해 WORSE를 병렬로 수행합니다.

속도를 높이는 가장 좋은 방법은 모든 O (N^2) 쌍의 점을 고려할 필요가 없으며 가까운 X 좌표가있는 점만 고려해야한다는 것을 인식하는 것입니다.

먼저 X 좌표, O (N 로그 N)로 목록을 정렬 한 다음 이웃을 떠날 때까지 각 지점의 목록에서 앞뒤로 처리합니다. foreach이 아닌 색인 생성을 사용해야합니다.

샘플 데이터 인 경우 목록이 이미 정렬되어 있습니다.

거리 테스트가 대칭이므로 검토에서 일치하는 포인트가 제거되므로 이전 포인트를 건너 뛸 수 있습니다.

for (int j = 0; j < points.Length; ++j) { 
    int x1 = points[j].X; 
    //for (int k = j; k >= 0 && points[k].X > x1 - 2; --k) { /* merge points */ } 
    for (int k = j + 1; k < points.Length && points[k].X < x1 + 2; ++k) { /* merge points */ } 
}

복잡성이 더할뿐만 아니라 캐시 동작이 훨씬 뛰어납니다. 또한 캐시 경합이 훨씬 적은 여러 스레드로 분할 될 수 있습니다.

출처

2011-04-30 19:36:06

감사합니다. Ben,이 트릭을 했어! 매우 빠르고 정확합니다. 다른 모든 사람들에게도 올바른 방향으로 나를 가리켜 주셔서 감사합니다. –

글쎄, 나는 당신이 원하는 것을 정확히 모른다. 그러나 시도해 보자.

먼저 List를 만들 때 보유 할 항목의 수를 알고 있으므로 원하는 초기 크기로 설정할 수 있습니다. 따라서 항상 성장할 필요는 없습니다.

List<Point> points = new List<Point>(100000);

다음으로 X 속성으로 목록을 정렬 할 수 있습니다. 따라서 각 점을 근처에있는 점과 비교하면됩니다. 첫 번째, 앞 또는 뒤로, 너무 먼 거리를 찾으면 비교를 멈출 수 있습니다.

출처

2011-04-30 19:38:48 Gabriel

목록의 항목을 수정하십시오 <T> 빨리

답변

관련 문제