How to iterate at elements from a sub list and then remove the sub list from the list? With great pe-CodePudding

This is a example: originalList is a List of object

var subList = (originalList.Where(x => x.number < 0)).ToList();
originalList.RemoveAll(x => x.number < 0);

I will use this subList later. In this example the originaList is iterated two times. This function is called billions of times and originalList is a large List, is there a easy way to improve the performance?

One important thing: the value of number of the object can change between two calls of this function.

CodePudding user response：

This method returns all elements fulfilling a condition and returns a list of the removed elements. It only iterates once.

public List<T> RemoveAll<T>(List<T> input, Func<T,bool> condition)
{
   List<T> result = new List<T>();
   for(int i = input.Count - 1; i >= 0; i--)
   {
      if(condition.Invoke(input[i]))
      {
         result.Add(input[i]);
         input.RemoveAt(i);
      }
   }
   return result;
}

A for loop is used, because the list is modified, making a foreach impossible. The list is iterated backwards, because otherwise the indices would not be correct anymore.

Online demo: https://dotnetfiddle.net/maox4A

CodePudding user response：

An efficiency improvement (though still ultimately O(n)) is to batch the removals together. My testing shows that depending on the frequency of removal, this can be the same speed or over 4 times faster. Here is the function as an extension method:

public static List<T> RemoveAllAndReturn<T>(this List<T> input, Func<T, bool> condition) {
    List<T> result = new List<T>();
    var removeCt = 0;
    for (int i = input.Count - 1; i >= 0; --i) {
        if (condition(input[i])) {
            result.Add(input[i]);
              removeCt;
        }
        else if (removeCt > 0) {
            input.RemoveRange(i   1, removeCt);
            removeCt = 0;
        }
    }
    if (removeCt > 0)
        input.RemoveRange(0, removeCt);
    return result;
}