python equivalente a filter () obteniendo dos listas de salida (es decir, partición de una lista)

>>> def partition(l, p):
...     return reduce(lambda x, y: (x[0]+[y], x[1]) if p(y) else (x[0], x[1]+[y]), l,  ([], []))
... 
>>> partition([1, 2, 3, 4, 5], lambda x: x < 3)
([1, 2], [3, 4, 5])

Y una versión un poco más fea pero más rápida del código anterior:

def partition(l, p):
    return reduce(lambda x, y: x[0].append(y) or x if p(y) else x[1].append(y) or x, l,  ([], []))

Esta es la segunda edición, pero creo que importa:

 def partition(l, p):
     return reduce(lambda x, y: x[not p(y)].append(y) or x, l, ([], []))

El segundo y el tercero son tan rápidos como el iterativo superior, pero son menos código.

Creo que groupby podría ser más relevante aquí:

Http://docs.python.org/library/itertools.html#itertools.groupby

Por ejemplo, dividir una lista en números pares e impares (o podría ser un número arbitrario de grupos):

>>> l=range(6)
>>> key=lambda x: x % 2 == 0
>>> from itertools import groupby
>>> {k:list(g) for k,g in groupby(sorted(l,key=key),key=key)}
    {False: [1, 3, 5], True: [0, 2, 4]}

Si no tienes un elemento duplicado en tu lista definitivamente puedes usar set:

>>> a = [1,4,12,7,42]
>>> b = filter(lambda x: x > 10, [1,4,12,7,42])
>>> no_b = set(a) - set(b)
set([1, 4, 7])

O se puede hacer por una lista comprensible:

>>> no_b = [i for i in a if i not in b]

N.B.: no es una función, pero solo conociendo el primer resultado de fitler() puedes deducir el elemento que no hizo mucho tu criterio de filtro .

TL; DR

El aceptado, la respuesta más votada [1] por Mark Byers

def partition(pred, iterable):
    trues = []
    falses = []
    for item in iterable:
        if pred(item):
            trues.append(item)
        else:
            falses.append(item)
    return trues, falses

Es el más simple y el el más rápido.

Evaluación comparativa de los diferentes enfoques

Los diferentes enfoques que se habían sugerido pueden clasificarse en general en tres categorías,

1. manipulación sencilla de la lista a través de lis.append, devolviendo una tupla 2 de listas,
2. lis.append mediado por un enfoque funcional, devolviendo un 2-tupla de listas,
3. usando la receta canónica dada en la itertools multa documentación, devolviendo una 2-tupla de, vagamente hablando, generadores.

Aquí sigue una implementación vainilla de las tres técnicas, primero el enfoque funcional, luego itertools y, finalmente, dos diferentes implementaciones de manipulación directa de listas, siendo la alternativa usando el False es cero, True es un truco.

Tenga en cuenta que esto es Python3 - por lo tanto reduce viene de functools - y que OP solicitar una tupla como (positives, negatives) pero mi todas las implementaciones devuelven (negatives, positives) {

$ ipython
Python 3.6.2 |Continuum Analytics, Inc.| (default, Jul 20 2017, 13:51:32) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.1.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import functools
   ...: 
   ...: def partition_fu(p, l, r=functools.reduce):
   ...:     return r(lambda x, y: x[p(y)].append(y) or x, l, ([], []))
   ...: 

In [2]: import itertools
   ...: 
   ...: def partition_it(pred, iterable,
   ...:               filterfalse=itertools.filterfalse,
   ...:               tee=itertools.tee):
   ...:     t1, t2 = tee(iterable)
   ...:     return filterfalse(pred, t1), filter(pred, t2)
   ...: 

In [3]: def partition_li(p, l):
   ...:     a, b = [], []
   ...:     for n in l:
   ...:         if p(n):
   ...:             b.append(n)
   ...:         else:
   ...:             a.append(n)
   ...:     return a, b
   ...: 

In [4]: def partition_li_alt(p, l):
   ...:     x = [], []
   ...:     for n in l: x[p(n)].append(n)
   ...:     return x
   ...: 

Necesitamos un predicado para aplicar a nuestras listas y listas (de nuevo, libremente hablando) en el que operar.

In [5]: p = lambda n:n%2

In [6]: five, ten = range(50000), range(100000)

Para superar el problema de probar el enfoque itertools, eso fue reported by joeln on Oct 31 '13 a las 6:17

Tonterías. Has calculado el tiempo necesario para construir el generadores en filterfalse y filter, pero no has iterado a través de la entrada o llamada pred una vez! La ventaja de la itertools receta es que no materializa ninguna lista, o mirar más adelante en la entrada de lo necesario. Llama pred dos veces como a menudo y toma casi el doble de tiempo que Byers et al.

He pensado en un bucle vacío que solo instancie todas las parejas de elementos en los dos iterables devueltos por la partición diferente función.

Primero usamos dos listas fijas para tener una idea de la sobrecarga implicada (usando el mismo conveniente magia de IPython %timeit)

In [7]: %timeit for e, o in zip(five, five): pass
4.21 ms ± 39.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

A continuación utilizamos las diferentes implementaciones, una tras otra

In [8]: %timeit for e, o in zip(*partition_fu(p, ten)): pass
53.9 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: %timeit for e, o in zip(*partition_it(p, ten)): pass
44.5 ms ± 3.84 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [10]: %timeit for e, o in zip(*partition_li(p, ten)): pass
36.3 ms ± 101 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [11]: %timeit for e, o in zip(*partition_li_alt(p, ten)): pass
37.3 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [12]:

Comentarios

El más sencillo de los enfoques es también el más rápido.

Usar el truco x[p(n)] es, ehm, inútil porque a cada paso tener que indexar una estructura de datos, lo que le da un leve penalización-es sin embargo, es bueno saber si desea persuadir a un sobreviviente de una disminución culture at pythonizing (en inglés).

El funcional enfoque, que es operativamente equivalente a la alternativa append implementación, es ~50% más lento, posiblemente debido a el hecho de que tenemos una función extra (w/r para predecir la evaluación) llamar a cada elemento de la lista.

El enfoque itertools tiene las ventajas (habituales) de que no no la lista potencialmente grande es instanciada y the la lista de entrada no es totalmente procesado si se sale del círculo del consumidor, pero cuando es más lento debido a la necesidad de aplicar el predicado en ambos fin de la tee

Aparte

Me he enamorado de la object.mutate() or object expresión que fue expuesto por Marii in their answer showing un enfoque funcional del problema - me temo que, tarde o temprano, Voy a abusar de ello.

Notas al pie

[1] Aceptado y más votado como hoy, Sep 14 2017-pero, por supuesto, tengo las mayores esperanzas para esta respuesta mía!

from itertools import ifilterfalse

def filter2(predicate, iterable):
    return filter(predicate, iterable), list(ifilterfalse(predicate, iterable))

Acabo de tener exactamente este requisito. No estoy interesado en la receta itertools ya que implica dos pases separados a través de los datos. Aquí está mi implementación:

def filter_twoway(test, data):
    "Like filter(), but returns the passes AND the fails as two separate lists"
    collected = {True: [], False: []}
    for datum in data:
        collected[test(datum)].append(datum)
    return (collected[True], collected[False])

Puedes mirar django.utils.functional.partition solución:

def partition(predicate, values):
    """
    Splits the values into two sets, based on the return value of the function
    (True/False). e.g.:

        >>> partition(lambda x: x > 3, range(5))
        [0, 1, 2, 3], [4]
    """
    results = ([], [])
    for item in values:
        results[predicate(item)].append(item)
    return results

En mi opinión es la solución más elegante presentada aquí.

Esta parte no está documentada, solo se puede encontrar el código fuente en https://docs.djangoproject.com/en/dev/_modules/django/utils/functional /

Todo el mundo parece pensar que su solución es la mejor, así que decidí usar timeit para probar todos ellos. Usé "def is_odd( x): return x & 1" como mi función predicada, y "xrange(1000)" como iterable. Aquí está mi versión de Python:

Python 2.7.3 (v2.7.3:70274d53c1dd, Apr  9 2012, 20:52:43) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin

Y aquí están los resultados de mis pruebas:

Mark Byers
1000 loops, best of 3: 325 usec per loop

cldy
1000 loops, best of 3: 1.96 msec per loop

Dan S
1000 loops, best of 3: 412 usec per loop

TTimo
1000 loops, best of 3: 503 usec per loop

Todos ellos son comparables entre sí. Ahora, intentemos usar el ejemplo dado en la documentación de Python.

import itertools

def partition(pred, iterable,
              # Optimized by replacing global lookups with local variables
              # defined as default values.
              filter=itertools.ifilter,
              filterfalse=itertools.ifilterfalse,
              tee=itertools.tee):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)

Esto parece ser un poco más rápido.

100000 loops, best of 3: 2.58 usec per loop

El ¡el código de ejemplo de itertools supera a todos los participantes por un factor de al menos 100! La moraleja es, no seguir reinventando la rueda.

Muchas buenas respuestas ya. Me gusta usar esto:

def partition( pred, iterable ):
    def _dispatch( ret, v ):
        if ( pred( v ) ):
            ret[0].append( v )
        else:
            ret[1].append( v )
        return ret
    return reduce( _dispatch, iterable, ( [], [] ) )

if ( __name__ == '__main__' ):
    import random
    seq = range( 20 )
    random.shuffle( seq )
    print( seq )
    print( partition( lambda v : v > 10, seq ) )