C＃集合 - 按元素排序（旋轉）

我有一個IEnumerable<Point>集合。可以說它包含5點（實際上它更像2000）C＃集合 - 按元素排序（旋轉）

我想訂購這個集合，以便集合中的一個特定點成爲第一個元素，所以它基本上是在特定點上切割集合並重新連接他們在一起。

所以我的5點列表：

{0,0}, {10,0}, {10,10}, {5,5}, {0,10}

在指數3相對於元素重新排序將變成：

{5,5}, {0,10}, {0,0}, {10,0}, {10,10}

什麼是解決這一計算最爲有效的方法問題，還是有一種已經存在的內置方法...如果是這樣，我似乎無法找到一個！

來源

2011-01-10 Dr. Paul Jarvis

定義*計算效率高*。你擔心時間，記憶，什麼？您正在優化的資源是什麼，以及*您的預算*是什麼？ – 2011-01-10 15:22:09

這個問題是在一個表示地理形狀的多邊形的上下文中提出的......每個多邊形可能有一個包含多達1500個點（x，y）的PointCollection，我可能有多達30,000個多邊形。點都必須重新排序。因此，在這種情況下，計算效率非常高，意味着幾乎所有這些，內存和時間。 – 2011-01-20 11:27:15

var list = new[] { 1, 2, 3, 4, 5 }; 

var rotated = list.Skip(3).Concat(list.Take(3)); 

// rotated is now {4, 5, 1, 2, 3}

來源

2011-01-10 12:05:34 ulrichb

雖然這很簡短，但問題是「計算效率最高」。這將計算列表中的前三個元素*兩次*這是浪費的;想象一下，如果這是列表中的第一萬個元素。你能想出一個計算效率更高的解決方案嗎？ – 2011-01-10 15:21:13

在這種情況下，一個簡單的數組副本是O（n），對於幾乎所有現實世界的目的而言，這應該足夠好。但是，我會在某些情況下授予您 - 如果這是多層算法中的一部分 - 這可能是相關的。另外，你是否需要以有序的方式遍歷這個集合或創建一個副本？

鏈接列表很容易重組，像這樣，雖然訪問隨機元素將會更加昂貴。總的來說，計算效率還取決於你準確訪問這個項目集合（以及它們是什麼類型的項目 - 值類型或引用類型？）。

標準的.NET鏈表似乎並不支持這種手動操作，但一般情況下，如果你有一個鏈表，你可以按照你描述的方式輕鬆移動列表的各個部分，只需分配新的「next 「和」以前的「指向端點的指針。

此處可用的集合庫支持此功能：http://www.itu.dk/research/c5/。具體而言，您正在尋找LinkedList<T>.Slide()您可以在LinkedList<T>.View()返回的對象上使用的方法。

來源

2011-01-10 12:13:03 Sander

ulrichb顯示的Linq方法的另一種替代方法是使用隊列類（一個fifo集合）將您的索引出列，並排出已取出的那些。

來源

2011-01-10 12:17:15

版本沒有列舉list兩次，但由於T[]的更高的內存消耗：

public static IEnumerable<T> Rotate<T>(IEnumerable<T> source, int count) 
{ 
    int i = 0; 

    T[] temp = new T[count]; 

    foreach (var item in source) 
    { 
     if (i < count) 
     { 
      temp[i] = item; 
     } 
     else 
     { 
      yield return item; 
     } 

     i++; 
    } 

    foreach (var item in temp) 
    { 
     yield return item; 
    } 
} 

[Test] 
public void TestRotate() 
{ 
    var list = new[] { 1, 2, 3, 4, 5 }; 

    var rotated = Rotate(list, 3); 

    Assert.That(rotated, Is.EqualTo(new[] { 4, 5, 1, 2, 3 })); 
}

注：添加參數檢查。

來源

2011-01-10 16:06:33 ulrichb

天真實現使用LINQ是：

IEnumerable x = new[] { 1, 2, 3, 4 }; 
var tail = x.TakeWhile(i => i != 3); 
var head = x.SkipWhile(i => i != 3); 
var combined = head.Concat(tail); // is now 3, 4, 1, 2

這裏發生的是，你執行兩次，以獲得你的第一個元素組合序列中所需要的比較。該解決方案可讀性強，但效率不高。由其他貢獻者描述的解決方案可能更有效率，因爲他們使用特殊的數據結構作爲數組或列表。

來源

2011-01-10 16:42:49 fausto

C＃集合 - 按元素排序（旋轉）

回答

相關問題