¿Cómo dividir una secuencia de acuerdo con un predicado?

Question

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

Esta función hipotética "splitter" sería algo como esto 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:

qué Python ya tienen una forma estándar/incorporado para hacer esto?

Esta funcionalidad no es ciertamente difícil de codificar (ver Apéndice a continuación), pero por una serie de razones, preferiría usar un método estándar/integrado que uno auto rodado.

Gracias!

Adición:

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

>>> 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 se mostró anteriormente en ese la subsecuencia de elementos que satisfacen el predicado viene en último lugar en vez de primero, pero esto es muy leve y muy fácil de corregir si es necesario.)

Se pueden evitar las llamadas redundantes al predicado (haciendo, básicamente, un " memoria en línea "), pero mi mejor intento de esto se vuelve bastante elaborado, 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 se preocupan por preservar el orden original, orden predeterminado sorted 's hace el trabajo (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

El particionamiento es uno de esos itertools recipes que hace justamente eso. Utiliza tee() para asegurarse de que itera la colección en una pasada a pesar de los múltiples iteradores, la función filter() integrada para capturar elementos que satisfacen el predicado, así como filterfalse() para obtener el efecto opuesto del filtro. Esto es lo más cercano a 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 2

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 sólo se 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 quieren 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 3

Si no le importa la eficiencia, creo que groupby (o cualquier "poner datos en n bins" funciones) 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,

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