與集合比較時確定添加和刪除項目的最佳算法

Question

我在尋找最佳算法來比較2個集合，並確定哪些元素已添加以及哪些元素已刪除。

private string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement, ICollection<UserInvolvement> oldInvolvement) 
{ 
    //I defined the new and old dictionary's for you to know what useful data is inside UserInvolvement. 
    //Both are Dictionary<int, int>, because The Involvement is just a enum flag. Integer. UserId is also Integer. 
    var newDict = newInvolvement.ToDictionary(x => x.UserID, x => x.Involvement); 
    var oldDict = oldInvolvement.ToDictionary(x => x.UserID, x => x.Involvement); 

    //I Want to compare new to old -> and get 2 dictionaries: added and removed. 
    var usersAdded = new Dictionary<int, Involvement>(); 
    var usersRemoved = new Dictionary<int, Involvement>(); 

    //What is the best algoritm to accomplish this? 

    return GetInvolvementLogging(usersAdded, usersRemoved); 
} 

private string GetInvolvementLogging(Dictionary<int, Involvement> usersAdded, Dictionary<int, Involvement> usersRemoved) 
{ 
    //TODO: generate a string based on those dictionaries. 
    return "Change in userinvolvement: "; 
} 

Answer 1

最後，這是我的實施GetInvolvementLogging：

（這裏的字符串生成器方法的實現與我的問題無關）

private string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement, ICollection<UserInvolvement> oldInvolvement) 
{ 
    //I defined the new and old dictionary's to focus on the relevant data inside UserInvolvement. 
    var newDict = newInvolvement.ToDictionary(x => x.UserID, x => (Involvement)x.Involvement); 
    var oldDict = oldInvolvement.ToDictionary(x => x.UserID, x => (Involvement)x.Involvement); 

    var intersection = newDict.Keys.Intersect(oldDict.Keys); //These are the id's of the users that were and remain involved. 
    var usersAdded = newDict.Keys.Except(intersection); 
    var usersRemoved = oldDict.Keys.Except(intersection); 

    var addedInvolvement = newDict.Where(x => usersAdded.Contains(x.Key)).ToDictionary(x => x.Key, x => x.Value); 
    var removedInvolvement = oldDict.Where(x => usersRemoved.Contains(x.Key)).ToDictionary(x => x.Key, x => x.Value); 

    //Check if the already involved users have a changed involvement. 
    foreach(var userId in intersection) 
    { 
     var newInvolvementFlags = newDict[userId]; 
     var oldInvolvementFlags = oldDict[userId]; 

     if ((int)newInvolvementFlags != (int)oldInvolvementFlags) 
     { 
      var xor = newInvolvementFlags^oldInvolvementFlags; 
      var added = newInvolvementFlags & xor; 
      var removed = oldInvolvementFlags & xor; 

      if (added != 0) 
      { 
       addedInvolvement.Add(userId, added); 
      } 
      if (removed != 0) 
      { 
       removedInvolvement.Add(userId, removed); 
      } 
     } 
    } 

    return GetInvolvementLogging(addedInvolvement, removedInvolvement); 
} 

Answer 2

添加元素只有在newDict去除僅在oldDict

var intersection = newDict.Keys.Intersect(oldDict.Keys); 

var added = newDict.Keys.Except(intersection); 
var removed = oldDict.Keys.Except(intersection); 

編輯

我修改你的基地功能，字典是沒有neded。

例UserInvolvement實施

class UserInvolvement 
{ 
    public int UserId; 
    public string Name; 
    public string OtherInfo; 

    public override bool Equals(object obj) 
    { 
     if (obj == null) 
     { 
      return false; 
     } 

     UserInvolvement p = obj as UserInvolvement; 
     if ((System.Object)p == null) 
     { 
      return false; 
     } 

     return (UserId == p.UserId) && (Name == p.Name) && (OtherInfo == p.OtherInfo); 
    } 

    public override string ToString() 
    { 
     return $"{UserId} - {Name} - {OtherInfo}"; 
    } 
} 

而且例如功能：

private static string GetInvolvementLogging(ICollection<UserInvolvement> newInvolvement, 
      ICollection<UserInvolvement> oldInvolvement) 
{ 
    var intersection = newInvolvement.Select(x => x.UserId).Intersect(oldInvolvement.Select(x => x.UserId)); 
    var addedIds = newInvolvement.Select(x => x.UserId).Except(intersection); 
    var removedIds = oldInvolvement.Select(x => x.UserId).Except(intersection); 

    List<UserInvolvement> modifiedUI = new List<UserInvolvement>(); 

    foreach (var i in intersection) 
    { 
     var ni = newInvolvement.First(a => a.UserId == i); 
     var oi = oldInvolvement.First(a => a.UserId == i); 

     if (!ni.Equals(oi)) 
     { 
      modifiedUI.Add(ni);     
     } 
    } 

    List<UserInvolvement> addedUI = newInvolvement.Where(x => addedIds.Contains(x.UserId)).Select(w => w).ToList(); 
    List<UserInvolvement> removedUI = oldInvolvement.Where(x => removedIds.Contains(x.UserId)).Select(w => w).ToList(); 

    StringBuilder sb = new StringBuilder(); 

    sb.AppendLine("Added"); 
    foreach (var added in addedUI) 
    { 
     sb.AppendLine(added.ToString());     
    } 
    sb.AppendLine("Removed"); 
    foreach (var removed in removedUI) 
    { 
     sb.AppendLine(removed.ToString()); 
    } 
    sb.AppendLine("Modified"); 
    foreach (var modified in modifiedUI) 
    { 
     sb.AppendLine(modified.ToString()); 
    } 

    return sb.ToString(); 
} 

而我的測試功能：

static void Main(string[] args) 
{ 
    List<UserInvolvement> newUI = new List<UserInvolvement>() 
    { 
     new UserInvolvement() 
     { 
      UserId = 1, 
      Name = "AAA", 
      OtherInfo = "QQQ" 
     }, 
     new UserInvolvement() 
     { 
      UserId = 2, 
      Name = "BBB", 
      OtherInfo = "123" 
     }, 
     new UserInvolvement() 
     { 
      UserId = 4, 
      Name = "DDD", 
      OtherInfo = "123ert" 
     } 


    }; 

    List<UserInvolvement> oldUI = new List<UserInvolvement>() 
    { 
     new UserInvolvement() 
     { 
      UserId = 2, 
      Name = "BBBC", 
      OtherInfo = "123" 
     }, 
     new UserInvolvement() 
     { 
      UserId = 3, 
      Name = "CCC", 
      OtherInfo = "QQ44" 
     }, 
     new UserInvolvement() 
     { 
      UserId = 4, 
      Name = "DDD", 
      OtherInfo = "123ert" 
     } 

    }; 

    string resp = GetInvolvementLogging(newUI, oldUI); 
    WriteLine(resp); 

    ReadKey(); 

    WriteLine("CU"); 
} 

結果是：

Added 
1 - AAA - QQQ 
Removed 
3 - CCC - QQ44 
Modified 
2 - BBB - 123 

Answer 3

您可以嘗試使用LINQ：

var usersAdded = newDict.Except(oldDict); 
var usersRemoved = oldDict.Except(newDict); 

如果需要字典，結果你可以施放：

var usersAdded = newDict.Except(oldDict).ToDictionary(x => x.Key, x => x.Value); 
var usersRemoved = oldDict.Except(newDict).ToDictionary(x => x.Key, x => x.Value); 

Answer 4

認爲最好的算法將是

foreach (var newItem in newDict)  
    if (!oldDict.ContainsKey(newItem.Key) || oldDict[newItem.Key]!=newItem.Value) 
     usersAdded.Add(newItem.Key, newItem.Value); 

foreach (var oldItem in oldDict) 
    if (!newDict.ContainsKey(oldItem.Key) || newDict[oldItem.Key]!=oldItem.Value) 
     usersRemoved.Add(oldItem.Key, oldItem.Value);