python - una - uso de la coma

¿Cómo dividir una secuencia según un predicado?

Question

Muy a menudo me encuentro con la necesidad de dividir una secuencia en las dos subsecuencias de elementos que satisfacen y no satisfacen un predicado dado (preservando el orden relativo original).

Esta función hipotética de "divisor" se vería así en acción:

>>> data = map(str, range(14))
>>> pred = lambda i: int(i) % 3 == 2
>>> splitter(data, pred)
[(''2'', ''5'', ''8'', ''11''), (''0'', ''1'', ''3'', ''4'', ''6'', ''7'', ''9'', ''10'', ''12'', ''13'')]

Mi pregunta es:

¿Python ya tiene una forma estándar / integrada para hacer esto?

Esta funcionalidad no es difícil de codificar (vea el Anexo a continuación), pero por varias razones, prefiero usar un método estándar / incorporado que uno auto-enrollado.

¡Gracias!

Apéndice:

La mejor función estándar que he encontrado hasta ahora para manejar esta tarea en Python es itertools.groupby . Para usarlo para esta tarea en particular, sin embargo, es necesario llamar a la función de predicado dos veces para cada miembro de la lista, lo que me parece molesto:

>>> import itertools as it
>>> [tuple(v[1]) for v in it.groupby(sorted(data, key=pred), key=pred)]
[(''0'', ''1'', ''3'', ''4'', ''6'', ''7'', ''9'', ''10'', ''12'', ''13''), (''2'', ''5'', ''8'', ''11'')]

(La última salida anterior difiere de la deseada que se mostró anteriormente en que la subsecuencia de elementos que satisfacen el predicado es la última en lugar de la primera, pero es muy pequeña y muy fácil de corregir si es necesario).

Uno puede evitar las llamadas redundantes al predicado (haciendo, básicamente, una "memoria en línea"), pero mi mejor intento de hacer esto es bastante complicado, muy lejos de la simplicidad de splitter(data, pred) :

>>> first = lambda t: t[0]
>>> [zip(*i[1])[1] for i in it.groupby(sorted(((pred(x), x) for x in data),
... key=first), key=first)]
[(''0'', ''1'', ''3'', ''4'', ''6'', ''7'', ''9'', ''10'', ''12'', ''13''), (''2'', ''5'', ''8'', ''11'')]

Por cierto, si no le importa conservar el orden original, el orden de sorted predeterminado se resuelve (por lo que el parámetro key puede omitirse de la llamada sorted ):

>>> [zip(*i[1])[1] for i in it.groupby(sorted(((pred(x), x) for x in data)),
... key=first)]
[(''0'', ''1'', ''3'', ''4'', ''6'', ''7'', ''9'', ''10'', ''12'', ''13''), (''2'', ''5'', ''8'', ''11'')]

Answer 1

Como una solución un poco más general a la partición, considere agrupar. Considere la siguiente función, inspirada en la función de group-by por clojure.

Le asigna una colección de elementos para agrupar y una función que se utilizará para agruparlos. Aquí está el código:

def group_by(seq, f):

    groupings = {}

    for item in seq:
        res = f(item)
        if res in groupings:
            groupings[res].append(item)
        else:
            groupings[res] = [item]

    return groupings

Para el caso original del OP:

y = group_by(range(14), lambda i: int(i) % 3 == 2)
{False: [0, 1, 3, 4, 6, 7, 9, 10, 12, 13], True: [2, 5, 8, 11]}

Un caso más general de agrupar elementos en una secuencia por longitud de cadena:

x = group_by(["x","xx","yy","zzz","z","7654321"], len)
{1: [''x'', ''z''], 2: [''xx'', ''yy''], 3: [''zzz''], 7: [''7654321'']}

Esto se puede extender a muchos casos, y es una funcionalidad central de los lenguajes funcionales. Funciona muy bien con el pitón dinámicamente escrito, ya que las claves en el mapa resultante pueden ser de cualquier tipo. ¡Disfrutar!

Answer 2

La partición es una de esas recetas de itertools que hace precisamente eso. Utiliza tee() para asegurarse de que está iterando la colección en una sola pasada a pesar de los múltiples iteradores, la función de filter() integrado filter() para capturar elementos que satisfacen el predicado, así como filterfalse() para obtener el efecto opuesto del filtro. Esto es lo más cerca que vas a obtener de un método estándar / incorporado.

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)

Answer 3

Sé que dijiste que no querías escribir tu propia función, pero no puedo imaginar por qué. Sus soluciones implican escribir su propio código, simplemente no las está modularizando en funciones.

Esto hace exactamente lo que quiere, es comprensible y solo evalúa el predicado una vez por elemento:

def splitter(data, pred):
    yes, no = [], []
    for d in data:
        if pred(d):
            yes.append(d)
        else:
            no.append(d)
    return [yes, no]

Si quieres que sea más compacto (por alguna razón):

def splitter(data, pred):
    yes, no = [], []
    for d in data:
        (yes if pred(d) else no).append(d)
    return [yes, no]

Answer 4

Si no te importa la eficiencia, creo que groupby (o cualquier función de "poner datos en n bandejas") tiene una buena correspondencia,

by_bins_iter = itertools.groupby(sorted(data, key=pred), key=pred)
by_bins = dict((k, tuple(v)) for k, v in by_bins_iter)

A continuación, puede llegar a su solución por,

return by_bins.get(True, ()), by_bins.get(False, ())

Answer 5

Una pequeña variación de una de las implementaciones de OP y la implementación de otro comentarista anterior utilizando groupby :

groups = defaultdict(list, { k : list(ks) for k, ks in groupby(items, f) })

groups[True] == the matching items, or [] if none returned True
groups[False] == the non-matching items, or [] if none returned False

Lamentablemente, como usted señala, groupby requiere que los elementos estén ordenados por el predicado primero, así que si eso no está garantizado, necesita esto:

groups = defaultdict(list, { k : list(ks) for k, ks in groupby(sorted(items, key=f), f) })

Todo un bocado, pero es una expresión única que particiona una lista por un predicado utilizando solo las funciones incorporadas.

No creo que solo se pueda usar sorted sin el parámetro key , porque groupby crea un nuevo grupo cuando alcanza un nuevo valor de la función clave. Por lo tanto, la sorted solo funcionará si los elementos se clasifican de forma natural según el predicado proporcionado.