Wie kann ich eine Liste umkehren oder sie rückwärts durchlaufen?

Wie iteriere ich in Python rückwärts über eine Liste?

_{Siehe auch: Wie kann ich eine umgekehrte Kopie einer Liste erhalten (vermeiden Sie eine separate Anweisung, wenn Sie eine Methode nach .reverse verketten)?}

>>> xs = [0, 10, 20, 40]
>>> xs[::-1]
[40, 20, 10, 0]

Erweiterte Slice-Syntax wird erklärt hier. Siehe auch, Dokumentation.

Zusammenfassung der Reverse-Methoden

Es gibt drei verschiedene integrierte Möglichkeiten, eine Liste umzukehren. Welche Methode die beste ist, hängt davon ab, ob Sie:

1. Umkehren einer vorhandenen Liste an Ort und Stelle (Ändern der ursprünglichen Listenvariablen)
   • Beste Lösung ist object.reverse() Methode
2. Erstellen Sie einen Iterator der umgekehrten Liste (da Sie ihn einer for-Schleife, einem Generator usw. zuführen werden)
   • Beste Lösung ist reversed(object) wodurch der Iterator erstellt wird
3. Erstellen Sie eine Kopie der Liste, nur in umgekehrter Reihenfolge (um die ursprüngliche Liste beizubehalten)
   • Die beste Lösung ist die Verwendung von Slices mit einer Schrittgröße von -1: object[::-1]

Aus Geschwindigkeitsgründen ist es am besten, die oben genannten integrierten Funktionen zu verwenden, um eine Liste umzukehren. Beim Umkehren sind sie bei kurzen Listen (10 Elemente) 2- bis 8-mal schneller und bei langen Listen bis zu über 300-mal schneller im Vergleich zu einer manuell erstellten Schleife oder einem manuell erstellten Generator. Das ist sinnvoll – sie sind in einer Muttersprache (dh C) geschrieben, werden von Experten erstellt, geprüft und optimiert. Sie sind auch weniger anfällig für Defekte und eignen sich eher für Rand- und Eckfälle.

Testskript

Fügen Sie alle Codeausschnitte in dieser Antwort zusammen, um ein Skript zu erstellen, das die verschiedenen Möglichkeiten zum Umkehren einer Liste ausführt, die unten beschrieben werden. Es misst jede Methode, während es 100.000 Mal ausgeführt wird. Die Ergebnisse werden im letzten Abschnitt für Listen der Länge 2, 10 und 1000 Elemente angezeigt.

from timeit import timeit
from copy import copy

def time_str_ms
    return '{0:8.2f} ms'.format(t * 1000)

Methode 1: An Ort und Stelle mit obj.reverse() umkehren

Wenn das Ziel nur darin besteht, die Reihenfolge der Elemente in einer vorhandenen Liste umzukehren, ohne sie zu durchlaufen oder eine Kopie zum Arbeiten zu erhalten, verwenden Sie die <list>.reverse() Funktion. Führen Sie dies direkt auf einem Listenobjekt aus, und die Reihenfolge aller Elemente wird umgekehrt:

Beachten Sie, dass das Folgende die ursprünglich angegebene Variable umkehrt, obwohl es auch die umgekehrte Liste zurückgibt. dh Sie können eine Kopie erstellen, indem Sie diese Funktionsausgabe verwenden. Normalerweise würden Sie dafür keine Funktion erstellen, aber das Timing-Skript erfordert es.

Wir testen die Leistung dieser beiden Methoden – zuerst einfach eine Liste an Ort und Stelle umkehren (Änderung der ursprünglichen Liste) und dann die Liste kopieren und anschließend umkehren, um zu sehen, ob dies im Vergleich zur anderen der schnellste Weg ist, eine umgekehrte Kopie zu erstellen Methoden.

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

Methode 2: Kehren Sie eine Liste mit Slices um obj[::-1]

Die integrierte Index-Slicing-Methode ermöglicht es Ihnen, eine Kopie eines Teils eines beliebigen indizierten Objekts zu erstellen.

• Es wirkt sich nicht auf das ursprüngliche Objekt aus
• Es erstellt eine vollständige Liste, keinen Iterator

Die generische Syntax lautet: <object>[first_index:last_index:step]. Um Slicing auszunutzen, um eine einfache umgekehrte Liste zu erstellen, verwenden Sie: <list>[::-1]. Wenn Sie eine Option leer lassen, werden sie auf die Standardwerte des ersten und letzten Elements des Objekts gesetzt (umgekehrt, wenn die Schrittgröße negativ ist).

Die Indizierung erlaubt die Verwendung negativer Zahlen, die vom Ende des Objektindex rückwärts zählen (dh -2 ist das vorletzte Element). Wenn die Schrittgröße negativ ist, wird mit dem letzten Element begonnen und um diesen Betrag rückwärts indexiert.

def rev_slice(mylist):
    a = mylist[::-1]
    return a

Methode 3: Kehren Sie eine Liste mit um reversed(obj) Iteratorfunktion

Da ist ein reversed(indexed_object) Funktion:

• Dadurch wird ein umgekehrter Index-Iterator erstellt, keine Liste. Großartig, wenn Sie es einer Schleife zuführen, um eine bessere Leistung bei großen Listen zu erzielen
• Dies erstellt eine Kopie und wirkt sich nicht auf das ursprüngliche Objekt aus

Testen Sie sowohl mit einem unformatierten Iterator als auch mit dem Erstellen einer Liste aus dem Iterator.

def reversed_iterator(mylist):
    a = reversed(mylist)
    return a

def reversed_with_list(mylist):
    a = list(reversed(mylist))
    return a

Methode 4: Umgekehrte Liste mit benutzerdefinierter/manueller Indizierung

Wie das Timing zeigt, ist es keine gute Idee, eigene Indizierungsmethoden zu erstellen. Verwenden Sie die integrierten Methoden, es sei denn, Sie müssen wirklich etwas Benutzerdefiniertes tun. Das bedeutet einfach, die eingebauten Methoden zu lernen.

Das heißt, es gibt keine große Strafe bei kleineren Listengrößen, aber wenn Sie die Größe erhöhen, wird die Strafe enorm. Der folgende Code könnte optimiert werden, da bin ich mir sicher, aber er kann niemals mit den integrierten Methoden übereinstimmen, da sie direkt in einer Muttersprache implementiert sind.

def rev_manual_pos_gen(mylist):
    max_index = len(mylist) - 1
    return [ mylist[max_index - index] for index in range(len(mylist)) ]

def rev_manual_neg_gen(mylist):
    ## index is 0 to 9, but we need -1 to -10
    return [ mylist[-index-1] for index in range(len(mylist)) ]

def rev_manual_index_loop(mylist):
    a = []
    reverse_index = len(mylist) - 1
    for index in range(len(mylist)):
        a.append(mylist[reverse_index - index])
    return a
    
def rev_manual_loop(mylist):
    a = []
    reverse_index = len(mylist)
    for index, _ in enumerate(mylist):
        reverse_index -= 1
        a.append(mylist[reverse_index])
    return a

Timing jeder Methode

Es folgt der Rest des Skripts, um jede Umkehrmethode zu timen. Es zeigt das Rückwärtsfahren an Ort und Stelle mit an obj.reverse() und Erstellen der reversed(obj) Iterator sind immer die schnellsten, während die Verwendung von Slices der schnellste Weg ist, eine Kopie zu erstellen.

Es beweist auch, nicht zu versuchen, einen Weg zu finden, es selbst zu tun, es sei denn, Sie müssen es tun!

loops_to_test = 100000
number_of_items = 10
list_to_reverse = list(range(number_of_items))
if number_of_items < 15:
    print("a: {}".format(list_to_reverse))
print('Loops: {:,}'.format(loops_to_test))
# List of the functions we want to test with the timer, in print order
fcns = [rev_in_place, reversed_iterator, rev_slice, rev_copy_reverse,
        reversed_with_list, rev_manual_pos_gen, rev_manual_neg_gen,
        rev_manual_index_loop, rev_manual_loop]
max_name_string = max([ len(fcn.__name__) for fcn in fcns ])
for fcn in fcns:
    a = copy(list_to_reverse) # copy to start fresh each loop
    out_str=" | out = {}".format(fcn(a)) if number_of_items < 15 else ''
    # Time in ms for the given # of loops on this fcn
    time_str = time_str_ms(timeit(lambda: fcn(a), number=loops_to_test))
    # Get the output string for this function
    fcn_str="{}(a):".format(fcn.__name__)
    # Add the correct string length to accommodate the maximum fcn name
    format_str="{{fx:{}s}} {{time}}{{rev}}".format(max_name_string + 4)
    print(format_str.format(fx=fcn_str, time=time_str, rev=out_str))

Timing-Ergebnisse

Die Ergebnisse zeigen, dass die Skalierung am besten mit den integrierten Methoden funktioniert, die für eine bestimmte Art der Umkehrung am besten geeignet sind. Mit anderen Worten, wenn die Anzahl der Objektelemente zunimmt, übertreffen die integrierten Methoden die anderen Methoden um noch mehr.

Die eingebaute Methode, die direkt das erreicht, was Sie brauchen, ist besser als die Aneinanderreihung von Dingen. dh Slicing ist am besten, wenn Sie eine Kopie der umgekehrten Liste benötigen – es ist schneller als das Erstellen einer doppelten Liste aus list(reversed(obj)) Funktion und schneller, als eine Kopie der Liste zu erstellen und dann eine In-Place-Operation durchzuführen obj.reverse(), aber nie mehr als doppelt so schnell. In der Zwischenzeit können benutzerdefinierte Methoden bei großen Listen um Größenordnungen länger dauern.

Für die Skalierung, mit einer 1000-Elemente-Liste, die reversed(<list>) Der Funktionsaufruf dauert ca. 30 ms, um den Iterator einzurichten, die Umkehrung an Ort und Stelle dauert nur ca. 55 ms, die Verwendung der Slice-Methode dauert ca. 210 ms, um eine Kopie der vollständigen umgekehrten Liste zu erstellen, aber die schnellste manuelle Methode, die ich erstellt habe, dauerte ~8400 ms.

Mit 2 Einträgen in der Liste:

a: [0, 1]
Loops: 100,000
rev_in_place(a):             24.70 ms | out = [1, 0]
reversed_iterator(a):        30.48 ms | out = <list_reverseiterator object at 0x0000020242580408>
rev_slice(a):                31.65 ms | out = [1, 0]
rev_copy_reverse(a):         63.42 ms | out = [1, 0]
reversed_with_list(a):       48.65 ms | out = [1, 0]
rev_manual_pos_gen(a):       98.94 ms | out = [1, 0]
rev_manual_neg_gen(a):       88.11 ms | out = [1, 0]
rev_manual_index_loop(a):    87.23 ms | out = [1, 0]
rev_manual_loop(a):          79.24 ms | out = [1, 0]

Mit 10 Einträgen in der Liste:

rev_in_place(a):             23.39 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_iterator(a):        30.23 ms | out = <list_reverseiterator object at 0x00000290A3CB0388>
rev_slice(a):                36.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_copy_reverse(a):         64.67 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_with_list(a):       50.77 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_pos_gen(a):      162.83 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_neg_gen(a):      167.43 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_index_loop(a):   152.04 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_loop(a):         183.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Und bei 1000 Einträgen in der Liste:

rev_in_place(a):             56.37 ms
reversed_iterator(a):        30.47 ms
rev_slice(a):               211.42 ms
rev_copy_reverse(a):        295.74 ms
reversed_with_list(a):      418.45 ms
rev_manual_pos_gen(a):     8410.01 ms
rev_manual_neg_gen(a):    11054.84 ms
rev_manual_index_loop(a): 10543.11 ms
rev_manual_loop(a):       15472.66 ms

Um dieselbe Liste umzukehren, verwenden Sie:

array.reverse()

Um eine umgekehrte Liste einer anderen Liste zuzuweisen, verwenden Sie:

newArray = array[::-1] 

Mit Slicing, zB array = array[::-1], ist ein netter Trick und sehr pythonisch, aber für Neulinge vielleicht etwas obskur. Die Verwendung der reverse()-Methode ist ein guter Weg, um in die tägliche Codierung einzusteigen, da sie leicht lesbar ist.

Wenn Sie jedoch eine vorhandene Liste wie in einer Interviewfrage umkehren müssen, werden Sie wahrscheinlich nicht in der Lage sein, integrierte Methoden wie diese zu verwenden. Der Interviewer wird eher darauf achten, wie Sie das Problem angehen, als auf die Tiefe der Python-Kenntnisse, ein algorithmischer Ansatz ist erforderlich. Das folgende Beispiel mit einem klassischen Swap könnte eine Möglichkeit sein, dies zu tun:-

def reverse_in_place(lst):      # Declare a function
    size = len(lst)             # Get the length of the sequence
    hiindex = size - 1
    its = size/2                # Number of iterations required
    for i in xrange(0, its):    # i is the low index pointer
        temp = lst[hiindex]     # Perform a classic swap
        lst[hiindex] = lst[i]
        lst[i] = temp
        hiindex -= 1            # Decrement the high index pointer
    print "Done!"

# Now test it!!
array = [2, 5, 8, 9, 12, 19, 25, 27, 32, 60, 65, 1, 7, 24, 124, 654]

print array                    # Print the original sequence
reverse_in_place(array)        # Call the function passing the list
print array                    # Print reversed list


**The result:**
[2, 5, 8, 9, 12, 19, 25, 27, 32, 60, 65, 1, 7, 24, 124, 654]
Done!
[654, 124, 24, 7, 1, 65, 60, 32, 27, 25, 19, 12, 9, 8, 5, 2]

Beachten Sie, dass dies bei Tupeln oder Zeichenfolgensequenzen nicht funktioniert, da Zeichenfolgen und Tupel unveränderlich sind, dh Sie können nicht in sie schreiben, um Elemente zu ändern.