def predicate_split1(stream, func):
    true_l, false_l = [], []
    tappend, fappend = true_l.append, false_l.append
    for item in stream:
        if func(item):
            tappend(item)
        else:
            fappend(item)
    return true_l, false_l

def predicate_split2(stream, func):
    true_l, false_l = [], []
    for item in stream:
        if func(item):
            true_l.append(item)
        else:
            false_l.append(item)
    return true_l, false_l

from collections import defaultdict
def predicate_split3(stream, func):
    d = defaultdict(list)
    for x in stream:
        # yes bool is needed... predicate can rely on
        # bool protocol, but key lookup wouldn't.
        d[bool(func(x))].append(x)
    return d.get(True, []), d.get(False, [])

from itertools import groupby
def predicate_split4(stream, func):
    true_l, false_l = [], []
    for key, sublist in groupby(stream, func):
        if key:
            true_l.extend(sublist)
        else:
            false_l.extend(sublist)
    return true_l, false_l

def predicate_split5(stream, func):
    true_l, false_l = [], []
    textend, fextend = true_l.extend, false_l.extend
    for key, sublist in groupby(stream, func):
        if key:
            textend(sublist)
        else:
            fextend(sublist)
    return true_l, false_l

#ferringb@hrair ~ $ for x in {1,2,3,4,5}; do python -m timeit -s "from itertools import groupby;raw=range(100000);f=lambda x:x%2==0;from snakeoil.lists import predicate_split${x} as ps" 'ps(raw, f)'; done
#10 loops, best of 3: 33 msec per loop
#10 loops, best of 3: 38.1 msec per loop
#10 loops, best of 3: 64 msec per loop
#10 loops, best of 3: 222 msec per loop
#10 loops, best of 3: 221 msec per loop