根據條件對通用列表進行「拆分」的最有效和最易讀的方法是什麼？

（高度簡化的例子）我有一個字符串泛型列表：根據條件對通用列表進行「拆分」的最有效和最易讀的方法是什麼？

var strings = new List<string> { "abc", "owla", "paula", "lala", "hop" };

我在尋找最有效的方式向此列表分割成一個列表與滿足的條件和元素列表元素不符合相同的條件。

Func<string, bool> condition = s => s.IndexOf("o") > -1; 
Predicate<string> kickOut = s => s.IndexOf("o") > -1; 
var stringsThatMeetCondition = strings.Where(condition); 
strings.RemoveAll(kickOut); 
var stringsThatDontMeetCondition = strings;

有沒有辦法通過原始列表循環一次？

來源

2011-05-23 TweeZz

'Where'擴展方法調出'IEnumerable '，但'RemoveAll'是就地操作。因此，您正在比較根本不同的操作。什麼是「寫作效率」？簡潔，簡潔，容易理解？你沒有說清楚。 – spender 2011-05-23 13:23:33

要非常小心地改變你有一個非實體化查詢的列表。 LINQ的推遲性質使得這不適用（儘管你的例子*應該可以） – spender 2011-05-23 13:26:50

什麼是簡明的？什麼是簡潔？ :)（我不是母語英語）我的意思是容易閱讀/理解。我的代碼現在是否正確？ – TweeZz 2011-05-23 13:31:49

這將做到這一點：

IEnumerable<T> FilterAndRemove(this List<T> list, Func<T, bool> pred) 
{ 
    List<T> filtered = new List<T>(); 
    int i = 0; 
    while(i < list.Count) 
    { 
    if (pred(list[i])) 
    { 
     filtered.Add(list[i]); 
     list.RemoveAt(i); 
    } 
    else 
    { 
     ++i; 
    } 
    } 
    return list; 
}

，但我相信你已經想到了類似的事情。你能否以你尋求的那種效率來更新你的答案？

請注意，在原始列表上運行pred和!pred的兩個篩選仍然是O（n），而且根本沒有效率。特別是考慮到你會得到兩個結果集的延遲評估的全部好處。另見羅布的回答。

該算法在O（n^2）中。

除了刪除每個元素，您還可以將它們收集到一個新列表中，並在返回之前將它們複製到輸入列表中。這也會讓你O（n）。

O（n）的另一個選項是切換到鏈表。

來源

2011-05-23 13:36:45 TheFogger

已更新的問題 – TweeZz 2011-05-23 13:53:40

我很想去這個..是否正確它只是循環一次原始列表？ – TweeZz 2011-05-23 14:23:24

@TweeZz是的，它只循環一次，但是請注意'將RemoveAt（i）'撞到O（n^2）的算法。我發佈了這個答案，因爲它完全符合你的示例代碼的含義，這意味着它會改變列表。我個人會喜歡Rob或Snowbear JIM編譯器的答案。你的代碼的用例是什麼，它爲什麼對性能至關重要？ – TheFogger 2011-05-23 15:31:17

使用一些LINQ：

var matches = list.Select(s => s.IndexOf("o") > -1).ToList(); 
var notMatches = list.Except(matches).ToList(); 
list.Clear(); 
list.AddRange(matches);

更新：正如在評論中提到的，要小心變異列表爲LINQ方法儘量點播，他們不會迭代列表，直至開始尋找IEnumerable。但在我的情況下，我打電話ToList，這有效地導致它貫穿整個項目列表。

來源

2011-05-23 13:22:49

選擇只是返回一個列表，對不對？它是否也修改原始列表實例？我的意思是我需要結束2列表。這會給我一個符合條件和原始列表的項目清單，對嗎？ – TweeZz 2011-05-23 13:24:14

選擇*不*返回一個列表。它返回一個IEnumerable ' – spender 2011-05-23 13:25:27

不，只返回一個IEnumerable。你需要改變原來的？ – 2011-05-23 13:25:29

爲什麼不直接使用

var stringsThatMeetCondition = strings.Where(condition); 
var stringsThatDontMeetCondition = strings.Where(x => !condition(x));

當然，你最終在應用列表中的狀態，以每個元素的兩倍。爲了避免這種情況，你可能想寫一個通用的分割函數，它不會那麼整齊。

來源

2011-05-23 13:39:46 Rob

+1這是我認爲最好的方式，除非性能表明否則。 – TheFogger 2011-05-23 13:42:25

Func<string, bool> condition = ...; 
var groupedStrings = strings.GroupBy(condition) 
var stringsMeetingCondition = groupedStrings.FirstOrDefault(g => g.Key); 
var stringsNotMeetingCondition = groupedStrings.FirstOrDefault(g => !g.Key);

來源

2011-05-23 13:42:39 Snowbear

根據條件對通用列表進行「拆分」的最有效和最易讀的方法是什麼？

回答

相關問題