Python: Finden Sie heraus, ob eine Liste von ganzen Zahlen kohärent ist

Question

Ich versuche herauszufinden, ob eine Liste von ganzen Zahlen kohärent oder "auf einer Strecke" ist, was bedeutet, dass der Unterschied zwischen zwei benachbarten Elementen genau eins sein muss und dass die Zahlen muss monoton ansteigen. I eine nette Vorgehensweise, bei der wir nach der Nummer in der Liste minus der Position des Elements in der Liste gruppieren können - dieser Unterschied ändert sich, wenn die Zahlen nicht kohärent sind. Offensichtlich sollte es genau eine Gruppe geben, wenn die Sequenz keine Lücken oder Wiederholungen enthält.

Test:

>>> l1 = [1, 2, 3, 4, 5, 6] 
>>> l2 = [1, 2, 3, 4, 5, 7] 
>>> l3 = [1, 2, 3, 4, 5, 5] 
>>> l4 = [1, 2, 3, 4, 5, 4] 
>>> l5 = [6, 5, 4, 3, 2, 1] 
>>> def is_coherent(seq): 
...  return len(list(g for _, g in itertools.groupby(enumerate(seq), lambda (i,e): i-e))) == 1 
... 
>>> is_coherent(l1) 
True 
>>> is_coherent(l2) 
False 
>>> is_coherent(l3) 
False 
>>> is_coherent(l4) 
False 
>>> is_coherent(l5) 
False 

Es funktioniert gut, aber ich persönlich finde, dass diese Lösung im Hinblick auf die Einfachheit des Problems ein wenig zu verworren ist. Können Sie einen klareren Weg finden, um dasselbe zu erreichen, ohne die Codelänge wesentlich zu erhöhen?

Edit: Zusammenfassung der Antworten

Aus den Antworten unten gegeben, die Lösung

def is_coherent(seq): 
    return seq == range(seq[0], seq[-1]+1) 

klar gewinnt. Für kleine Listen (10^3 Elemente) ist es in der Größenordnung von 10 mal schneller als der groupby Ansatz und (auf meinem Rechner) immer noch viermal schneller als der nächstbeste Ansatz (mit izip_longest). Es hat das schlechteste Skalierungsverhalten, aber selbst für eine große Liste mit 10^8 Elementen ist es immer noch zweimal schneller als der nächstbeste Ansatz, was wiederum die izip_longest -basierte Lösung ist.

Relevant Timing-Informationen mit timeit erhalten:

Testing is_coherent_groupby... 
    small/large/larger/verylarge duration: 8.27 s, 20.23 s, 20.22 s, 20.76 s 
    largest/smallest = 2.51 
Testing is_coherent_npdiff... 
    small/large/larger/verylarge duration: 7.05 s, 15.81 s, 16.16 s, 15.94 s 
    largest/smallest = 2.26 
Testing is_coherent_zip... 
    small/large/larger/verylarge duration: 5.74 s, 20.54 s, 21.69 s, 24.62 s 
    largest/smallest = 4.28 
Testing is_coherent_izip_longest... 
    small/large/larger/verylarge duration: 4.20 s, 10.81 s, 10.76 s, 10.81 s 
    largest/smallest = 2.58 
Testing is_coherent_all_xrange... 
    small/large/larger/verylarge duration: 6.52 s, 17.06 s, 17.44 s, 17.30 s 
    largest/smallest = 2.65 
Testing is_coherent_range... 
    small/large/larger/verylarge duration: 0.96 s, 4.14 s, 4.48 s, 4.48 s 
    largest/smallest = 4.66 

Testing Code:

import itertools 
import numpy as np 
import timeit 


setup = """ 
import numpy as np 
def is_coherent_groupby(seq): 
    return len(list(g for _, g in itertools.groupby(enumerate(seq), lambda (i,e): i-e))) == 1 

def is_coherent_npdiff(x): 
    return all(np.diff(x) == 1) 

def is_coherent_zip(seq): 
    return all(x==y+1 for x, y in zip(seq[1:], seq)) 

def is_coherent_izip_longest(l): 
    return all(a==b for a, b in itertools.izip_longest(l, xrange(l[0], l[-1]+1))) 

def is_coherent_all_xrange(l): 
    return all(l[i] + 1 == l[i+1] for i in xrange(len(l)-1)) 

def is_coherent_range(seq): 
    return seq == range(seq[0], seq[-1]+1) 


small_list = range(10**3) 
large_list = range(10**6) 
larger_list = range(10**7) 
very_large_list = range(10**8) 
""" 


fs = [ 
    'is_coherent_groupby', 
    'is_coherent_npdiff', 
    'is_coherent_zip', 
    'is_coherent_izip_longest', 
    'is_coherent_all_xrange', 
    'is_coherent_range' 
    ] 


for n in fs: 
    print "Testing %s..." % n 
    t1 = timeit.timeit(
     '%s(small_list)' % n, 
     setup, 
     number=40000 
     )  
    t2 = timeit.timeit(
     '%s(large_list)' % n, 
     setup, 
     number=100 
     )  
    t3 = timeit.timeit(
     '%s(larger_list)' % n, 
     setup, 
     number=10 
     ) 
    t4 = timeit.timeit(
     '%s(very_large_list)' % n, 
     setup, 
     number=1 
     ) 
    print " small/large/larger/verylarge duration: %.2f s, %.2f s, %.2f s, %.2f s" % (t1, t2, t3, t4) 
    print " largest/smallest = %.2f" % (t4/t1) 

Prüfmaschine:

• Linux 3.2.0 (Ubuntu 12,04)
• Python 2.7 .3 (gcc 4.1.2)
• numpy 1.6.2 mit Intel-Compiler gebaut
• CPU: E5-2650 @ 2.00GHz
• 24 GB Speicher

Answer 1

wie Kampf

sorted_list = sorted(my_list) 
return sorted_list == range(sorted_list[0],sorted_list[-1]+1) 

oder wenn es nur kohärent, wenn es ist bereits sortiert

return my_list == range(my_list[0],my_list[-1]+1) 

Wenn Sie Python 3 verwenden, benötigen Sie list(range(...))

Answer 2

Ich weiß nicht Python, aber ich weiß seine Funktion, so dass es eine kleine Schleife Funktion, die es tun wird, wenn Sie die Syntax für die korrekte Python ändern.

PSEUDO CODE

def is_coherent(seq): 
    for x in xrange(1, len(seq)-1): 
     if (seq[x+1]-seq[x] != 1) return false; 
    return true 

Answer 3

def is_coherent(seq): 
    return all(x==y+1 for x, y in zip(seq[1:], seq)) 

Answer 4

Wenn ich etwas in Ihren Beispielen mit Blick auf bin, diese einfachere Lösung ist eigentlich kürzer.

>>> l1 = [1, 2, 3, 4, 5, 6] 
>>> l2 = [1, 2, 3, 4, 5, 7] 
>>> l3 = [1, 2, 3, 4, 5, 5] 
>>> l4 = [1, 2, 3, 4, 5, 4] 
>>> l5 = [6, 5, 4, 3, 2, 1] 
>>> 
>>> def is_coherent(seq): 
...  return seq == range(seq[0], seq[0]+len(seq), 1) 
... 
>>> is_coherent(l1) 
True 
>>> is_coherent(l2) 
False 
>>> is_coherent(l3) 
False 
>>> is_coherent(l4) 
False 
>>> is_coherent(l5) 
False 
>>> 

Die Ergebnisse einiger grundlegenden Performance-Tests scheinen zu zeigen, dass diese Methode wesentlich schneller ist (ich habe Ihr Beispiel als is_coherent2 hinzugefügt):

Carl > python -m timeit -s 'from t import is_coherent, l1' 'is_coherent(l1)' 
1000000 loops, best of 3: 0.782 usec per loop 
Carl > python -m timeit -s 'from t import is_coherent, l3' 'is_coherent(l3)' 
1000000 loops, best of 3: 0.796 usec per loop 
Carl > python -m timeit -s 'from t import is_coherent2, l1' 'is_coherent2(l1)' 
100000 loops, best of 3: 4.54 usec per loop 
Carl > python -m timeit -s 'from t import is_coherent2, l3' 'is_coherent2(l3)' 
100000 loops, best of 3: 4.93 usec per loop 

Answer 5

Diese Kurzschlüssen und schaffen keine zusätzlichen Liste, die es für das Testen sehr großer Listen nützlich macht.

def is_coherent(l): 
    return all(a==b for a, b in izip_longest(l, xrange(l[0], l[-1]+1))) 

Oder

def is_coherent(l): 
    return all(l[i] + 1 == l[i+1] for i in xrange(len(l)-1)) 

Answer 6

Wenn Sie sich für eine numpy Lösung suchen:

import numpy as np 

def is_coherent(x): 
    return all(np.diff(x) == 1) 

is_coherent(np.array([1,2,3,4,5])) 
Out[39]: True 

is_coherent(np.array([1,2,3,4,8])) 
Out[40]: False