목록에서 항목을 빠르게 제거하는 방법

목록에서 항목을 빠르게 제거하는 방법

---

C #에서 항목을 빠르게 제거하는 방법을 찾고 List<T>있습니다. 설명서에는 List.Remove()및 List.RemoveAt()작업이 모두O(n)

• 목록. 제거
• List.RemoveAt

이것은 내 응용 프로그램에 심각한 영향을 미칩니다.

몇 가지 다른 제거 방법을 작성하고 List<String>500,000 개 항목으로 모두 테스트했습니다 . 테스트 사례는 다음과 가변적입니다.

---

개요

나는 숫자 각 숫자 ( "1", "2", "3", ...)의 클래스를 생성하는 방법을 작성했습니다. 그런 다음 remove목록의 5 번째 항목마다 시도했습니다 . 목록을 생성하는 데 사용되는 방법은 다음과 같습니다.

private List<String> GetList(int size)
{
    List<String> myList = new List<String>();
    for (int i = 0; i < size; i++)
        myList.Add(i.ToString());
    return myList;
}

테스트 1 : RemoveAt ()

다음은 RemoveAt()방법 을 테스트하는 데 시험 테스트 입니다.

private void RemoveTest1(ref List<String> list)
{
     for (int i = 0; i < list.Count; i++)
         if (i % 5 == 0)
             list.RemoveAt(i);
}

테스트 2 : 제거 ()

다음은 Remove()방법 을 테스트하는 데 시험 테스트 입니다.

private void RemoveTest2(ref List<String> list)
{
     List<int> itemsToRemove = new List<int>();
     for (int i = 0; i < list.Count; i++)
        if (i % 5 == 0)
             list.Remove(list[i]);
}

테스트 3 : null로 설정하고 정렬 한 다음 RemoveRange

이 테스트에서는 목록을 한 번 반복하고 제거 할 항목을 설정했습니다 null. 그런 다음 목록을 정렬하고 (널이 맨 위에있게 됨) 맨 위에있는 모든 항목을 제거했습니다. 참고 : 당신은 순서를 변경해야 할 수도 있습니다.

private void RemoveTest3(ref List<String> list)
{
    int numToRemove = 0;
    for (int i = 0; i < list.Count; i++)
    {
        if (i % 5 == 0)
        {
            list[i] = null;
            numToRemove++;
        }
    }
    list.Sort();
    list.RemoveRange(0, numToRemove);
    // Now they're out of order...
}

테스트 4 : 새 목록을 만들고 모든 "좋은"값을 새 목록에 추가

이 테스트에서는 새 목록을 만들고 모든 보관 항목을 새 목록에 추가했습니다. 그런 다음이 모든 항목을 원래 목록에 넣습니다.

private void RemoveTest4(ref List<String> list)
{
   List<String> newList = new List<String>();
   for (int i = 0; i < list.Count; i++)
   {
      if (i % 5 == 0)
         continue;
      else
         newList.Add(list[i]);
   }

   list.RemoveRange(0, list.Count);
   list.AddRange(newList);
}

테스트 5 : null로 설정 한 다음 FindAll ()

테스트에서는 삭제할이 모든 항목을 null로 설정 한 다음 FindAll()기능 현관을 사용하여 삭제 되지 않은 모든 항목을 찾습니다.null

private void RemoveTest5(ref List<String> list)
{
    for (int i = 0; i < list.Count; i++)
       if (i % 5 == 0)
           list[i] = null;
    list = list.FindAll(x => x != null);
}

테스트 6 : null로 설정 한 다음 RemoveAll ()

이 테스트에서는 null다음이 RemoveAll()기능을 사용하여 삭제되지 않은 모든 항목을 제거했습니다.null

private void RemoveTest6(ref List<String> list)
{
    for (int i = 0; i < list.Count; i++)
        if (i % 5 == 0)
            list[i] = null;
    list.RemoveAll(x => x == null);
}

---

클라이언트 애플리케이션 및 출력

int numItems = 500000;
Stopwatch watch = new Stopwatch();

// List 1...
watch.Start();
List<String> list1 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest1(ref list1);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 2...
watch.Start();
List<String> list2 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest2(ref list2);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 3...
watch.Reset(); watch.Start();
List<String> list3 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest3(ref list3);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 4...
watch.Reset(); watch.Start();
List<String> list4 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest4(ref list4);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 5...
watch.Reset(); watch.Start();
List<String> list5 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest5(ref list5);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 6...
watch.Reset(); watch.Start();
List<String> list6 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest6(ref list6);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

결과

00:00:00.1433089   // Create list
00:00:32.8031420   // RemoveAt()

00:00:32.9612512   // Forgot to reset stopwatch :(
00:04:40.3633045   // Remove()

00:00:00.2405003   // Create list
00:00:01.1054731   // Null, Sort(), RemoveRange()

00:00:00.1796988   // Create list
00:00:00.0166984   // Add good values to new list

00:00:00.2115022   // Create list
00:00:00.0194616   // FindAll()

00:00:00.3064646   // Create list
00:00:00.0167236   // RemoveAll()

메모 및 설명

• 처음 두 테스트는 제거 할 때마다 목록이 다시 정렬되기 때문에 제거 목록에서 다섯 번째 항목을 제거합니다. 500,000 개 항목 중 83,334 개만 제거 (10 만 개 집 함). 나는 이것으로 괜찮습니다-분명히 Remove () / RemoveAt () 메소드는 어쨌든 좋은 생각이 아닙니다.

• 에서 다섯-th 목록 항목을 제거하려고했지만 실제로 는 그런 패턴이 없을을 구석으로입니다. 제거 할 항목은 무작위입니다.

• List<String>이 예에서는 를 사용했지만 항상 그런 [해석] 아닙니다. 그것은List<Anything>

• 시작 목록에 항목을 넣지 않는 것은 옵션 이 아닙니다 .

• 다른 방법 (3-6) 모두은 비교적 성능이 훨씬 우수 했지만 약간 걱정이됩니다. 3, 5, 6에서는 값을로 설정 한 null다음이 센티넬에 따라 모든 항목을 제거해야합니다. 목록에있는 항목 중 하나가 null의도하지 않게 제거 될 수 있는 시나리오를 상상할 수 있기 때문에 접근 방식이 마음에 들지 않습니다 .

내 질문은 :에서 많은 항목을 빠르게 제거하는 가장 좋은 방법은 List<T>무엇입니까? 내가 시도한 대부분의 접근 방식은 나에게 정말 추하고 접근으로 위험 해에 관심이 많습니다. 는 List잘못된 데이터 구조?

지금은 새 목록을 만들고 새 목록에 좋은 항목을 추가하는쪽으로 기울이고 더 나은 방법이있을 것입니다.

---

목록은 제거와 관련하여 사용 데이터 구조가 아닙니다. 제거 구매 이중 항목의 참조 업데이트 만 필요시 사용 연결 목록 (LinkedList)을 사용하는 것이 좋습니다.

---

새 목록을 만드는 데 만족한다면 없습니다. 예를 들면 :

// This overload of Where provides the index as well as the value. Unless
// you need the index, use the simpler overload which just provides the value.
List<string> newList = oldList.Where((value, index) => index % 5 != 0)
                              .ToList();

그러나 같은 다른 데이터 구조, 할 수 있습니다보고 LinkedList<T>또는 HashSet<T>. 실제로 데이터 구조에서 필요한 기능에 따라 수행합니다.

---

나는 느낌 HashSet, LinkedList또는 Dictionary더 나은 서비스를 할 것입니다.

---

순서가 중요하지 간단한 간단한 O (1) List.Remove 메서드가 있습니다.

public static class ListExt
{
    // O(1) 
    public static void RemoveBySwap<T>(this List<T> list, int index)
    {
        list[index] = list[list.Count - 1];
        list.RemoveAt(list.Count - 1);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, T item)
    {
        int index = list.IndexOf(item);
        RemoveBySwap(list, index);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, Predicate<T> predicate)
    {
        int index = list.FindIndex(predicate);
        RemoveBySwap(list, index);
    }
}

이 솔루션은 메모리 순회에 적용에도 적용을 먼저 찾아야하는 사용합니다.

메모 :

• 목록이없는 것들이 찾는 항목의 색인을 찾는 것입니다.
• 연결 목록은 순회시 느리며 특히 수명이 긴 국립 컬렉션의 경우 더 느립니다.

---

할 수 있습니다. 목록 제거는 마지막 요소에서 수행 될 때 O (1)입니다. 관련된 다음 요소의 이동이 없습니다. (일반적으로 목록 제거가 O (n) 인 이유)

for (int i = list.Count - 1; i >= 0; --i)
  list.RemoveAt(i);

---

좋아 이렇게 사용 된 RemoveAll을 시도하십시오

static void Main(string[] args)
{
    Stopwatch watch = new Stopwatch();
    watch.Start();
    List<Int32> test = GetList(500000);
    watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
    watch.Reset(); watch.Start();
    test.RemoveAll( t=> t % 5 == 0);
    List<String> test2 = test.ConvertAll(delegate(int i) { return i.ToString(); });
    watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

    Console.WriteLine((500000 - test.Count).ToString());
    Console.ReadLine();

}

static private List<Int32> GetList(int size)
{
    List<Int32> test = new List<Int32>();
    for (int i = 0; i < 500000; i++)
        test.Add(i);
    return test;
}

이것은 두 번만 반복되고 정확히 100,000 개의 항목을 제거합니다.

이 코드에 대한 내 출력 :

00:00:00.0099495 
00:00:00.1945987 
1000000

HashSet을 시도하도록 업데이트했습니다.

static void Main(string[] args)
    {
        Stopwatch watch = new Stopwatch();
        do
        {
            // Test with list
            watch.Reset(); watch.Start();
            List<Int32> test = GetList(500000);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            watch.Reset(); watch.Start();
            List<String> myList = RemoveTest(test);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            Console.WriteLine((500000 - test.Count).ToString());
            Console.WriteLine();

            // Test with HashSet
            watch.Reset(); watch.Start();
            HashSet<String> test2 = GetStringList(500000);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            watch.Reset(); watch.Start();
            HashSet<String> myList2 = RemoveTest(test2);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            Console.WriteLine((500000 - test.Count).ToString());
            Console.WriteLine();
        } while (Console.ReadKey().Key != ConsoleKey.Escape);

    }

    static private List<Int32> GetList(int size)
    {
        List<Int32> test = new List<Int32>();
        for (int i = 0; i < 500000; i++)
            test.Add(i);
        return test;
    }

    static private HashSet<String> GetStringList(int size)
    {
        HashSet<String> test = new HashSet<String>();
        for (int i = 0; i < 500000; i++)
            test.Add(i.ToString());
        return test;
    }

    static private List<String> RemoveTest(List<Int32> list)
    {
        list.RemoveAll(t => t % 5 == 0);
        return list.ConvertAll(delegate(int i) { return i.ToString(); });
    }

    static private HashSet<String> RemoveTest(HashSet<String> list)
    {
        list.RemoveWhere(t => Convert.ToInt32(t) % 5 == 0);
        return list;
    }

이것은 나에게 준다 :

00:00:00.0131586
00:00:00.1454723
100000

00:00:00.3459420
00:00:00.2122574
100000

---

나는 큰 목록을 다룰 때 이것이 종종 더 빠르다는 것을 발견했습니다. 제거의 속도와 사전에서 제거 할 올바른 항목을 찾는 것은 사전을 만드는 것 이상입니다. 하지만 몇 가지, 원래 목록에는 고유 한 값이 있어야하며 일단 완료되면 순서가 보장되지 않는다고 생각합니다.

List<long> hundredThousandItemsInOrignalList;
List<long> fiftyThousandItemsToRemove;

// populate lists...

Dictionary<long, long> originalItems = hundredThousandItemsInOrignalList.ToDictionary(i => i);

foreach (long i in fiftyThousandItemsToRemove)
{
    originalItems.Remove(i);
}

List<long> newList = originalItems.Select(i => i.Key).ToList();

---

또는 다음을 수행 할 수 있습니다.

List<int> listA;
List<int> listB;

...

List<int> resultingList = listA.Except(listB);

---

n이 정말로 커질 때까지 목록은 LinkedLists보다 빠릅니다. 그 이유는 소위 캐시 미스가 목록보다 LinkedList를 사용하는 경우 훨씬 더 자주 발생하기 때문입니다. 메모리 조회는 상당히 비쌉니다. 목록이 배열로 구현됨에 따라 CPU는 필요한 데이터가 나란히 저장되어 있음을 알고 있기 때문에 한 번에 많은 데이터를로드 할 수 있습니다. 그러나 연결된 목록은 CPU가 다음에 필요한 데이터에 대한 힌트를 제공하지 않으므로 CPU가 더 많은 메모리 조회를 수행하게됩니다. 그건 그렇고. 메모리라는 용어는 RAM을 의미합니다.

자세한 내용은 https://jackmott.github.io/programming/2016/08/20/when-bigo-foolsya.html을 참조하십시오.

---

다른 답변 (및 질문 자체)은 기본 제공 .NET Framework 클래스를 사용하여이 "슬러그"(느림 버그)를 처리하는 다양한 방법을 제공합니다.

그러나 타사 라이브러리로 전환하려는 경우 데이터 구조를 변경하고 목록 유형을 제외하고 코드를 변경하지 않고 그대로두면 더 나은 성능을 얻을 수 있습니다.

Loyc Core 라이브러리에는 동일한 방식으로 작동 List<T>하지만 항목을 더 빨리 제거 할 수 있는 두 가지 유형이 포함되어 있습니다.

• DList<T>List<T>임의의 위치에서 항목을 제거 할 때 2 배의 속도 향상을 제공하는 간단한 데이터 구조입니다.
• AList<T>List<T>목록이 매우 길면 속도를 크게 높일 수있는 정교한 데이터 구조입니다 (목록이 짧으면 속도가 느려질 수 있음).

참고 URL : https://stackoverflow.com/questions/6926554/how-to-quickly-remove-items-from-a-list