python - tag - import django template

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

Question

Digamos que tengo una lista y una función de filtrado. Usando algo como

>>> filter(lambda x: x > 10, [1,4,12,7,42])
[12, 42]

Puedo obtener los elementos que coinciden con el criterio. ¿Hay alguna función que pueda usar que genere dos listas, una de elementos que coincidan, uno de los elementos restantes? Podría llamar a la función filter() dos veces, pero eso es un poco feo :)

Editar: el orden de los elementos debe conservarse, y puedo tener elementos idénticos varias veces.

Answer 1

TL; DR

La respuesta más aceptada y más votada [1] por

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 más rápido.

Benchmarking de los diferentes enfoques

Los diferentes enfoques que se han sugerido se pueden clasificar ampliamente en tres categorías,

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

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

Tenga en cuenta que esto es Python3 - por lo tanto reduce proviene de functools - y que OP solicite una tupla como (positives, negatives) pero todas mis implementaciones regresan (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 (una vez más, en términos generales) sobre los cuales operar.

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

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

Para superar el problema al probar el enfoque de itertools , eso fue informado por joeln el 31 de octubre de joeln a las 6:17

Disparates. Has calculado el tiempo necesario para construir los generadores en filter - filter y filter , pero no has iterado a través de la entrada o llamado " pred una vez. La ventaja de la receta itertools es que no materializa ninguna lista, ni mira más adelante en la entrada de lo necesario. Llama a pred dos veces más y tarda casi el doble que Byers et al.

He pensado en un ciclo vacío que solo ejemplifica todas las parejas de elementos en los dos iterables devueltos por las diferentes funciones de partición.

Primero usamos dos listas fijas para tener una idea de la sobrecarga implícita (usando el muy conveniente %timeit mágico 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, usamos las diferentes implementaciones, una después de la 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 simple de los enfoques es también el más rápido.

Usar el truco x[p(n)] es, ehm, inútil porque en cada paso tiene que indexar una estructura de datos, lo que le da una pequeña penalización; sin embargo, es bueno saber si desea persuadir a un sobreviviente de una cultura en declive en Pitonizar.

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

El enfoque itertools tiene las ventajas (habituales) de que is no se instancia ninguna lista potencialmente grande y ❷ la lista de entrada no se procesa del todo si se sale del bucle del consumidor, pero cuando lo usamos es más lento debido a la necesidad de aplicar el predicado en ambos extremos del tee

Aparte

Me object.mutate() or object del object.mutate() or object modismo de object.mutate() or object que expuso Marii en su respuesta que muestra un enfoque funcional del problema. Me temo que, tarde o temprano, voy a abusar de él.

Notas a pie de página

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

Answer 2

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 una cantidad arbitraria 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]}

Answer 3

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 ) )

Answer 4

Prueba esto:

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

Uso:

>>> trues, falses = partition(lambda x: x > 10, [1,4,12,7,42])
>>> trues
[12, 42]
>>> falses
[1, 4, 7]

También hay una sugerencia de implementación en las recetas itertools :

from itertools import filterfalse, tee

def partition(pred, iterable):
    ''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)

La receta proviene de la documentación de Python 3.x. En Python 2.x filterfalse se llama ifilterfalse .

Answer 5

Puede ver la solución django.utils.functional.partition :

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/

Answer 6

Si no tiene un elemento duplicado en su lista, definitivamente puede 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 puedes hacerlo por una lista comprensible:

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

NB: no es una función, solo conociendo el primer resultado del fitler () puede deducir el elemento que no hizo mucho su criterio de filtro.

Answer 7

Solo tenía 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])

Answer 8

Todo el mundo parece pensar que su solución es la mejor, así que decidí usar timeit para probarlos a todos. Usé "def is_odd (x): return x & 1" como mi función de predicado, 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 mi prueba:

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

Esos son todos 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 código de ejemplo itertools supera a todos los visitantes por un factor de al menos 100! La moraleja es, no sigas reinventando la rueda.

Answer 9

>>> 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 es importante:

 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 uno superior pero tienen menos código.

Answer 10

from itertools import ifilterfalse

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