Как быстро удалить элементы из списка - PullRequest
Новая
       1

Как быстро удалить элементы из списка

68 голосов
/ 03 августа 2011

Я ищу способ быстро удалить элементы из C # List<T>. В документации говорится, что операции List.Remove() и List.RemoveAt() являются O(n)

Это серьезно влияет на мое заявление.

Я написал несколько разных методов удаления и протестировал их на 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. Затем я отсортировал список (так что null был бы вверху) и удалил все элементы сверху, которые были установлены в 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: установить в ноль, а затем 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: установить в ноль и затем 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()

Примечания и комментарии

  • Первые два теста фактически не удаляют каждый 5-й элемент из списка, поскольку список переупорядочивается после каждого удаления. Фактически, из 500 000 предметов, только 83 334 были удалены (должно было быть 100 000). Я согласен с этим - очевидно, что методы Remove () / RemoveAt () не очень хорошая идея.

  • Хотя я пытался удалить 5-й элемент из списка, в реальности такого шаблона не будет. Записи, которые будут удалены, будут случайными.

  • Хотя я использовал List<String> в этом примере, это не всегда будет так. Это может быть List<Anything>

  • Не помещать элементы в список для начала это не вариант.

  • Все остальные методы (3 - 6) работали намного лучше, относительно , но меня это немного беспокоило - в 3, 5 и 6 я был вынужден установить значение в null, а затем удалите все предметы в соответствии с этим стражем. Мне не нравится такой подход, потому что я могу представить сценарий, в котором один из элементов в списке может быть null, и он будет удален непреднамеренно.

Мой вопрос: каков наилучший способ быстрого удаления многих предметов из List<T>? Большинство подходов, которые я пробовал, выглядят очень уродливо и потенциально опасно для меня. Является ли List неправильной структурой данных?

Сейчас я склоняюсь к созданию нового списка и добавлению хороших предметов в новый список, но, похоже, должен быть лучший способ.

Ответы [ 10 ]

35 голосов
/ 03 августа 2011

Список не является эффективной структурой данных, когда дело доходит до удаления.Лучше использовать двойной связанный список (LinkedList), поскольку удаление просто требует обновления ссылок в смежных записях.

17 голосов
/ 03 августа 2011

Если вы счастливы, создавая новый список, вам не нужно проходить настройку элементов на ноль.Например: 

// 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>.Это действительно зависит от того, какие функции вам нужны от вашей структуры данных.

13 голосов
/ 03 августа 2011

Я чувствую, что HashSet, LinkedList или Dictionary сделают вас намного лучше.

11 голосов
/ 01 июня 2015

Если порядок не имеет значения, тогда существует простой метод 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 (n), поскольку список должен быть несортированным.
  • Связанные списки работают медленно, особенно для больших коллекций с длинными периодами жизни.
4 голосов
/ 13 февраля 2014

Вы всегда можете удалить элементы из конца списка.Удаление списка равно O (1) при выполнении последнего элемента, поскольку все, что он делает, это счетчик приращений.Здесь нет смещения следующих элементов.(что является причиной, по которой удаление списка обычно является O (n)) 

for (int i = list.Count - 1; i >= 0; --i)
  list.RemoveAt(i);
3 голосов
/ 13 мая 2014

Я обнаружил, что при работе с большими списками это часто происходит быстрее. Скорость удаления и поиска нужного элемента в словаре для удаления более чем компенсирует создание словаря. Пара вещей, хотя, оригинальный список должен иметь уникальные значения, и я не думаю, что порядок будет гарантирован, как только вы закончите. 

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();
3 голосов
/ 03 августа 2011

Хорошо, попробуйте 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
2 голосов
/ 13 октября 2016

Списки работают быстрее, чем LinkedLists, пока n не станет действительно большим.Причиной этого является то, что так называемые ошибки кэширования происходят чаще при использовании LinkedLists, чем Lists.Поиски памяти довольно дороги.Поскольку список реализован в виде массива, процессор может загружать кучу данных одновременно, поскольку он знает, что необходимые данные хранятся рядом друг с другом.Однако связанный список не дает ЦП никакой подсказки о том, какие данные требуются далее, что заставляет ЦП делать больше обращений к памяти.Кстати.Под термином память я имею в виду RAM.

Для получения более подробной информации смотрите: https://jackmott.github.io/programming/2016/08/20/when-bigo-foolsya.html

2 голосов
/ 12 июля 2014

Или вы можете сделать это: 

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

... 

List<int> resultingList = listA.Except(listB);
1 голос
/ 26 февраля 2016

Другие ответы (и сам вопрос) предлагают различные способы борьбы с этим «слагом» (ошибка медлительности) с использованием встроенных классов .NET Framework.

Но если вы хотите переключиться на стороннюю библиотеку, вы можете повысить производительность, просто изменив структуру данных и оставив свой код без изменений, за исключением типа списка.

Библиотеки Loyc Core включают два типа, которые работают так же, как List<T>, но могут быстрее удалять элементы:

  • DList<T> - это простая структура данных, которая дает в два раза ускорение по сравнению с List<T> при удалении элементов из случайных местоположений
  • AList<T> - это сложная структура данных, которая дает вам большое ускорение по сравнению с List<T>, когда ваши списки очень длинные (но могут быть медленнее, когда список короткий).
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...