3
votes

Une boucle "for ... in" en Python augmente-t-elle la complexité de l'espace?

Disons que j'avais la fonction suivante:

def findNumVowels(s):
    vowels = ['a', 'e', 'i', 'o', 'u']
    numVowels = 0
    for char in s:
        if char in vowels:
            numVowels += 1
    return numVowels

print(findNumVowels("hello world")) # 3

La boucle for ... in ajouterait-elle à la complexité spatiale de cette fonction en créant une nouvelle chaîne pour chaque char dans s , ou est-ce que ce sucre syntaxique fait abstraction du fait que nous accédons à un index spécifique d'une chaîne?

python python-3.x big-o

2 commentaires

non cela n'augmente pas la complexité de l'espace

Notez que l'indexation dans un objet str crée de toute façon un nouvel objet str . Mais tout cela n'a aucun rapport avec la complexité de l'espace.

3 Réponses :

0
votes

Voici une version avec compréhension de liste:

def findNumVowels(s):
    vowels = ['a', 'e', 'i', 'o', 'u']
    return len([char_literal for char_literal in s if char_literal in vowels])

findNumVowels("Kunal")

Comme vous pouvez le voir, les chaînes Python sont immuables, ce qui signifie qu'elles ne peuvent pas être modifiées après leur création. Nous indexons simplement la chaîne avec la construction for..in, ce qui ne prend pas de complexité d'espace supplémentaire.

2 commentaires

Les boucles for avec dans n'indexent pas l'itérable. Essayez une boucle for et changez la variable temporaire dans le corps de la boucle.

Notez que votre version ici crée une complexité d'espace O (N) car vous matérialisez une liste qui dépend de la taille de la chaîne.

3
votes

Non, la boucle en elle-même ne le fait pas. Considérez:

for char in some_string:
    print(char)

Il ne nécessite qu'un seul objet supplémentaire de taille constante. C'est constant par rapport à la taille de la chaîne . Donc, peu importe si ma chaîne contient 10 ou 1000 caractères, elle nécessite toujours une str supplémentaire pour la boucler. Par conséquent, cela prend un espace constant.

3 commentaires

Ne nécessiterait-il pas n objets supplémentaires où n est la longueur de la chaîne? Les tailles des chaînes peuvent être fixes, mais en ce qui concerne la fonction dans son ensemble, la quantité d'espace supplémentaire utilisée dépendrait de la taille de l'entrée.

@KyleU Vous créez de nouveaux objets mais n'en avez qu'un à la fois. Maintenant, si vous les accumuliez dans une liste par exemple, cela nécessiterait un espace O (N). Avec la boucle ci-dessus, les objets sont créés et détruits à chaque itération.

cela semble être correct. Je regarde maintenant le comptage de références Python et le ramasse-miettes et il semble que s'il n'y a pas de références à char , il est immédiatement désalloué.

0
votes

Premièrement, la réponse qui vous tient à cœur est que la boucle for n'ajoute en fait pas à la complexité de l'espace. Cependant, si vous travaillez avec de grands tableaux, la complexité temporelle de la boucle for est très faible. Il est recommandé d'utiliser une opération vectorisée au lieu de plusieurs boucles for. Par exemple, numpy.dot () , qui est très courant en machine learning ou en deep learning.

1 commentaires

L'utilisation de tableaux numpy n'aiderait pas la complexité temporelle ou spatiale.