Поиск и удаление элементов из коллекции

Каков наилучший способ удалить набор из коллекции, но сохраните элементы, которые были удалены в отдельной коллекции?

Я написал метод расширения, который делает это, но я думаю, что должен быть лучший способ. Вот моя функция:

public static List<T> FindAndRemove<T>(this List<T> lst, Predicate<T> match)
{
    List<T> ret = lst.FindAll(match);
    lst.RemoveAll(match);
    return ret;
}

И вы будете использовать его следующим образом:

List<String> myList = new List<String>();
myList.Add("ABC");
myList.Add("DEF");
myList.Add("ABC");
List<String> removed = myList.FindAndRemove(x => x == "ABC");
// myList now contains 1 item (DEF)
// removed now contains 2 items (ABC, ABC)

Я не уверен на 100%, что происходит за кулисами методов FindAll и RemoveAll, но я полагаю, что лучший способ - это как-то перевести элементы из одного списка в другой.

Ответы

Ответ 1

Ответ на вопрос - лучший из предлагаемых и предлагаемых решений. Вот тайминг на моей машине:

public static class Class1
{
    // 21ms on my machine
    public static List<T> FindAndRemove<T>(this List<T> lst, Predicate<T> match)
    {
        List<T> ret = lst.FindAll(match);
        lst.RemoveAll(match);
        return ret;
    }

    // 538ms on my machine
    public static List<T> MimoAnswer<T>(this List<T> lst, Predicate<T> match)
    {
        var ret = new List<T>();
        int i = 0;
        while (i < lst.Count)
        {
            T t = lst[i];
            if (!match(t))
            {
                i++;
            }
            else
            {
                lst.RemoveAt(i);
                ret.Add(t);
            }
        }
        return ret;
    }

    // 40ms on my machine
    public static IEnumerable<T> GuvanteSuggestion<T>(this IList<T> list, Func<T, bool> predicate)
    {
        var removals = new List<Action>();

        foreach (T item in list.Where(predicate))
        {
            T copy = item;
            yield return copy;
            removals.Add(() => list.Remove(copy));
        }

        // this hides the cost of processing though the work is still expensive
        Task.Factory.StartNew(() => Parallel.ForEach(removals, remove => remove()));
    }
}

[TestFixture]
public class Tester : PerformanceTester
{
    [Test]
    public void Test()
    {
        List<int> ints = Enumerable.Range(1, 100000).ToList();
        IEnumerable<int> enumerable = ints.GuvanteSuggestion(i => i % 2 == 0);
        Assert.That(enumerable.Count(), Is.EqualTo(50000));
    }
}

Ответ 2

Я не согласен с тем, что он наиболее эффективен - вы дважды вызываете предикат match для каждого элемента списка.

Я бы сделал это вот так:

    var ret = new List<T>(); 
    var remaining = new List<T>(); 
    foreach (T t in lst) {
        if (match(t)) 
        { 
            ret.Add(t); 
        } 
        else 
        { 
            remaining.Add(t); 
        } 
    }
    lst.Clear();
    lst.AddRange(remaining);
    return ret;

Ответ 3

В зависимости от размера вашей коллекции вы можете реализовать его как HashSet, а не List. В достаточно больших коллекциях (насколько большой "достаточно" несколько зависит от того, что находится в коллекции, по моему опыту), HashSets может быть намного быстрее и быстрее находить элементы внутри себя, чем списки.

Ответ 4

То, что вы должны пытаться сделать, - это разбить исходный список на два новых списка. Реализация должна работать над любыми IEnumerable, а не только списками, и должна предполагать, что источник является неизменным. См. Это сообщение о разделении: Список разделов LINQ в списки из 8 участников. Я думаю, MoreLinq уже закрыл.