修改列表中的項目<T> fast

我試圖使用Parallel.ForEach和ConcurrentBag更快地執行代碼，但它仍然運行的時間很長（特別是在考慮到在我的場景中我也可能是1.000.000 ++ ）：修改列表中的項目<T> fast

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

描述你想達到什麼目的。即使對於N> = 20000，O（N^2）也太多了。 – 2011-04-30 19:31:51

如果你真的要在你的集合中有超過一百萬個項目，你可能想要開始尋找比嵌套循環更好的搜索算法......是否將它分散到少數幾個並行化的核心，它仍然會是10^12次迭代，這是很多的（你會意識到，這將刪除，例如，一個點的線，無論多長時間，只要點是彼此足夠接近，對吧？） – 2011-04-30 19:32:22

我需要在每個_X_上使用__ __ __ __ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _點所有點，而_X_可以與x 1-x 2 2011-04-30 19:37:57

由於數據訪問模式，該代碼將並行執行WORSE。

加速它的最好方法是認識到你不需要考慮所有的O（N^2）對點，但只有那些具有附近X座標的點。

首先，按X座標排序列表O（N log 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

感謝本，這是訣竅！非常快速和正確。感謝所有其他人爲我指出了正確的方向。 – 2011-04-30 22:14:48

嗯，我不知道你想要什麼，但讓我們試試。

首先，創建列表時，您可能需要設置所需的初始大小，因爲您知道它將容納多少個項目。所以它不需要一直增長。

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

接下來，您可以通過X屬性對列表進行排序。所以你只能比較每個點和它附近的點：當你發現第一個點，向前或向後，太遠時，你可以停止比較。

來源

2011-04-30 19:38:48 Gabriel

修改列表中的項目<T> fast

回答

相關問題