Cách nhanh hơn để thực hiện Danh sách <T> .Contains()

Question

Tôi đang cố gắng làm những gì tôi nghĩ là "không giao nhau" (tôi không chắc tên đúng là gì, nhưng đó là những gì Tim Sweeney của EpicGames gọi nó là trong UnrealEd cũ)

// foo and bar have some identical elements (given a case-insensitive match) 
List‹string› foo = GetFoo(); 
List‹string› bar = GetBar(); 

// remove non matches 
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 

Sau đó, tôi làm một việc khác mà tôi trừ kết quả từ bản gốc để xem phần nào tôi đã xóa. Đó là siêu nhanh bằng cách sử dụng .Except(), do đó, không có rắc rối ở đó.

Phải có cách nhanh hơn để thực hiện việc này, vì điều này có hiệu suất kém với ~ 30.000 phần tử (của chuỗi) trong Danh sách. Tốt hơn là, một phương pháp để thực hiện bước này và một phương pháp sau này trong một lần giảm sẽ là tốt đẹp. Tôi đã thử sử dụng .Exists() thay vì .Contains(), nhưng nó hơi chậm hơn. Tôi cảm thấy một chút dày, nhưng tôi nghĩ rằng nó nên có thể với một số sự kết hợp của .Except() và .Intersect() và/hoặc .Union().

Answer 1

Với giao nhau nó sẽ được thực hiện như thế này:

var matches = ((from f in foo 
       select f) 
       .Intersect(
        from b in bar 
        select b, StringComparer.InvariantCultureIgnoreCase)) 

Answer 2

Thao tác này có thể được gọi là sự khác biệt đối xứng.

Bạn cần cấu trúc dữ liệu khác, như bảng băm. Thêm giao điểm của cả hai bộ vào nó, sau đó khác biệt giao điểm từ mỗi bộ.

UPDATE:

Tôi có một chút thời gian để thử điều này trong mã. Tôi đã từng HashSet<T> với một bộ 50.000 chuỗi, 2-10 ký tự dài với kết quả như sau:

gốc: 79.499 ms

Hashset: 33 ms

BTW , có một phương pháp trên HashSet gọi là SymmetricExceptWith mà tôi nghĩ sẽ làm công việc cho tôi, nhưng nó thực sự thêm các phần tử khác nhau từ cả hai tập hợp vào tập hợp phương thức được gọi. Có lẽ đây là những gì bạn muốn, thay vì để lại hai bộ ban đầu chưa sửa đổi, và mã sẽ thanh lịch hơn.

Đây là mã:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // foo and bar have some identical elements (given a case-insensitive match) 
     var foo = getRandomStrings(); 
     var bar = getRandomStrings(); 

     var timer = new Stopwatch(); 

     timer.Start(); 
     // remove non matches 
     var f = foo.Where(x => !bar.Contains(x)).ToList(); 
     var b = bar.Where(x => !foo.Contains(x)).ToList(); 
     timer.Stop(); 

     Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds)); 

     timer.Reset(); 

     timer.Start(); 
     var intersect = new HashSet<String>(foo); 
     intersect.IntersectWith(bar); 

     var fSet = new HashSet<String>(foo); 
     var bSet = new HashSet<String>(bar); 

     fSet.ExceptWith(intersect); 
     bSet.ExceptWith(intersect); 
     timer.Stop(); 

     var fCheck = new HashSet<String>(f); 
     var bCheck = new HashSet<String>(b); 

     Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds)); 

     Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set)); 
     Console.ReadKey(); 
    } 

    static Random _rnd = new Random(); 

    private const int Count = 50000; 

    private static List<string> getRandomStrings() 
    { 
     var strings = new List<String>(Count); 

     var chars = new Char[10]; 

     for (var i = 0; i < Count; i++) 
     { 
      var len = _rnd.Next(2, 10); 

      for (var j = 0; j < len; j++) 
      { 
       var c = (Char)_rnd.Next('a', 'z'); 
       chars[j] = c; 
      } 

      strings.Add(new String(chars, 0, len)); 
     } 

     return strings; 
    } 
} 

Answer 3

Có tên trong danh sách là một O (N) hoạt động. Nếu bạn có cấu trúc dữ liệu khác, chẳng hạn như danh sách được sắp xếp hoặc từ điển, bạn sẽ giảm đáng kể thời gian của mình. Việc truy cập một khóa trong một danh sách được sắp xếp thường là thời gian O (log N), và trong một băm thường là thời gian O (1).

Answer 4

Nếu các phần tử là duy nhất trong mỗi danh sách mà bạn nên xem xét sử dụng một HashSet

Các HashSet (T) lớp cung cấp cao hoạt động hiệu quả đề ra. Tập hợp là bộ sưu tập không chứa các thành phần trùng lặp và có các thành phần không theo thứ tự thứ tự cụ thể.

Answer 5

Với danh sách được sắp xếp, bạn có thể sử dụng tìm kiếm nhị phân.