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

Question

У меня есть список объектов User, и я должен удалить ОДИН элемент из списка с определенным UserID.

Этот метод должен быть максимально быстрым, в настоящее время я зацикливаюсь на каждом элементе и проверяю, соответствует ли идентификатор идентификатору пользователя, если нет, то я добавляю строку в мою коллекцию FilterList.

List allItems = GetItems();

for(int x = 0; x < allItems.Count; x++)
{
    if(specialUserID == allItems[x].ID)
        continue;
    else
        filteredItems.Add( allItems[x] );
}

Answer 1

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

Answer 2

Что ж, если вы хотите создать новую коллекцию, чтобы оставить оригинал нетронутым, вы должны перебрать все элементы.

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

Ваша логика программы с continue выглядит немного задом наперед ... просто используйте оператор! = Вместо оператора ==:

List<User> allItems = GetItems();

List<User> filteredItems = new List<User>(allItems.Count - 1);

foreach (User u in allItems) {
   if(u.ID != specialUserID) {
      filteredItems.Add(u);
   }
}

Если вы хотите изменить исходную коллекцию вместо создания новой, хранение элементов в Dictionary<int, User> будет самым быстрым вариантом. И обнаружение элемента, и его удаление близки к операциям O (1), поэтому вся операция будет близка к операции O (1) вместо операции O (n).

Answer 3

Используйте хеш-таблицу. Время поиска равно O (1) для всего, что предполагает хороший алгоритм хеширования с минимальным потенциалом столкновения. Я бы порекомендовал что-то, что реализует IDictionary

Answer 4

Если вам нужно перейти из одного списка в другой, вот быстрый результат, который я нашел:

        var filtered = new List<SomeClass>(allItems);
        for (int i = 0; i < filtered.Count; i++)
            if (filtered[i].id == 9999)
                filtered.RemoveAt(i);

Я попытался сравнить ваш метод, метод, описанный выше, и оператор linq "where":

            var allItems = new List<SomeClass>();
        for (int i = 0; i < 10000000; i++)
            allItems.Add(new SomeClass() { id = i });

        Console.WriteLine("Tests Started");
        var timer = new Stopwatch();

        timer.Start();
        var filtered = new List<SomeClass>();
        foreach (var item in allItems)
            if (item.id != 9999)
                filtered.Add(item);
        var y = filtered.Last();
        timer.Stop();
        Console.WriteLine("Transfer to filtered list: {0}", timer.Elapsed.TotalMilliseconds);

        timer.Reset();
        timer.Start();
        filtered = new List<SomeClass>(allItems);
        for (int i = 0; i < filtered.Count; i++)
            if (filtered[i].id == 9999)
                filtered.RemoveAt(i);
        var s = filtered.Last();
        timer.Stop();
        Console.WriteLine("Removal from filtered list: {0}", timer.Elapsed.TotalMilliseconds);

        timer.Reset();
        timer.Start();
        var linqresults = allItems.Where(x => (x.id != 9999));
        var m = linqresults.Last();
        timer.Stop();
        Console.WriteLine("linq list: {0}", timer.Elapsed.TotalMilliseconds);

Результаты были следующими: Тесты начаты

Перевод в отфильтрованный список: 610.5473

Удаление из отфильтрованного списка: 207.5675

Список linq: 379,4382

Использование «Add (someCollection)» и «.RemoveAt» было намного быстрее.

Кроме того, последующие вызовы .RemoveAt довольно дешевы.

Answer 5

public static void RemoveSingle<T>(this List<T> items, Predicate<T> match)
{
    int i = -1;
    while (i < items.Count && !match(items[++i])) ;
    if (i < items.Count)
    {
        items[i] = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
    }
}

Answer 6

Если считать список четным, я бы:

(а) получить список числа процессоров

(b) Разделите ваш список на равные части для каждого процессора

(c) порождает поток для каждого процессора с этими порциями данных с условием завершения, если найден предикат, возвращающий логический флаг.

Answer 7

Вот мысль, как насчет того, чтобы вы не удалили ее как таковую? Я имею в виду что-то вроде этого:

public static IEnumerable<T> LoopWithExclusion<T>(this IEnumerable<T> list, Func<T,bool> excludePredicate)
{
   foreach(var item in list)
   {
      if(excludePredicate(item))
      {
         continue;
      }

      yield return item;
   }
}

Дело в том, что всякий раз, когда вам нужен «отфильтрованный» список, просто вызовите этот метод расширения, который перебирает исходный список, возвращает все элементы, кроме тех, которые вам не нужны.

Примерно так:

List<User> users = GetUsers();

//later in the code when you need the filtered list:

foreach(var user in users.LoopWithExclusion(u => u.Id == myIdToExclude))
{
   //do what you gotta do
}

Answer 8

Я знаю, что это не самый быстрый, но как насчет универсального списка и удаления ()? ( * 1002 MSDN *). Кто-нибудь знает, как это работает по сравнению с, например. пример в вопросе?

Answer 9

Если у вас есть список, и вы хотите изменить его на месте, чтобы удалить элемент, соответствующий условию, следующее выполняется быстрее, чем любая из опубликованных альтернатив:

        for (int i = allItems.Count - 1; i >= 0; i--)
            if (allItems[i].id == 9999)
                allItems.RemoveAt(i);

A Dictionary может быть быстрее для некоторых целей, но не стоит сбрасывать со счетов List. Для небольших коллекций это, вероятно, будет быстрее, а для больших коллекций это может сэкономить память, что, в свою очередь, может сделать ваше приложение быстрее в целом. Профилирование - это единственный способ определить, что быстрее в реальном приложении.

Answer 10

Я не могу понять, почему никому не было дано самое простое, прямое и очевидное решение (также самое быстрое из List). Этот код удаляет ОДИН элемент с соответствующим идентификатором.

for(int i = 0; i < items.Count; i++) {
    if(items[i].ID == specialUserID) {
        items.RemoveAt[i];
        break;
    }
}