Je pense à optimiser mon code en omettant certains appels récursifs et en les remplaçant par des boucles while ou autres boucles itératives.

La fonction récursive est la suivante:

def repr(e):
    if isinstance(e, (list, tuple)):
        return "(%s)" % " ".join(map(repr, e))
    return str(e)

La sortie pour repr([1, [2, [3, 4]]]) est (1 (2 (3 4)))

Existe-t-il un moyen de remplacer map-part par la boucle while dans ce cas? Je voudrais tester la différence de performances entre différentes façons de le faire.

0
MarkokraM 12 mars 2019 à 08:55

2 réponses

Meilleure réponse

Le nom repr appartient déjà à une fonction intégrée Python, donc plutôt que de le redéfinir, supposons que votre code soit:

def my_repr(e):
    if isinstance(e, (list, tuple)):
        return "(%s)" % " ".join(map(my_repr, e))

    return str(e)

En supposant que vous ne vouliez pas faire une simple manipulation de chaîne, mais plutôt parcourir la liste, nous pourrions remplacer la pile de récursion implicite par une pile explicite :

def my_repr(e):
    stack = [e]

    result = ""

    while stack:
        item = stack.pop()

        if isinstance(item, (list, tuple)):
            stack.append(")")
            stack.extend(reversed(item))
            result += "("
        elif item == ")":
            result += item
        else:
            result += str(item) + " "

    return result

Ce qui précède est grossier et ne formate pas parfaitement la chaîne, mais peut être suffisant pour le chronométrage. L'avantage par rapport à l'approche de manipulation de chaîne de @shotgunner est que vous pouvez faire des choses plus complexes avec item dans le cadre de l'ajout à la chaîne, par exemple:

            result += str(item * item) + " "

Où votre chaîne de sortie contient maintenant les carrés des nombres dans la structure d'entrée. Ou peu importe.

Sur le plan temporel, vous constaterez que cet exemple non récursif est plus lent que votre exemple récursif. Ils font tous deux essentiellement la même quantité de travail, mais le récursif en fait plus au niveau C et le non récursif en fait plus en Python. Et celui non récursif devrait être repensé pour ne pas avoir besoin d'un appel à reversed(). Un avantage de cette implémentation non récursive est qu'une grande entrée complexe ne doit pas déclencher la limitation de la pile d'appels de Python, comme celle récursive.

1
cdlane 12 mars 2019 à 06:42
def repr(e):
    return str(e).replace("[", "(").replace("]", ")").replace(",", " ")

Exemple:

>>> repr([1, [2, [3, 4]]])
'(1 (2 (3 4)))'

Pour tester les performances, vous pouvez utiliser le module timeit comme ceci:

import timeit

def repr1(e):
    if isinstance(e, (list, tuple)):
        return "(%s)" % " ".join(map(repr, e))
    return str(e)

def repr2(e):
    return str(e).replace("[", "(").replace("]", ")").replace(",", " ")


duration1 = timeit.timeit('repr1([1, [2, [3, 4]]])', 'from __main__ import repr1',number=1000)
duration2 = timeit.timeit('repr2([1, [2, [3, 4]]])', 'from __main__ import repr2', number=1000)

print(duration1, duration2)

Pour des listes plus grandes comme list(range(10000)):

print(duration1, duration2)
# 1.0414706510000542 0.7595879010000317

Vous pouvez également utiliser str.translate():

def repr3(e):
    table = str.maketrans("[],", "() ")
    return str(e).translate(table)
1
shotgunner 12 mars 2019 à 06:44