So sánh hai IEnumerable để phát hiện các thay đổi

Question

Đối với bài đăng đầu tiên của tôi ở đây, tôi có một câu hỏi liên quan đến so sánh IEnumerable. Tôi có cấu trúc có thể ràng buộc dựa trên logic đếm. Nội dung của các thay đổi IEnumerable theo thời gian và tôi phải tự bắn các sự kiện CollectionChanged.

Tôi có một thuật toán rất ngây thơ cho phép tôi phát hiện các thay đổi đơn giản giữa hai trạng thái của IEnumerable (đơn giản thêm, loại bỏ đơn giản, nhiều bổ sung, nhiều loại bỏ) nhưng nó không phải là rất hiệu quả và không phát hiện tất cả mọi thứ.

Một ví dụ nhanh về những gì tôi cần:

Nhà nước 1 của IEnumerable: A * B * C * D * E

Nhà nước 2 của IEnumerable: A * C * B * D * D1

Đối với ví dụ này, tôi sẽ phải phát hiện

• Một hoạt động di chuyển: B thay đổi chỉ số 1-2
• Một Add hoạt động: D1 được chèn vào index 4
• Một hoạt động remove: E đã được gỡ bỏ

Có một thuật toán để giải quyết vấn đề này một cách hiệu quả càng tốt (O (nLog (n)) sẽ là một khởi đầu tốt)?

Cảm ơn!

Answer 1

Đây là uncompiled, mã psuedo chưa được kiểm tra và rút gọn.

Cho một phát hiện động thái duy nhất là đủ Items chỉ có thể di chuyển về phía trước, di chuyển về phía sau sẽ là kết quả của một mục được di chuyển hoặc loại bỏ

ví dụ Nhà nước 1 của IEnumerable: A * B * C * D * E

Nhà nước 2 của IEnumerable: A * D * B * C * D1

quả trong cả B và C di chuyển về phía trước.

enum1pos = -1; 
enum2pos = 0; 
    Value2 = enum2.Next() 
    enum2pos++; 
List<int> SkipList = new SkipList(); 
while(enum1 has values left) 
{ 
    Value1 = enum1.Next() 
    enum1pos++; 
    //Skip over moved items. 
    while (SkipList.Count > 0 && SkipList[0] == enum2.Position) 
    { 
    Value2 = enum2.Next() 
    enum2pos++; 
    } 
    if (Value1 == Value2) 
    Value2 = enum2.Next() 
    enum2pos++; 
    continue; 

    int temp = enum2pos; 
    while(Value1 !=Value and enum2 has more values) 
    { 
    Value2 = enum2.Next(); 
    enum2pos++; 
    } 
    if(Value1 != Value2) 
    ItemDeleted(Value1); 
    else 
    { 
    ItemMoved(Value1, enum2pos); 
    SkipList.Add(enum2pos); 
    } 
    //This is expensive for IEnumerable! 
    enum2.First(); 
    loop temp times 
    enum2.Next(); 
    //if 
} 
while (enum2 has values left) 
{ 
    while (SkipList.Count > 0 && SkipList[0] == enum2.Position) 
    { 
    Value2 = enum2.Next() 
    enum2pos++; 
    } 
    if (enum2 has values left) 
    Added(Value2, enum2pos) 
} 

Kết quả: Hãy so sánh A và A
Tiếp
So sánh B và D
Find B
B Moved -> 2
Thêm 2 đến Bỏ qua Danh sách
Đặt lại Enum2
So sánh C và D
Tìm C
C Đã di chuyển -> 3
Thêm 3 vào Bỏ qua Danh sách
Đặt lại Enum2
Tiếp
Hãy so sánh D và D
Tiếp
Skip (2)
Skip (3)
Hãy so sánh E và D1
Tìm E
Removed (E)
Tiếp
Kết thúc của Enum1 Đã thêm (D1,4)

Tôi nghĩ rằng có một khoản tiết kiệm ở đâu đó nếu enum2pos được quá xa phía sau để xem nếu nó đã được gỡ bỏ và nếu nó đã không thêm một bỏ qua cho vị trí ban đầu của nó trong enum1, điều này sẽ giúp với vị trí của enum2 được thiết lập lại tất cả các thời gian.

Answer 2

Nếu bạn thích sử dụng LINQ, đây là một giải pháp đơn giản dựa trên ví dụ của bạn .. Xin lỗi nhưng không chắc chắn về việc thực hiện ..

var a = new List<string>{"A","B","C","D","E"}; 
var b = new List<string>{"A","C","B","D","D1"}; 

var removed = a.Except(b); 
var moved = a.Where(x => b[a.IndexOf(x)] != x && !removed.Contains(x)); 
List<string> newlyInserted = new List<string>(); 
foreach (var item in removed) 
{ 
    //Newly inserted into the list - D1 
    newlyInserted.Add(b[a.IndexOf(item)]); 
    //Index of D1 if required 
    var indexOfNewlyAddedItem = a.IndexOf(item); 
} 

hoặc đơn giản là

var newlyAdded = b.Except(a);