Umkehrung einer Zeichenkette in Python

Question

Es gibt keinen eingebauten reverse Funktion für Pythons str Objekt. Wie lässt sich diese Methode am besten implementieren?

Wenn Sie eine sehr knappe Antwort geben, erläutern Sie bitte deren Effizienz. Zum Beispiel, ob die str Objekt in ein anderes Objekt umgewandelt wird, usw.

Answer 1

Verwendung von Aufschneiden :

>>> 'hello world'[::-1]
'dlrow olleh'

---

Die Slice-Notation hat die Form [start:stop:step] . In diesem Fall lassen wir das start y stop Positionen, da wir die gesamte Zeichenfolge benötigen. Wir verwenden auch step = -1 was soviel bedeutet wie "wiederholt um 1 Zeichen von rechts nach links gehen".

Answer 2

Wie lässt sich eine Umkehrfunktion für Zeichenketten am besten implementieren?

Meine eigene Erfahrung mit dieser Frage ist akademisch. Wenn Sie jedoch ein Profi sind und eine schnelle Antwort suchen, verwenden Sie einen Slice, der nach und nach -1 :

>>> 'a string'[::-1]
'gnirts a'

oder besser lesbar (aber langsamer aufgrund der Methodennamenssuche und der Tatsache, dass join eine Liste bildet, wenn ein Iterator angegeben wird), str.join :

>>> ''.join(reversed('a string'))
'gnirts a'

oder aus Gründen der Lesbarkeit und Wiederverwendbarkeit den Slice in eine Funktion einfügen

def reversed_string(a_string):
    return a_string[::-1]

und dann:

>>> reversed_string('a_string')
'gnirts_a'

Längere Erklärung

Wenn Sie an der akademischen Darstellung interessiert sind, lesen Sie bitte weiter.

Es gibt keine eingebaute Umkehrfunktion in Pythons str-Objekt.

Hier sind ein paar Dinge über Pythons Zeichenketten, die Sie wissen sollten:

1. In Python, Zeichenketten sind unveränderlich . Durch das Ändern einer Zeichenfolge wird die Zeichenfolge nicht verändert. Es wird eine neue Zeichenfolge erstellt.

2. Strings sind zerlegbar. Wenn Sie eine Zeichenkette zerschneiden, erhalten Sie eine neue Zeichenkette von einem Punkt in der Zeichenkette, vorwärts oder rückwärts, bis zu einem anderen Punkt, in bestimmten Abständen. Sie nehmen die Slice-Notation oder ein Slice-Objekt in einem Subscript:

   string[subscript]

Der tiefgestellte Index erzeugt einen Abschnitt, indem er einen Doppelpunkt in die geschweiften Klammern einfügt:

    string[start:stop:step]

Um ein Slice außerhalb der geschweiften Klammern zu erstellen, müssen Sie ein Slice-Objekt erstellen:

    slice_obj = slice(start, stop, step)
    string[slice_obj]

Ein lesbarer Ansatz:

Während ''.join(reversed('foo')) lesbar ist, erfordert sie den Aufruf einer String-Methode, str.join auf eine andere aufgerufene Funktion, die relativ langsam sein kann. Lassen Sie uns dies in eine Funktion packen - wir werden darauf zurückkommen:

def reverse_string_readable_answer(string):
    return ''.join(reversed(string))

Der leistungsfähigste Ansatz:

Viel schneller geht es mit einem Reverse Slice:

'foo'[::-1]

Aber wie können wir dies für jemanden, der mit Slices oder der Absicht des ursprünglichen Autors weniger vertraut ist, lesbarer und verständlicher machen? Erstellen wir ein Slice-Objekt außerhalb der tiefgestellten Notation, geben wir ihm einen beschreibenden Namen und übergeben wir es an die tiefgestellte Notation.

start = stop = None
step = -1
reverse_slice = slice(start, stop, step)
'foo'[reverse_slice]

Implementieren als Funktion

Um dies tatsächlich als Funktion zu implementieren, ist es meiner Meinung nach semantisch klar genug, einfach einen beschreibenden Namen zu verwenden:

def reversed_string(a_string):
    return a_string[::-1]

Und die Verwendung ist einfach:

reversed_string('foo')

Was dein Lehrer wahrscheinlich will:

Wenn Sie einen Lehrer haben, möchte er wahrscheinlich, dass Sie mit einer leeren Zeichenkette beginnen und eine neue Zeichenkette aus der alten aufbauen. Sie können dies mit reiner Syntax und Literalen in einer while-Schleife tun:

def reverse_a_string_slowly(a_string):
    new_string = ''
    index = len(a_string)
    while index:
        index -= 1                    # index = index - 1
        new_string += a_string[index] # new_string = new_string + character
    return new_string

Theoretisch ist das schlecht, denn denken Sie daran, Zeichenketten sind unveränderlich - also jedes Mal, wenn es so aussieht, als würden Sie ein Zeichen an Ihre new_string wird theoretisch jedes Mal eine neue Zeichenfolge erstellt! CPython weiß jedoch, wie man dies in bestimmten Fällen optimieren kann, von denen dieser triviale Fall einer ist.

Beste Praxis

Theoretisch ist es besser, die Teilzeichenketten in einer Liste zu sammeln und sie später zu verbinden:

def reverse_a_string_more_slowly(a_string):
    new_strings = []
    index = len(a_string)
    while index:
        index -= 1                       
        new_strings.append(a_string[index])
    return ''.join(new_strings)

Wie wir jedoch in den folgenden Zeitangaben für CPython sehen werden, dauert dies tatsächlich länger, da CPython die Stringverkettung optimieren kann.

Zeitangaben

Hier sind die Zeitangaben:

>>> a_string = 'amanaplanacanalpanama' * 10
>>> min(timeit.repeat(lambda: reverse_string_readable_answer(a_string)))
10.38789987564087
>>> min(timeit.repeat(lambda: reversed_string(a_string)))
0.6622700691223145
>>> min(timeit.repeat(lambda: reverse_a_string_slowly(a_string)))
25.756799936294556
>>> min(timeit.repeat(lambda: reverse_a_string_more_slowly(a_string)))
38.73570013046265

CPython optimiert die Stringverkettung, während andere Implementierungen darf nicht :

... verlassen Sie sich nicht auf CPythons effiziente Implementierung der String-Verkettung an Ort und Stelle für Anweisungen der Form a += b oder a = a + b . Diese Optimierung ist selbst in CPython anfällig (sie funktioniert nur für einige Typen) und ist in Implementierungen, die kein Refcounting verwenden, überhaupt nicht vorhanden. In leistungssensiblen Teilen der Bibliothek sollte stattdessen die Form ''.join() verwendet werden. Damit wird sichergestellt, dass die Verkettung in linearer Zeit über verschiedene Implementierungen hinweg erfolgt.

Answer 3

@Paolo's s[::-1] ist am schnellsten; ein langsamerer Ansatz (vielleicht besser lesbar, aber das ist fraglich) ist ''.join(reversed(s)) .

Answer 4

Diese Antwort ist etwas länger und enthält 3 Abschnitte: Benchmarks der bestehenden Lösungen, warum die meisten Lösungen hier falsch sind , meine Lösung .

Die vorhandenen Antworten sind nur korrekt, wenn Unicode-Modifikatoren / Graphem-Cluster ignoriert werden. Ich werde mich später damit befassen, aber zunächst einen Blick auf die Geschwindigkeit einiger Umkehralgorithmen werfen:

list_comprehension  : min:   0.6s, mean:   0.6s, max:    2.2s
reverse_func        : min:   1.9s, mean:   2.0s, max:    7.9s
reverse_reduce      : min:   5.7s, mean:   5.9s, max:   10.2s
reverse_loop        : min:   3.0s, mean:   3.1s, max:    6.8s

list_comprehension  : min:   4.2s, mean:   4.5s, max:   31.7s
reverse_func        : min:  75.4s, mean:  76.6s, max:  109.5s
reverse_reduce      : min: 749.2s, mean: 882.4s, max: 2310.4s
reverse_loop        : min: 469.7s, mean: 577.2s, max: 1227.6s

Sie können sehen, dass die Zeit für das Listenverständnis ( reversed = string[::-1] ) ist in allen Fällen bei weitem die niedrigste (auch nach Korrektur meines Tippfehlers).

String-Umkehrung

Wenn Sie eine Zeichenkette wirklich im allgemeinen Sinne umkehren wollen, ist es VIEL komplizierter. Nehmen wir zum Beispiel die folgende Zeichenkette ( brauner Finger, der nach links zeigt , gelber Finger nach oben zeigend ). Das sind zwei Grapheme, aber 3 Unicode-Codepunkte. Der zusätzliche Punkt ist ein Hautmodifikator .

example = ""

Aber wenn Sie es mit einer der angegebenen Methoden umkehren, erhalten Sie brauner Finger, der nach oben zeigt , gelber Finger zeigt nach links . Der Grund dafür ist, dass der Farbmodifikator "braun" immer noch in der Mitte liegt und auf alles, was davor liegt, angewendet wird. Wir haben also

• U: nach oben gerichteter Finger
• M: brauner Modifikator
• L: Finger zeigt nach links

und

original: LMU                    
reversed: UML (above solutions)  
reversed: ULM (correct reversal) 

Unicode Graphem-Cluster sind etwas komplizierter als nur Modifikatorcodepunkte. Glücklicherweise gibt es eine Bibliothek für den Umgang mit Grapheme :

>>> import grapheme
>>> g = grapheme.graphemes("")
>>> list(g)
['', '']

und daher wäre die richtige Antwort

def reverse_graphemes(string):
    g = list(grapheme.graphemes(string))
    return ''.join(g[::-1])

die auch bei weitem die langsamste ist:

list_comprehension  : min:    0.5s, mean:    0.5s, max:    2.1s
reverse_func        : min:   68.9s, mean:   70.3s, max:  111.4s
reverse_reduce      : min:  742.7s, mean:  810.1s, max: 1821.9s
reverse_loop        : min:  513.7s, mean:  552.6s, max: 1125.8s
reverse_graphemes   : min: 3882.4s, mean: 4130.9s, max: 6416.2s

Der Kodex

#!/usr/bin/env python

import numpy as np
import random
import timeit
from functools import reduce
random.seed(0)

def main():
    longstring = ''.join(random.choices("ABCDEFGHIJKLM", k=2000))
    functions = [(list_comprehension, 'list_comprehension', longstring),
                 (reverse_func, 'reverse_func', longstring),
                 (reverse_reduce, 'reverse_reduce', longstring),
                 (reverse_loop, 'reverse_loop', longstring)
                 ]
    duration_list = {}
    for func, name, params in functions:
        durations = timeit.repeat(lambda: func(params), repeat=100, number=3)
        duration_list[name] = list(np.array(durations) * 1000)
        print('{func:<20}: '
              'min: {min:5.1f}s, mean: {mean:5.1f}s, max: {max:6.1f}s'
              .format(func=name,
                      min=min(durations) * 10**6,
                      mean=np.mean(durations) * 10**6,
                      max=max(durations) * 10**6,
                      ))
        create_boxplot('Reversing a string of length {}'.format(len(longstring)),
                       duration_list)

def list_comprehension(string):
    return string[::-1]

def reverse_func(string):
    return ''.join(reversed(string))

def reverse_reduce(string):
    return reduce(lambda x, y: y + x, string)

def reverse_loop(string):
    reversed_str = ""
    for i in string:
        reversed_str = i + reversed_str
    return reversed_str

def create_boxplot(title, duration_list, showfliers=False):
    import seaborn as sns
    import matplotlib.pyplot as plt
    import operator
    plt.figure(num=None, figsize=(8, 4), dpi=300,
               facecolor='w', edgecolor='k')
    sns.set(style="whitegrid")
    sorted_keys, sorted_vals = zip(*sorted(duration_list.items(),
                                           key=operator.itemgetter(1)))
    flierprops = dict(markerfacecolor='0.75', markersize=1,
                      linestyle='none')
    ax = sns.boxplot(data=sorted_vals, width=.3, orient='h',
                     flierprops=flierprops,
                     showfliers=showfliers)
    ax.set(xlabel="Time in ms", ylabel="")
    plt.yticks(plt.yticks()[0], sorted_keys)
    ax.set_title(title)
    plt.tight_layout()
    plt.savefig("output-string.png")

if __name__ == '__main__':
    main()

Answer 5

Kurze Antwort (TL;DR)

Exemple

### example01 -------------------
mystring  =   'coup_ate_grouping'
backwards =   mystring[::-1]
print(backwards)

### ... or even ...
mystring  =   'coup_ate_grouping'[::-1]
print(mystring)

### result01 -------------------
'''
gnipuorg_eta_puoc
'''

Ausführliche Antwort

Hintergrund

Diese Antwort wird gegeben, um auf das folgende Anliegen von @odigity einzugehen:

Wow! Ich war zunächst entsetzt über die von Paolo vorgeschlagene Lösung, aber das aber das trat hinter dem Entsetzen zurück, das ich beim Lesen des ersten Kommentar: "Das ist sehr pythonisch. Gute Arbeit!" Ich bin so beunruhigt, dass eine so kluge Gemeinschaft denkt, dass es eine gute Idee ist, solch kryptische Methoden für etwas so eine gute Idee ist. Warum ist es nicht einfach s.reverse()?

Problem

• Kontext
  • Python 2.x
  • Python 3.x
• Szenario:
  • Entwickler möchte eine Zeichenkette umwandeln
  • Die Umwandlung erfolgt in umgekehrter Reihenfolge aller Zeichen

Lösung

• Beispiel01 führt zu dem gewünschten Ergebnis, indem erweiterte Slice-Notation .

Fallstricke

• Der Entwickler könnte etwas erwarten wie string.reverse()
• Die muttersprachliche Idiomatik (auch bekannt als " pythonisch ") Lösung ist für neuere Entwickler möglicherweise nicht lesbar
• Der Entwickler könnte versucht sein, seine eigene Version von string.reverse() um die Slice-Notation zu vermeiden.
• Die Ausgabe der Slice-Notation kann in manchen Fällen kontra-intuitiv sein:
  • siehe z.B. Beispiel02
    • print 'coup_ate_grouping'[-4:] ## => 'ping'
    • im Vergleich zu
    • print 'coup_ate_grouping'[-4:-1] ## => 'pin'
    • im Vergleich zu
    • print 'coup_ate_grouping'[-1] ## => 'g'
  • die unterschiedlichen Ergebnisse der Indexierung auf [-1] kann einige Entwickler abschrecken

Begründung

Bei Python gibt es einen besonderen Umstand zu beachten: Ein String ist ein iterierbar Typ.

Ein Grund für den Ausschluss eines string.reverse() Methode ist es, Python-Entwicklern einen Anreiz zu geben, die Macht dieses besonderen Umstandes zu nutzen.

Vereinfacht ausgedrückt bedeutet dies, dass jedes einzelne Zeichen in einer Zeichenkette einfach als Teil einer sequentiellen Anordnung von Elementen bearbeitet werden kann, genau wie Arrays in anderen Programmiersprachen.

Um zu verstehen, wie das funktioniert, kann ein Blick auf Beispiel02 einen guten Überblick geben.

Beispiel02

### example02 -------------------
## start (with positive integers)
print 'coup_ate_grouping'[0]  ## => 'c'
print 'coup_ate_grouping'[1]  ## => 'o' 
print 'coup_ate_grouping'[2]  ## => 'u' 

## start (with negative integers)
print 'coup_ate_grouping'[-1]  ## => 'g'
print 'coup_ate_grouping'[-2]  ## => 'n' 
print 'coup_ate_grouping'[-3]  ## => 'i' 

## start:end 
print 'coup_ate_grouping'[0:4]    ## => 'coup'    
print 'coup_ate_grouping'[4:8]    ## => '_ate'    
print 'coup_ate_grouping'[8:12]   ## => '_gro'    

## start:end 
print 'coup_ate_grouping'[-4:]    ## => 'ping' (counter-intuitive)
print 'coup_ate_grouping'[-4:-1]  ## => 'pin'
print 'coup_ate_grouping'[-4:-2]  ## => 'pi'
print 'coup_ate_grouping'[-4:-3]  ## => 'p'
print 'coup_ate_grouping'[-4:-4]  ## => ''
print 'coup_ate_grouping'[0:-1]   ## => 'coup_ate_groupin'
print 'coup_ate_grouping'[0:]     ## => 'coup_ate_grouping' (counter-intuitive)

## start:end:step (or start:end:stride)
print 'coup_ate_grouping'[-1::1]  ## => 'g'   
print 'coup_ate_grouping'[-1::-1] ## => 'gnipuorg_eta_puoc'

## combinations
print 'coup_ate_grouping'[-1::-1][-4:] ## => 'puoc'

Schlussfolgerung

El kognitive Belastung die mit dem Verständnis der Slice-Notation in Python verbunden sind, können in der Tat zu viel für einige Anwender und Entwickler sein, die nicht viel Zeit in das Erlernen der Sprache investieren wollen.

Wenn man jedoch die grundlegenden Prinzipien verstanden hat, kann dieser Ansatz im Vergleich zu festen Methoden zur Manipulation von Zeichenketten sehr vorteilhaft sein.

Für diejenigen, die anderer Meinung sind, gibt es alternative Ansätze, wie Lambda-Funktionen, Iteratoren oder einfache einmalige Funktionsdeklarationen.

Falls gewünscht, kann ein Entwickler seine eigene string.reverse()-Methode implementieren, aber es ist gut, den Grundgedanken hinter diesem Aspekt von Python zu verstehen.

Siehe auch

• alternativer einfacher Ansatz
• alternativer einfacher Ansatz
• alternative Erklärung der Slice-Notation