Pythonische Möglichkeit, zu überprüfen, ob eine Liste sortiert ist oder nicht

Gibt es eine pythonische Möglichkeit, zu überprüfen, ob eine Liste bereits in ASC oder DESC sortiert ist

 listtimestamps = [1, 2, 3, 5, 6, 7] 

So etwas wie isttimestamps.isSorted() , das True oder False zurückgibt.

Ich möchte eine Liste von Zeitstempeln für einige Nachrichten eingeben und überprüfen, ob die Transaktionen in der richtigen Reihenfolge erschienen sind.

17 Solutions collect form web for “Pythonische Möglichkeit, zu überprüfen, ob eine Liste sortiert ist oder nicht”

Eigentlich geben wir nicht die Antwort, die anijhaw sucht. Hier ist der eine Liner:

 all(l[i] <= l[i+1] for i in xrange(len(l)-1)) 

Ich würde einfach benutzen

 if sorted(lst) == lst: # code here 

Es sei denn, es ist eine sehr große Liste, in diesem Fall möchten Sie vielleicht eine benutzerdefinierte Funktion erstellen.

Wenn du es einfach nur sortierst, wenn es nicht sortiert ist, dann vergiss den Scheck und sortiere ihn.

 lst.sort() 

Und denkst du nicht zu viel

Wenn du eine benutzerdefinierte Funktion willst, kannst du so etwas machen

 def is_sorted(lst, key=lambda x: x): for i, el in enumerate(lst[1:]): if key(el) < key(lst[i]): # i is the index of the previous element return False return True 

Dies ist O (n) wenn die Liste schon sortiert ist (und O (n) in einer for Schleife an diesem!), Also, wenn du nicht davon ausgehst, dass es nicht sortiert (und ziemlich zufällig) die meiste Zeit ist, würde ich Wieder einmal die Liste sortieren.

Diese Iteratorform ist 10-15% schneller als die Integer-Indizierung:

 # from itertools import izip as zip # python 2 only! def is_sorted(l): return all(a <= b for a, b in zip(l[:-1], l[1:])) 

Eine schöne Möglichkeit, dies zu implementieren ist, die imap Funktion von itertools :

 from itertools import imap, tee import operator def is_sorted(iterable, compare=operator.le): a, b = tee(iterable) next(b, None) return all(imap(compare, a, b)) 

Diese Implementierung ist schnell und funktioniert auf beliebigen iterables.

Ich würde das tun (stehlen von vielen Antworten hier [Aaron Sterling, Wai Yip Tung, sorta von Paul McGuire] und meistens Armin Ronacher ):

 from itertools import tee, izip def pairwise(iterable): a, b = tee(iterable) next(b, None) return izip(a, b) def is_sorted(iterable, key=lambda a, b: a <= b): return all(key(a, b) for a, b in pairwise(iterable)) 

Ein schönes Ding: Du musst nicht das zweite Iterable für die Serie erkennen (im Gegensatz zu einem List Slice).

Ich lief einen Benchmark und sorted(lst, reverse=True) == lst war der schnellste für lange Listen, und all(l[i] >= l[i+1] for i in xrange(len(l)-1)) War der schnellste für kurze Listen . Diese Benchmarks wurden auf einem MacBook Pro 2010 13 "(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5) ausgeführt.

UPDATE: Ich habe das Skript so überarbeitet, dass du es direkt auf deinem eigenen System ausführen kannst. Die vorherige Version hatte Bugs. Außerdem habe ich sowohl sortierte als auch unsortierte Eingaben hinzugefügt.

  • Am besten für kurze Sortierlisten: all(l[i] >= l[i+1] for i in xrange(len(l)-1))
  • Bestes für lange sortierte Listen: sorted(l, reverse=True) == l
  • Am besten für kurze unsortierte Listen: all(l[i] >= l[i+1] for i in xrange(len(l)-1))
  • Am besten für lange unsortierte Listen: all(l[i] >= l[i+1] for i in xrange(len(l)-1))

In den meisten Fällen gibt es einen klaren Sieger.

UPDATE: Die Antworten von aaronsterling (# 6 und # 7) sind in allen Fällen die schnellsten. # 7 ist der schnellste, weil es nicht eine Schicht von indirection, um den Schlüssel zu suchen.

 #!/usr/bin/env python import itertools import time def benchmark(f, *args): t1 = time.time() for i in xrange(1000000): f(*args) t2 = time.time() return t2-t1 L1 = range(4, 0, -1) L2 = range(100, 0, -1) L3 = range(0, 4) L4 = range(0, 100) # 1. def isNonIncreasing(l, key=lambda x,y: x >= y): return all(key(l[i],l[i+1]) for i in xrange(len(l)-1)) print benchmark(isNonIncreasing, L1) # 2.47253704071 print benchmark(isNonIncreasing, L2) # 34.5398209095 print benchmark(isNonIncreasing, L3) # 2.1916718483 print benchmark(isNonIncreasing, L4) # 2.19576501846 # 2. def isNonIncreasing(l): return all(l[i] >= l[i+1] for i in xrange(len(l)-1)) print benchmark(isNonIncreasing, L1) # 1.86919999123 print benchmark(isNonIncreasing, L2) # 21.8603689671 print benchmark(isNonIncreasing, L3) # 1.95684289932 print benchmark(isNonIncreasing, L4) # 1.95272517204 # 3. def isNonIncreasing(l, key=lambda x,y: x >= y): return all(key(a,b) for (a,b) in itertools.izip(l[:-1],l[1:])) print benchmark(isNonIncreasing, L1) # 2.65468883514 print benchmark(isNonIncreasing, L2) # 29.7504849434 print benchmark(isNonIncreasing, L3) # 2.78062295914 print benchmark(isNonIncreasing, L4) # 3.73436689377 # 4. def isNonIncreasing(l): return all(a >= b for (a,b) in itertools.izip(l[:-1],l[1:])) print benchmark(isNonIncreasing, L1) # 2.06947803497 print benchmark(isNonIncreasing, L2) # 15.6351969242 print benchmark(isNonIncreasing, L3) # 2.45671010017 print benchmark(isNonIncreasing, L4) # 3.48461818695 # 5. def isNonIncreasing(l): return sorted(l, reverse=True) == l print benchmark(isNonIncreasing, L1) # 2.01579380035 print benchmark(isNonIncreasing, L2) # 5.44593787193 print benchmark(isNonIncreasing, L3) # 2.01813793182 print benchmark(isNonIncreasing, L4) # 4.97615599632 # 6. def isNonIncreasing(l, key=lambda x, y: x >= y): for i, el in enumerate(l[1:]): if key(el, l[i-1]): return False return True print benchmark(isNonIncreasing, L1) # 1.06842684746 print benchmark(isNonIncreasing, L2) # 1.67291283607 print benchmark(isNonIncreasing, L3) # 1.39491200447 print benchmark(isNonIncreasing, L4) # 1.80557894707 # 7. def isNonIncreasing(l): for i, el in enumerate(l[1:]): if el >= l[i-1]: return False return True print benchmark(isNonIncreasing, L1) # 0.883186101913 print benchmark(isNonIncreasing, L2) # 1.42852401733 print benchmark(isNonIncreasing, L3) # 1.09229516983 print benchmark(isNonIncreasing, L4) # 1.59502696991 

Obwohl ich glaube nicht, dass es eine Garantie dafür gibt, dass die sorted eingebauten Anrufe seine cmp-Funktion mit i+1, i , das scheint es für CPython zu tun.

So können Sie so etwas wie:

 def my_cmp(x, y): cmpval = cmp(x, y) if cmpval < 0: raise ValueError return cmpval def is_sorted(lst): try: sorted(lst, cmp=my_cmp) return True except ValueError: return False print is_sorted([1,2,3,5,6,7]) print is_sorted([1,2,5,3,6,7]) 

Oder auf diese Weise (ohne ob Aussagen -> EAFP ist falsch gegangen ;-)):

 def my_cmp(x, y): assert(x >= y) return -1 def is_sorted(lst): try: sorted(lst, cmp=my_cmp) return True except AssertionError: return False 

Nicht sehr pythonisch, aber wir brauchen mindestens eine reduce() Antwort, richtig?

 def is_sorted(iterable): prev_or_inf = lambda prev, i: i if prev <= i else float('inf') return reduce(prev_or_inf, iterable, float('-inf')) < float('inf') 

Die Akkumulatorvariable speichert einfach den zuletzt überprüften Wert, und wenn ein Wert kleiner als der vorhergehende Wert ist, wird der Akkumulator auf unendlich gesetzt (und ist also immer noch unendlich, da der 'vorherige Wert' immer größer ist als Die aktuelle).

SapphireSun ist ganz richtig. Sie können einfach lst.sort() . Pythons Sortierung (TimSort) prüft, ob die Liste bereits sortiert ist. Wenn so sort () in linearer Zeit abgeschlossen ist. Klingt wie eine Pythonische Weise, um sicherzustellen, dass eine Liste sortiert wird;)

Wie von @aaronsterling angemerkt, ist die folgende Lösung die kürzeste und am schnellsten, wenn das Array sortiert und nicht zu klein ist: def is_sorted (lst): return (sortiert (lst) == lst)

Wenn die meiste Zeit das Array nicht sortiert ist, wäre es wünschenswert, eine Lösung zu verwenden, die das gesamte Array nicht scannt und False zurückgibt, sobald ein unsortiertes Präfix entdeckt wird. Im Folgenden ist die schnellste Lösung, die ich finden konnte, ist es nicht besonders elegant:

 def is_sorted(lst): it = iter(lst) try: prev = it.next() except StopIteration: return True for x in it: if prev > x: return False prev = x return True 

Mit Nathan Farringtons Benchmark erreicht dies eine bessere Laufzeit als die Verwendung von sortierten (lst) in allen Fällen, außer wenn auf der großen sortierten Liste ausgeführt wird.

Hier sind die Benchmark-Ergebnisse auf meinem Computer.

Sortiert (lst) == lst Lösung

  • L1: 1.23838591576
  • L2: 4.19063091278
  • L3: 1,17996287346
  • L4: 4,68399500847

Zweite Lösung:

  • L1: 0.81095790863
  • L2: 0.802397012711
  • L3: 1,06135106087
  • L4: 8,82761001587

Ich benutze diese Ein-Liner auf numpy.diff ():

 def issorted(x): """Check if x is sorted""" return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0? 

Ich habe es nicht wirklich gegen jede andere Methode geplant, aber ich nehme an, dass es schneller ist als jede reine Python-Methode, besonders für große n, da die Schleife in numpy.diff (wahrscheinlich) direkt in C (n-1 Subtraktionen gefolgt von n -1 Vergleiche).

Allerdings müssen Sie vorsichtig sein, wenn x ein unsigned int ist, was einen stillen Integer-Unterlauf in numpy.diff () verursachen könnte, was zu einem falschen Positiv führt. Hier ist eine modifizierte Version:

 def issorted(x): """Check if x is sorted""" try: if x.dtype.kind == 'u': # x is unsigned int array, risk of int underflow in np.diff x = numpy.int64(x) except AttributeError: pass # no dtype, not an array return (numpy.diff(x) >= 0).all() 

Dies ähnelt der Top-Antwort, aber ich mag es besser, weil es explizite Indizierung vermeidet. Angenommen, Ihre Liste hat den Namen lst , können Sie generieren
(item, next_item) Tupel aus deiner Liste mit zip :

 all(x <= y for x,y in zip(lst, lst[1:])) 

In Python 3 gibt zip bereits einen Generator zurück, in Python 2 kannst du itertools.izip für eine bessere Speicher-Effizienz verwenden.

Kleine Demo:

 >>> lst = [1, 2, 3, 4] >>> zip(lst, lst[1:]) [(1, 2), (2, 3), (3, 4)] >>> all(x <= y for x,y in zip(lst, lst[1:])) True >>> >>> lst = [1, 2, 3, 2] >>> zip(lst, lst[1:]) [(1, 2), (2, 3), (3, 2)] >>> all(x <= y for x,y in zip(lst, lst[1:])) False 

Die letzte schlägt fehl, wenn das Tupel (3, 2) ausgewertet wird.

Bonus: Prüfen von endlichen (!) Generatoren, die nicht indiziert werden können:

 >>> def gen1(): ... yield 1 ... yield 2 ... yield 3 ... yield 4 ... >>> def gen2(): ... yield 1 ... yield 2 ... yield 4 ... yield 3 ... >>> g1_1 = gen1() >>> g1_2 = gen1() >>> next(g1_2) 1 >>> all(x <= y for x,y in zip(g1_1, g1_2)) True >>> >>> g2_1 = gen2() >>> g2_2 = gen2() >>> next(g2_2) 1 >>> all(x <= y for x,y in zip(g2_1, g2_2)) False 

Vergewissern Sie sich, itertools.izip hier zu verwenden, wenn Sie Python 2 verwenden, sonst würden Sie den Zweck itertools.izip , keine Listen von den Generatoren zu erstellen.

Faul

 def is_sorted(l): l2 = iter(l) next(l2, None) return all(a <= b for a, b in zip(l, l2)) 

Dies ist in der Tat der kürzeste Weg, um es mit Rekursion zu tun:

Wenn es sortiert ist, wird True ausdrucken, wird False ausgedruckt

  def is_Sorted(lst): if len(lst) == 1: return True return lst[0] <= lst[1] and is_Sorted(lst[1:]) any_list = [1,2,3,4] print is_Sorted(any_list) 

Wenn Sie den schnellsten Weg für numpy Arrays wollen, verwenden Sie numba , die, wenn Sie conda verwenden sollte bereits installiert sein

Der Code wird schnell sein, weil er von numba kompiliert wird

 import numba @numba.jit def issorted(vec, ascending=True): if len(vec) < 2: return True if ascending: for i in range(1, len(vec)): if vec[i-1] > vec[i]: return False return True else: for i in range(1, len(vec)): if vec[i-1] < vec[i]: return False return True 

und dann:

 >>> issorted(array([4,9,100])) >>> True 

Nur um einen anderen Weg hinzuzufügen (auch wenn es ein zusätzliches Modul benötigt): iteration_utilities.all_monotone :

 >>> from iteration_utilities import all_monotone >>> listtimestamps = [1, 2, 3, 5, 6, 7] >>> all_monotone(listtimestamps) True >>> all_monotone([1,2,1]) False 

Zur Überprüfung nach DESC-Bestellung:

 >>> all_monotone(listtimestamps, decreasing=True) False >>> all_monotone([3,2,1], decreasing=True) True 

Es gibt auch einen strict Parameter, wenn man unbedingt überprüfen muss (wenn aufeinanderfolgende Elemente nicht gleich sein sollten) monotone Sequenzen.

Es ist kein Problem in deinem Fall, aber wenn deine Sequenzen nan Werte enthalten, dann werden einige Methoden fehlschlagen, zum Beispiel mit sortierten:

 def is_sorted_using_sorted(iterable): return sorted(iterable) == iterable >>> is_sorted_using_sorted([3, float('nan'), 1]) # definetly False, right? True >>> all_monotone([3, float('nan'), 1]) False 

Beachten Sie, dass iteration_utilities.all_monotone Vergleich zu den anderen oben genannten Lösungen besonders für unsortierte Eingaben schneller läuft (siehe Benchmark ).

Definitiv arbeitet in Python 3 und höher für Integer oder Strings:

 def tail(t): return t[:] letters = ['a', 'b', 'c', 'd', 'e'] rest = tail(letters) rest.sort() if letters == rest: print ('Given list is SORTED.') else: print ('List NOT Sorted.') 

========================================== =====================

Eine andere Möglichkeit zu finden, ob die angegebene Liste sortiert ist oder nicht

 trees1 = list ([1, 4, 5, 3, 2]) trees2 = list (trees1) trees2.sort() if trees1 == trees2: print ('trees1 is SORTED') else: print ('Not sorted') 
  • Finden Sie Elemente von Array ein am nächsten zu Elementen von Array zwei
  • Python (Numpy) Array Sortierung
  • Heapq mit benutzerdefinierten vergleichen prädikat
  • Wie man die schnelle Sortierung nach Index in einer Liste einer Liste sortiert
  • CSV in Python sortieren
  • Wie entferne ich das Element aus einer Tupelliste, wenn das 2. Element in jedem Tupel ein Duplikat ist?
  • Erweiterte Sortierkriterien für eine Liste von verschachtelten Tupeln
  • Wie kann man zufällig zufällig zwischen gleichen Werten werden?
  • Sortierung einer Liste von Tupeln mit 3 Elementen in Python
  • So ersetzen Sie Zahlen mit Auftrag in (Python) Liste
  • Vektorisierte radix sort mit numpy - kann es schlagen np.sort?
  • Python ist die beste Programmiersprache der Welt.