IList에서 여러 항목을 제거하는 가장 효율적인 방법 <T>

Question

IList<T> 개체에서 여러 항목을 제거하는 가장 효율적인 방법은 무엇입니까? 원래 목록에서와 동일한 순서로 제거하려는 모든 항목 중 IEnumerable<T>이 있다고 가정합니다.

IList<T> items; 
IEnumerable<T> itemsToDelete; 
... 

foreach (var x in itemsToDelete) 
{ 
    items.Remove(x); 
} 

그러나 나는 그것이이 방법 Remove가 호출 될 때마다 beggining에서 목록을 통해 이동하기 때문에 그것이 효율적이지 같아요 :

내가 생각하고있는 유일한 방법입니다.

Answer 1

제거 할 항목의 수가 커질수록, 당신은 아마 목록을 통과하고 "제거 항목"의 HashSet에 대해 각 항목을 확인 찾을 수는 더 효율적입니다. 이와 같은 확장 방법이 도움이 될 수 있습니다.

static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove) 
{ 
    var set = new HashSet<T>(itemsToRemove); 

    var list = iList as List<T>; 
    if (list == null) 
    { 
     int i = 0; 
     while (i < iList.Count) 
     { 
      if (set.Contains(iList[i])) iList.RemoveAt(i); 
      else i++; 
     } 
    } 
    else 
    { 
     list.RemoveAll(set.Contains); 
    } 
} 

아래의 작은 프로그램을 사용하여 벤치마킹했습니다. (IList<T> 실제로 List<T>의 경우에 최적의 경로를 사용하고 있습니다.)

내 컴퓨터에서

(내 테스트 데이터를 사용하여),이 확장자 방법은, 코드에 대한 17초 대 실행 1.5 초했다 너의 질문. 그러나, 나는 다른 크기의 데이터로 테스트하지 않았다. 아이템을 두 개만 제거하면 확실합니다. RemoveAll2이 빠릅니다.

static class Program 
{ 
    static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove) 
    { 
     var set = new HashSet<T>(itemsToRemove); 

     var list = iList as List<T>; 
     if (list == null) 
     { 
      int i = 0; 
      while (i < iList.Count) 
      { 
       if (set.Contains(iList[i])) iList.RemoveAt(i); 
       else i++; 
      } 
     } 
     else 
     { 
      list.RemoveAll(set.Contains); 
     } 
    } 

    static void RemoveAll2<T>(this IList<T> list, IEnumerable<T> itemsToRemove) 
    { 
     foreach (var item in itemsToRemove) 
      list.Remove(item); 
    } 

    static void Main(string[] args) 
    { 
     var list = Enumerable.Range(0, 10000).ToList(); 
     var toRemove = new[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
           43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 
          103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 
          173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 
          241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 
          317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 
          401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 
          479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 
          571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 
          647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
          739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 
          827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 
          919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}; 
     list.RemoveAll(toRemove); // JIT 
     //list.RemoveAll2(toRemove); // JIT 

     var sw = Stopwatch.StartNew(); 
     for (int i = 0; i < 10000; i++) 
     { 
      list.RemoveAll(toRemove); 
      //list.RemoveAll2(toRemove); 
     } 
     sw.Stop(); 
     Console.WriteLine("Elapsed: {0} ms", sw.ElapsedMilliseconds); 
     Console.ReadKey(); 
    } 
} 

---

UPDATE (아래 @ KarmaEDV의 코멘트) :

public static void RemoveAll<T>(this IList<T> iList, IEnumerable<T> itemsToRemove, IEqualityComparer<T> comparer) 
{ 
    var set = new HashSet<T>(itemsToRemove, comparer); 

    var list = iList as List<T>; 
    if (list == null) 
    { 
     int i = 0; 
     while (i < iList.Count) 
     { 
      if (set.Contains(iList[i])) iList.RemoveAt(i); 
      else i++; 
     } 
    } 
    else 
    { 
     list.RemoveAll(set.Contains); 
    } 
} 

: 사용자 지정 같음 비교를 사용해야 할 경우 은, 확장 방법은 이러한 비교자를 걸리는 과부하를 가질 수

Answer 2

List<T>의 인스턴스를 참조하는 경우 해당 유형으로 캐스팅하고 RemoveAll을 사용하면 해당 구현의 세부 사항에 의존하지 않는 다른 방법보다 성능이 향상됩니다. 최적의 접근 방식은 제거하려고하는 항목의 상대적 비율과 IList<T>의 성격에 따라 달라집니다 동안

그렇지 않으면, 당신의 가장 좋은 방법은 List<T> 새로운 명확로 IList<T>를 복사 할 수 있습니다 제안했다 항목을 선택적으로 다시 추가 할 수 있습니다. 목록의 항목이 효율적인 해싱에 도움이되지 않는 경우에도 IEnumerable<T>의 항목이 IList<T>의 항목과 동일한 순서로되어 있다는 사실은 관련성이 떨어집니다. IEnumerable<T>에서 항목을 읽어서 시작하십시오. 그런 다음 해당 배열이 발견 될 때까지 배열의 항목을 목록에 복사합니다. 그런 다음 IEnumerable<T>에서 다음 항목을 읽고 해당 배열이 발견 될 때까지 목록에서 목록으로 복사하십시오. IEnumerable<T>이 모두 소모되면 List<T>에 배열 잔액을 복사하십시오.

이 방법은 IList<T>의 많은 구현을 사용하면 빠릅니다. 그러나 각 항목을 삭제하고 다시 추가한다는 사실은 관찰 가능한 목록과 같은 것에 부작용을 줄 수 있다는 단점이 있습니다. 명부가 관측 될 수있는 경우에, 정확성을 지키는 훨씬 느린 N^2 알고리즘을 사용해야 할 수도 있습니다. [BTW, IList<T>에는 Remove(T) 메서드가 있지만 더 유용한 RemoveAll(Func<T,bool>) 메서드가 없습니다. Remove(T)은 대부분 IndexOf 및 RemoveAt으로 중복되며, RemoveAll은 항목을 제거하고 다시 추가 할 수없는 경우 부재 중 O (N^2) 개의 많은 작업을 O (N) 구현할 수 있습니다.

Answer 3

아마도 도움이됩니다. 같은 유형의 다른 아이디어가 포함될 수 있습니다.

IList<T> items; 

IEnumerable<T> itemsToDelete; 
... 
{ 
    if(items.Equals(itemsToDelete)) //Equal lists? 
    { 
     items.Clear(); 
     return true; 
    } 


    if( (double) items.Count/itemsToDelete.Count < 1){ 
     /* It is faster to iterate the small list first. */ 
       foreach (var x in items) 
       { 
       if(itemsToDelete.Contains(x)){/**/} 

       } 
    } 
    else{ 
      foreach (var x in itemsToDelete) 
       { 
       items.Remove(x); 
       } 
    } 
}