recursive - Inverse une chaîne en Python




python reverse chain (12)

Il n'y a pas de fonction reverse intégrée pour l'objet str de Python. Quelle est la meilleure façon de mettre en œuvre cette méthode?

Si vous fournissez une réponse très concise, veuillez préciser son efficacité. Par exemple, si l'objet str est converti en un objet différent, etc.


Quelle est la meilleure façon d'implémenter une fonction inverse pour les chaînes?

Ma propre expérience avec cette question est académique. Cependant, si vous êtes un pro à la recherche de la réponse rapide, utilisez une tranche de -1 :

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

ou plus lisible (mais plus lent à cause des recherches de noms de méthodes et du fait que join forme une liste quand on lui donne un itérateur), str.join :

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

ou pour la lisibilité et la réutilisabilité, mettre la tranche dans une fonction

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

et alors:

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

Explication plus longue

Si vous êtes intéressé par l'exposition académique, continuez à lire.

Il n'y a pas de fonction inverse intégrée dans l'objet str de Python.

Voici quelques informations sur les chaînes de Python que vous devriez connaître:

  1. En Python, les chaînes sont immuables . Changer une chaîne ne modifie pas la chaîne. Il en crée un nouveau.

  2. Les cordes sont tranchantes. Trancher une chaîne vous donne une nouvelle chaîne d'un point de la chaîne, en avant ou en arrière, à un autre point, par des incréments donnés. Ils prennent la notation de tranche ou un objet de tranche dans un indice:

    string[subscript]
    

L'indice crée une tranche en incluant un deux-points dans les accolades:

    string[start:stop:step]

Pour créer une découpe en dehors des accolades, vous devez créer un objet découpe:

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

Une approche lisible:

Alors que ''.join(reversed('foo')) est lisible, il faut appeler une méthode string, str.join , sur une autre fonction appelée, qui peut être assez lente. Mettons ceci dans une fonction - nous y reviendrons:

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

L'approche la plus performante:

Beaucoup plus rapide utilise une tranche inverse:

'foo'[::-1]

Mais comment pouvons-nous rendre cela plus lisible et compréhensible pour quelqu'un qui connaît moins les tranches ou l'intention de l'auteur original? Créons un objet découpé en dehors de la notation de l'indice, lui donnons un nom descriptif et transmettons-le à la notation de l'indice.

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

Implémenter comme fonction

Pour réellement l'implémenter en tant que fonction, je pense qu'il est sémantiquement assez clair pour utiliser simplement un nom descriptif:

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

Et l'usage est simplement:

reversed_string('foo')

Ce que votre professeur veut probablement:

Si vous avez un instructeur, ils veulent probablement que vous commenciez avec une chaîne vide, et construisiez une nouvelle chaîne à partir de l'ancienne. Vous pouvez le faire avec de la syntaxe pure et des littéraux en utilisant une boucle while:

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

C'est théoriquement mauvais parce que, rappelez-vous, les cordes sont immuables - donc à chaque fois que vous ajoutez un personnage à votre new_string , cela crée théoriquement une nouvelle corde à chaque fois! Cependant, CPython sait comment l'optimiser dans certains cas, dont ce cas trivial en est un.

Meilleur entrainement

Théoriquement, mieux vaut rassembler vos sous-chaînes dans une liste, et les rejoindre plus tard:

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)

Cependant, comme nous le verrons dans les timings ci-dessous pour CPython, cela prend plus de temps car CPython peut optimiser la concaténation de chaîne.

Timings

Voici les horaires:

>>> 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 optimise la concaténation de chaînes, tandis que d'autres implémentations ne peuvent pas :

... ne comptez pas sur l'implémentation efficace de CPython de concaténation de chaînes sur place pour les instructions de la forme a + = b ou a = a + b. Cette optimisation est fragile même dans CPython (elle ne fonctionne que pour certains types) et n'est pas du tout présente dans les implémentations qui n'utilisent pas refcounting. Dans les parties sensibles de la performance de la bibliothèque, le formulaire '' .join () doit être utilisé à la place. Cela assurera que la concaténation se produit en temps linéaire à travers différentes implémentations.


Réponse rapide (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
'''

Réponse détaillée

Contexte

Cette réponse est fournie pour répondre à la préoccupation suivante de @odigity:

Sensationnel. J'ai été horrifié au début par la solution proposée par Paolo, mais cela a pris une place de dos à l'horreur que j'ai ressentie en lisant le premier commentaire: "C'est très pythonique, bon travail!" Je suis tellement troublé qu'une communauté si brillante pense que l'utilisation de méthodes si énigmatiques pour quelque chose de si basique est une bonne idée. Pourquoi n'est-ce pas juste s.reverse ()?

Problème

  • Le contexte
    • Python 2.x
    • Python 3.x
  • Scénario:
    • Le développeur veut transformer une chaîne
    • La transformation consiste à inverser l'ordre de tous les personnages

Solution

Pièges

  • Le développeur peut s'attendre à quelque chose comme string.reverse()
  • La solution idiomatique native (aka " pythonic ") peut ne pas être lisible par les nouveaux développeurs
  • Le développeur peut être tenté d'implémenter sa propre version de string.reverse() pour éviter la notation de tranche.
  • La sortie de la notation de tranche peut être contre-intuitive dans certains cas:
    • voir par exemple, example02
      • print 'coup_ate_grouping'[-4:] ## => 'ping'
      • par rapport à
      • print 'coup_ate_grouping'[-4:-1] ## => 'pin'
      • par rapport à
      • print 'coup_ate_grouping'[-1] ## => 'g'
    • les différents résultats de l'indexation sur [-1] peuvent jeter certains développeurs

Raisonnement

Python a une circonstance particulière à connaître: une chaîne est un type iterable .

Une raison pour exclure une méthode string.reverse() est d'inciter les développeurs python à exploiter la puissance de cette circonstance particulière.

En termes simplifiés, cela signifie simplement que chaque caractère d'une chaîne peut être facilement exploité dans le cadre d'un arrangement séquentiel d'éléments, tout comme les tableaux dans d'autres langages de programmation.

Pour comprendre comment cela fonctionne, l'examen de l'exemple 02 peut fournir un bon aperçu.

Exemple02

### 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'

Conclusion

La charge cognitive associée à la compréhension de la façon dont la notation en tranches fonctionne en python peut en effet être trop pour certains adoptants et développeurs qui ne souhaitent pas investir beaucoup de temps dans l'apprentissage de la langue.

Néanmoins, une fois les principes de base compris, la puissance de cette approche par rapport aux méthodes de manipulation de chaînes fixes peut être très favorable.

Pour ceux qui pensent autrement, il existe des approches alternatives, telles que les fonctions lambda, les itérateurs ou les déclarations de fonctions uniques.

Si vous le souhaitez, un développeur peut implémenter sa propre méthode string.reverse (), mais il est bon de comprendre la logique derrière cet aspect de python.

Voir également


Bien sûr, en Python, vous pouvez faire de très belles choses en 1 ligne. :)
Voici une solution simple et polyvalente qui pourrait fonctionner dans n'importe quel langage de programmation.

def reverse_string(phrase):
    reversed = ""
    length = len(phrase)
    for i in range(length):
        reversed += phrase[length-1-i]
    return reversed

phrase = raw_input("Provide a string: ")
print reverse_string(phrase)

En voici un sans [::-1] ou reversed (à des fins d'apprentissage):

def reverse(text):
    new_string = []
    n = len(text)
    while (n > 0):
        new_string.append(text[n-1])
        n -= 1
    return ''.join(new_string)
print reverse("abcd")

vous pouvez utiliser += pour concaténer des chaînes mais join() est plus rapide.


Méthode récursive:

def reverse(s): return s[0] if len(s)==1 else s[len(s)-1] + reverse(s[0:len(s)-1])

Exemple:

print(reverse("Hello!"))    #!olleH

Que diriez-vous:

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

C'est la syntaxe de tranche étendue . Cela fonctionne en faisant [begin:end:step] - en laissant begin et end off et en spécifiant un pas de -1, il inverse une chaîne.


Une autre alternative, (pas efficace! Juste pour montrer la diversité de Python avec autant de solutions possibles!): Convertir la chaîne en liste en utilisant la fonction list (). Une valeur de liste est un type de données modifiable. Nous pouvons donc utiliser la méthode reverse () qui inverse les objets d'une liste en place. Et puis nous convertissons la liste en une chaîne en utilisant la méthode de jointure de liste avec un séparateur vide:

>>> s = 'hello world'
>>> s
'hello world'
>>> t = list(s) # convert to list
>>> t
['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
>>> t.reverse() # reverse method of list
>>> t
['d', 'l', 'r', 'o', 'w', ' ', 'o', 'l', 'l', 'e', 'h']
>>> s = ''.join(t) # convert to string
>>> s
'dlrow olleh'

Une façon moins perplexe de le regarder serait:

string = 'happy'
print(string)

'content'

string_reversed = string[-1::-1]
print(string_reversed)

'yppah'

En anglais [-1 :: - 1] se lit comme suit:

"A partir de -1, aller tout le chemin, en prenant des mesures de -1"


Voici un pas chic:

def reverse(text):
    r_text = ''
    index = len(text) - 1

    while index >= 0:
        r_text += text[index] #string canbe concatenated
        index -= 1

    return r_text

print reverse("hello, world!")

Vous pouvez utiliser la fonction inversée avec une liste compréhensible. Mais je ne comprends pas pourquoi cette méthode a été éliminée en python 3, était inutilement.

string = [ char for char in reversed(string)]

def reverse(input):
    return reduce(lambda x,y : y+x, input)

s = 'hello'
ln = len(s)
i = 1
while True:
    rev = s[ln-i]
    print rev,
    i = i + 1
    if i == ln + 1 :
        break

SORTIE:

o l l e h




string