Nicest, efficient way to get result tuple of sequence items fullfilling and not fullfilling condition

Question

(This is professional best practise/ pattern interest, not home work request)

• INPUT: any unordered sequence or generator items, function myfilter(item) returns True if filter condition is fulfilled

• OUTPUT: (filter_true, filter_false) tuple of sequences of original type which contain the elements partitioned according to filter in original sequence order.

How would you express this without doing double filtering, or should I use double filtering? Maybe filter and loop/generator/list comprehencion with next could be answer?

Should I take out the requirement of keeping the type or just change requirement giving tuple of tuple/generator result, I can not return easily generator for generator input, or can I? (The requirements are self-made)

Here test of best candidate at the moment, offering two streams instead of tuple

import itertools as it
from sympy.ntheory import isprime as myfilter

mylist = xrange(1000001,1010000,2)
left,right = it.tee((myfilter(x), x) for x in mylist)
filter_true = (x for p,x in left if p)
filter_false = (x for p,x in right if not p)

print 'Hundred primes and non-primes odd  numbers'
print  '\n'.join( " Prime %i, not prime %i" %
                  (next(filter_true),next(filter_false))
                  for i in range(100))

Answer 1

I think your best bet will be constructing two separate generators:

filter_true = (x for x in mylist if myfilter(x))
filter_false = (x for x in mylist if not myfilter(x))

Answer 2

The easy way (but less efficient) is to tee the iterable and filter both of them:

import itertools
left, right = itertools.tee( mylist )
filter_true = (x for x in left if myfilter(x))
filter_false = (x for x in right if myfilter(x))

This is less efficient than the optimal solution, because myfilter will be called repeatedly for each element. That is, if you have tested an element in left, you shouldn't have to re-test it in right because you already know the answer. If you require this optimisation, it shouldn't be hard to implement: have a look at the implementation of tee for clues. You'll need a deque for each returned iterable which you stock with the elements of the original sequence that should go in it but haven't been asked for yet.

Answer 3

Let's suppose that your probleme is not memory but cpu, myfilter is heavy and you don't want to iterate and filter the original dataset twice. Here are some single pass ideas :

The simple and versatile version (memoryvorous) :

filter_true=[]
filter_false=[]
for item in  items:
    if myfilter(item):
        filter_true.append(item)
    else:
        filter_false.append(item)  

The memory friendly version : (doesn't work with generators (unless used with list(items)))

while items:
    item=items.pop()
    if myfilter(item):
        filter_true.append(item)
    else:
        filter_false.append(item)  

The generator friendly version :

while True:
    try:
        item=next(items)
        if myfilter(item):
            filter_true.append(item)
        else:
            filter_false.append(item)  
    except StopIteration:
        break

Answer 4

Here is a way to do it which only calls myfilter once for each item and will also work if mylist is a generator

import itertools as it
left,right = it.tee((myfilter(x), x) for x in mylist)
filter_true = (x for p,x in left if p)
filter_false = (x for p,x in right if not p)