Filtering a List

I will try to simplify my problem. Let say I have a collection (more specifically a List) with different types of elements, for explanation purpose let say we have objects “Person” with different age of birth and an ID. I will represent a person like this: {<id>,<year>}

At some point, I want to get a sub list of all the persons born on 1988 and 1989, and if there is no persons born on that years, I want all the persons born in 1990:

[{1,1988},{2,1988},{3,1982},{4,1995},{5,1989},{6,1989},{7,1990}] ==> 
[{1,1988},{2,1988},{5,1989},{6,1989}]


[{1,1990},{2,1981},{3,1983},{4,1993},{5,1981},{6,1989},{7,1990}] ==>
[{6,1989}]

[{1,1990},{2,1981},{3,1983},{4,1993},{5,1981},{6,1985},{7,1990}] ==>
[{1,1990},{7,1990}]

Option 0

At first I though about using the filter method on the apache commons library, but this wouldn’t work as I would need to know about all the element on the list to decide if a particular element goes on the sub list or not, so I ruled this option out.

Option 1

Then, the simplest way I can see to do this is loop through the list looking for elements that match the first condition (1988 or 1989), and then, if I can’t find any, loop again to look for elements that match the second condition (1900). But I don’t like this because you have to loop through the list more than once.

Option 2

The other option I can think about is to loop through the list only once, and to have two different sub list, one with the elements that match the first condition and another with the elements that match the second condition. At the end, if the first sub list is empty, we return the second sub list.

Which one of these two is better (more efficient)?
Which would you use and why?
Do you think there is a better solution than these?

Here are the relevant considerations that would influence what I’d do.

Is this method time-critical? If not, forget considerations about which is faster. Looping over a data structure is rarely more expensive than the actual processing you are doing on the data.
If it is time-critical, which is faster in an experiment? Guessing which alternative is faster is almost always useless – if it’s worth doing micro-optimization, it’s worth doing empirically. Yes, that means coding both and throwing one of the solutions away. That’s life.
Overall, the one that’s the easiest to read while still satisfying the requirements is better than anything else. If the library you are using supports complex filtering, maybe with a user-defined filter callback, write a complex callback, give it a meaningful name and then solve the original problem in one line. You can’t get more readable than that. Otherwise, it’s worth trying it out with pseudocode: one alternative has an extra if and another loop that’s executed only conditionally; the other has a more complicated loop body and a small if that returns one list if the other is empty. That sounds a bit closer to the original problem statement “if there are no persons born in those years, I want all the persons born in 1990”, so it might be better. But again you should look at both and then decide which is preferable.

Which one of these two is better (more efficient)?

You did not really define what you mean by “efficient”, but on the other hand, your actual problem is a little more complex than what you described.
I’d be interested to have more details, if possible.

Since there is no specific timing or memory usage requirements, nor clear external constraints about your inputs, the problem is a little too general: you should not really worry about which option is more efficient.

Let’s see, for example, the worst case complexity:

Option 1: O(n) time, O(n) space
Option 2: O(n) time, O(n) space

I now more than one people who would instantly say:
“If it is linear, don’t waste your time with it!“

Now, practically, Option 2 might seem more interesting because:

you only need to loop once over your data and,
for most people (myself included), the mental representation of how computation is done assumes that it is better to compute everything in one pass instead of doing multiple passes (because list traversal might require some overhead); that model does not necessarly takes into accout external constraints like I/O, memory, caches and so on, and how they interact. In fact, I find it really difficult to know beforehand what option is best, in general. However, multiple passes are a great way to separate work into readable chunks (e.g. see how compilers don’t try to do everything at once).

If you have some objective evidence that you need to optimize that part, experiment and measure for a specific metric with representative inputs.

Which would you use and why?

I would use Option 1, mostly in order to Keep It Simple, Stupid, and also because there is no apparent reason that “efficiency” is critical here.

Option 1 is readable, easy to understand, easy to maintain.

Do you think there is a better solution than these?

“Better” is equally hard to understand, here, for the same reasons as above.
But if we assume that “Option 2” definitely is better than “Option 1”, then Option 2 can be even more better:

As soon as you encounter 1988 or 1989, stop populating the second list.

Then, you never will store more than N elements (in either output lists), if your input list has N elements.

For the fun of it, here is a prototype implementation in Common Lisp. Remember, I don’t recommend this approach, I’d personnally stick with Option 1.

First, here are some test sequences (yours included):

   (defparameter *test*
     '(((c 1990) (x 1990))
       ((a 1989) (b 1988) (c 1990))
       ((a 1990) (b 1985) (c 1998))
       ((a 1990) (b 1985) (c 1988))
       ((1 1990) (2 1981) (3 1983) (4 1993) (5 1981) (6 1985) (7 1990))
       ((1 1990) (2 1981) (3 1983) (4 1993) (5 1981) (6 1989) (7 1990))
       ((1 1988) (2 1988) (3 1982) (4 1995) (5 1989) (6 1989) (7 1990))))

Here is a modified option 2 which does not collect “1990” elements if some current or previous element was a member of {1988,1989}:

 (defun option-2 (pair-list)
   (loop for (name year) in pair-list
         for member-p = (member year '(1989 1988) :test #'eql)
         for some-member-p = member-p then (or some-member-p member-p)
         when member-p 
           collect (list name year) into bag-a
         when (and (not some-member-p) (eql year 1990))
           collect (list name year) into bag-b
         finally (return (if some-member-p bag-a bag-b))))

   (mapcar #'option-2 *test*)

   => (((C 1990) (X 1990)) ((A 1989) (B 1988)) ((A 1990)) ((C 1988))
      ((1 1990) (7 1990)) ((6 1989)) ((1 1988) (2 1988) (5 1989) (6 1989)))

For comparison, here is Option 1. It is easier to understand, IMHO:

 (defun option-1 (pair-list)
      (or (remove-if-not (lambda (x) (member x '(1989 1988) :test #'eql)) 
                         pair-list :key #'second)                   
          (remove-if-not (lambda (x) (eql x 1990)) 
                         pair-list :key #'second))))

 (mapcar #'option-1 *test*)

  => (((C 1990) (X 1990)) ((A 1989) (B 1988)) ((A 1990)) ((C 1988))
      ((1 1990) (7 1990)) ((6 1989)) ((1 1988) (2 1988) (5 1989) (6 1989)))

My first thought is to either sort the list or keep it in sorted order. This way, you know while you’re traversing it once you pass the first condition, you’re on the second condition. You can also have early termination once you’ve passed both the first and second conditions.

I’m assuming that this is a stripped down example though, and you might be doing this on more than one property.

So, the second way I’d do it is to have one list. Add items form condition 1 to the front of the list, add items from condition 2 to the end of the list. Keep a counter of how many items matched condition 1. If the counter is greater than 0, return the first part of the list, if it’s 0, then return the list as is.

Filed under: softwareengineering - @ 01:06

Thẻ: collections, filtering, java

Thiết kế website giá rẻ

Danh mục

Filtering a List

Option 0

Option 1

Option 2