Hi all

 

I was into filtering items lately :) and I have decided to write about some of the techniques out there starting with the old

 

The good old Foreach

Well we have all used this before once you get a list in your hands just iterate through all the items and select the ones you want:

   1: private static List<int> TheOld_FilterPositiveItems(List<int> t)
   2: {
   3:     List<int> ret = new List<int>();
   4:     foreach (int i in t)
   5:     {
   6:         if (i > 0)
   7:         {
   8:             ret.Add(i);
   9:         }
  10:     }
  11:     return ret;
  12: }

I hope you are not using this method. As there are other good methods like this one:

 

Filtering Using Predicates

This method is much more simple and nice. first we will have to define a predicate that will point to a function that will hold the logic of the filtering. Here is the function that will provide the testing of whether the integer is positive or not:

   1: private static bool intpredicate(int i)
   2: {
   3:     if (i > 0)
   4:     {
   5:         return true;
   6:     }
   7:     return false;
   8: }

Pretty simple.

 

Here is how we use it to filter all the integers:

   1: private static List<int> FilterPositiveItems2(List<int> t)
   2: {
   3:     Predicate<int> pred = new Predicate<int>(intpredicate);
   4:     return t.FindAll(pred);
   5: }

That takes care of filtering using predicates. Not a bad way of doing it but here comes the slickest way of filtering:

 

Filtering Using Lmbda Expressions

This is just an improvement on the previous method instead of using the predicate we will provide List.FindAll with a lambda expression.

 

We will use the following expression:

n => n>0 which can be translated like this: n where n is larger then 0.

this lambda expression has a return type of boolean so it can be placed instead of the predicate:

   1: private static List<int> TheSlick_FilterPositiveItems(List<int> t)
   2: {
   3:     return t.FindAll(n => n > 0);
   4: }

That’s it.

 

Enjoy

 

Amit

Tags :

6 Responses to “Filtering List Items, The Old, The New and the Slick”


  1. James Curran

    Said on December 24, 2008 :

    Don’t build a new list if you don’t have to.

    private static IEnumerable EvenSlicker_FilterPositiveItems(IEnumerable t)
    {
    foreach(int n in t)
    if (n > 0)
    yield return n;

    }

    The advantage is if you try using the method this this:

    foreach(int n in FilterPositiveItems(myList) {…}

    Your way is O(2N) while mine is O(N)

  2. Keith

    Said on December 24, 2008 :

    Using lambda expressions actually is filtering with a predicate. Lambdas are just a syntax for declaring anonymous delegates.

    In addition to your 3 ways up there, you can also use an anonymous delegate instead of the second method of doing things. This would be the preferred way of doing it if you are still using 2.0.

  3. configurator

    Said on December 24, 2008 :

    Once again, I have to reiterate what I’ve stated here before.

    I know you don’t like the ‘yield’ keyword, but it’s things like this that it’s meant for.

    All of your examples create a copy of your list in memory, filtering only the needed results.

    However, there are two methods that are a lot better unless you actually need a List:

    1. Use the yield keyword directly. This function will return an IEnumreable object that when enumerated finds the results you want.

    private static IEnumerable FilterPositives(IEnumerable numbers) {
    foreach (int num in numbers)
    if (num > 0)
    yield return num;
    }

    2. Use LINQ’s Where method. The following two functions will return the same result as my previous example.

    private static List FilterPositives2(List numbers) {
    return numbers.Where(intpredicate); // intpredicate is your method from earlier
    }

    private static List FilterPositives3(List numbers) {
    return numbers.Where(num => num > 0);
    }

  4. Niki

    Said on December 28, 2008 :

    @James: Just nitpicking: there is no difference betweeen O(2*N) and O(N). That’s kind of the point of the big-O-Notation. Anyway, I think appending an item to a List is O(N), so the “good old foreach”-version might actually be O(N^2).

    I usually use Enumerable.Where, which is equivalent to your version. I guess the most efficient way would be to filter the items inline (the way std::remove_if in the C++ STL works).

  5. Khalid Abuhakmeh

    Said on December 31, 2008 :

    The third way (the slick) isn’t anything new to .NET. It has been there since delegates and generics were introduced. Just replace the lambda expression with an inline anonymous method and it’s the same thing. Granted, it’s not as pretty.

  6. configurator

    Said on January 5, 2009 :

    @Niki: The Amortized cost of adding items to a list is O(N). However, the memory cost would also be O(N) and in a yield/Where way would be O(1).

Post a Comment