Domanda Modo Pythonic per determinare se le voci dell'elenco non nullo sono 'continue'


Sto cercando un modo per determinare facilmente se non tutti gli elementi di Nessuno in un elenco si verificano in una singola sezione continua.  Userò numeri interi come esempi di non articoli Nessuno.

Ad esempio, la lista [None, None, 1, 2, 3, None, None] soddisfa i miei requisiti per le voci continue continue. Al contrario, [1, 2, None, None, 3, None] è non continua, perché non ci sono voci tra interi.

Alcuni altri esempi per rendere questo più chiaro possibile.

Continuo:
[1, 2, 3, None, None]
[None, None, 1, 2, 3]
[None, 1, 2, 3, None]

Non continuo:
[None, 1, None, 2, None, 3]
[None, None, 1, None, 2, 3]
[1, 2, None, 3, None, None] 

Il mio primo approccio è stato quello di utilizzare le variabili per tenere traccia del fatto che ci fossimo imbattuti o meno None ancora, e anche se non ci siamo imbattuti in un int ancora - questo finisce con una serie di istruzioni if ​​/ else molto annidate e molto difficili da seguire incorporate in un ciclo for. (Oltre alla bruttezza, confesso di non averlo fatto funzionare in ogni caso).

Qualcuno sa un modo più semplice per capire se gli elementi non di Nessuno in una lista si verificano in una singola fetta continua?


44
2018-02-06 04:13


origine


risposte:


def contiguous(seq):
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

Qui ci sono un paio di esempi. Puoi usare next(seq) per ottenere l'elemento successivo da un iteratore. Metterò un segno che punta al prossimo elemento dopo ciascuno

Esempio 1:

seq = iter([None, 1, 2, 3, None])        #  [None, 1, 2, 3, None]
                                         # next^
all(x is None for x in seq)            
                                         #        next^
any(x is None for x in seq)            
                                         #                    next^ (off the end)
return all(x is None for x in seq)       # all returns True for the empty sequence

example2:

seq = iter([1, 2, None, 3, None, None])  #    [1, 2, None, 3, None, None]
                                         # next^
all(x is None for x in seq)            
                                         #    next^
any(x is None for x in seq)            
                                         #             next^  
return all(x is None for x in seq)       # all returns False when 3 is encountered

44
2018-02-06 04:41



Buon vecchio itertools.groupby Al salvataggio:

from itertools import groupby

def contiguous(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

>>> contiguous([1,2,3,None,None])
True
>>> contiguous([None, 1,2,3,None])
True
>>> contiguous([None, None, 1,2,3])
True
>>> contiguous([None, 1, None, 2,3])
False
>>> contiguous([None, None, 1, None, 2,3])
False
>>> contiguous([None, 1, None, 2, None, 3])
False
>>> contiguous([1, 2, None, 3, None, None])
False

[modificare]

Poiché sembra esserci qualche discussione nei commenti, spiegherò perché mi piace questo approccio meglio di altri.

Stiamo cercando di scoprire se esiste un gruppo contiguo di oggetti non None e

sum(1 for k,g in groupby(seq, lambda x: x is not None) if k)

conta il numero di oggetti contigui non None, utilizzando la funzione nello stdlib che è progettata per creare gruppi contigui. Non appena vediamo groupby, pensiamo "gruppi contigui" e viceversa. In questo senso, è auto-documentante. Questo è fondamentalmente il definizione del mio obiettivo.

IMHO l'unica debolezza è che non cortocircuita, e che potrebbe essere riparata, ma dopo averci pensato un po 'lo preferisco ancora perché usa un primitivo che mi piace - "conta il numero di gruppi contigui non-Nessuno" - che preferisco semplicemente "dirmi se c'è più di un gruppo contiguo non-Nessuno appena puoi".

Molti degli approcci per implementare l'ultimo si basano su osservazioni intelligenti sul problema, come "se c'è un solo gruppo contiguo di oggetti non-Nessuno, quindi se scansioniamo fino a trovare il primo oggetto non-Nessuno, e quindi scansioniamo gli oggetti finché non troviamo il primo gruppo non-Nessuno se ne esiste uno, quindi se è rimasto qualcosa è Nessuno ci dà la nostra risposta. " (O qualcosa del genere, che è parte del mio problema: devo pensarci.) A me sembra di usare "dettagli di implementazione" sul problema per risolverlo, e si concentra sulle proprietà del problema che possiamo usare per risolvere esso, piuttosto che semplicemente specificando il problema a Python e lasciando che Python faccia il lavoro.

Sono un orso di pochissimo cervello, come dice il proverbio, e mi piace evitare di dover essere intelligente, poiché nella mia esperienza è un percorso disseminato di FAIL.

Come sempre, il chilometraggio di ognuno può variare, ovviamente, e probabilmente in proporzione alla loro intelligenza.


25
2018-02-06 04:20



Potresti usare qualcosa del genere itertools.groupby:

from itertools import groupby

def are_continuous(items):
    saw_group = False

    for group, values in groupby(items, lambda i: i is not None):
        if group:
            if saw_group:
                return False
            else:
                saw_group = True

    return True

Questo verrà iterato solo fino a quando vedrà un gruppo due volte. Non sono sicuro se lo consideri [None, None], quindi adattalo alle tue esigenze.


12
2018-02-06 04:21



Questo potrebbe non essere il modo migliore per farlo, ma puoi cercare la prima voce non None e l'ultima non-None voce e quindi controllare la sezione per None. per esempio.:

def is_continuous(seq):
    try:
        first_none_pos = next(i for i,x in enumerate(seq) if x is not None)
        #need the or None on the next line to handle the case where the last index is `None`.
        last_none_pos = -next(i for i,x in enumerate(reversed(seq)) if x is not None) or None
    except StopIteration: #list entirely of `Nones`
        return False
    return None not in seq[first_none_pos:last_none_pos]

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

Questo funzionerà per qualsiasi tipo di sequenza.


7
2018-02-06 04:21



Il modo naturale di consumare elementi di sequenza è quello di utilizzare dropwhile:

from itertools import dropwhile
def continuous(seq):
    return all(x is None for x in dropwhile(lambda x: x is not None,
                                            dropwhile(lambda x: x is None, seq)))

Possiamo esprimere questo senza chiamate di funzioni annidate:

from itertools import dropwhile
def continuous(seq):
    core = dropwhile(lambda x: x is None, seq)
    remainder = dropwhile(lambda x: x is not None, core)
    return all(x is None for x in remainder)

7
2018-02-06 10:44



Una fodera:

contiguous = lambda l: ' ' not in ''.join('x '[x is None] for x in l).strip()

Il vero lavoro è fatto dal strip funzione. Se ci sono spazi in una stringa spogliata, quindi non stanno conducendo / seguendo. Il resto della funzione converte l'elenco in una stringa, che ha uno spazio per ciascuno None.


5
2018-02-06 12:11



Ho fatto un po 'di profilazione per confrontare l'approccio di @ gnibbler con l'approccio groupby. L'approccio di @ gnibber è sempre più veloce, specialmente per liste più lunghe Ad esempio, vedo un aumento di prestazioni del 50% per gli input casuali con lunghezza 3-100, con una probabilità del 50% di contenere una singola sequenza int (selezionata casualmente), e in caso contrario con valori casuali. Prova il codice qui sotto. Ho intervallato i due metodi (selezionando casualmente quale si va per primo) per assicurarsi che tutti gli effetti di caching vengano cancellati. Basandomi su questo, direi che mentre l'approccio groupby è più intuitivo, l'approccio di @ gnibber potrebbe essere appropriato se la profilazione indica che questa è una parte importante del codice globale da ottimizzare - in tal caso, i commenti appropriati dovrebbero essere usati per indica cosa sta succedendo con l'utilizzo di tutti / tutti i valori degli iteratori dei consumatori.

from itertools import groupby
import random, time

def contiguous1(seq):
    # gnibber's approach
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

def contiguous2(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

times = {'contiguous1':0,'contiguous2':0}

for i in range(400000):
    n = random.randint(3,100)
    items = [None] * n
    if random.randint(0,1):
        s = random.randint(0,n-1)
        e = random.randint(0,n-s)
        for i in range(s,e):
            items[i] = 3
    else:
        for i in range(n):
            if not random.randint(0,2):
                items[i] = 3
    if random.randint(0,1):
        funcs = [contiguous1, contiguous2]
    else:
        funcs = [contiguous2, contiguous1]
    for func in funcs:
        t0 = time.time()
        func(items)
        times[func.__name__] += (time.time()-t0)

print
for f,t in times.items():
    print '%10.7f %s' % (t, f)

3
2018-02-06 18:10