I thinking of optimizing my code by leaving out some recursive calls and replacing them by while or other iterative loops.
Recursive function is this:
def repr(e):
if isinstance(e, (list, tuple)):
return "(%s)" % " ".join(map(repr, e))
return str(e)
Output for repr([1, [2, [3, 4]]]) is (1 (2 (3 4)))
Is there a way to replace map-part with while loop in this case? I'd like to test the performance difference between different ways of doing it.
The name repr already belongs to a Python built-in function, so rather than redefine it, let's assume your code is:
def my_repr(e):
if isinstance(e, (list, tuple)):
return "(%s)" % " ".join(map(my_repr, e))
return str(e)
Assuming you don't want to do a simple string manipulation, but rather actually walk the list, we could replace the implicit recursion stack with an explicit stack:
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
The above is crude, and doesn't format the string perfectly, but may be good enough for timing purposes. The advantage over the string manipulation approach by @shotgunner is that you can do more complex things with item as part of adding it to the string, for example:
result += str(item * item) + " "
Where your output string now contains the squares of the numbers in the input structure. Or whatever.
Timing-wise, you'll find that this non-recursive example is slower than your recursive one. They're both basically doing the same amount of work, but the recursive one is doing more at the C level and the non-recursive one is doing more in Python. And the non-recursive one should be redesigned not to need a call to reversed(). One advantange of this non-recursive implementation is that large, complex input shouldn't trip Python's call stack limitation, like the recursive one.
def repr(e):
return str(e).replace("[", "(").replace("]", ")").replace(",", " ")
example:
>>> repr([1, [2, [3, 4]]])
'(1 (2 (3 4)))'
for testing the performance you can use timeit module like this:
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)
for bigger lists like list(range(10000)):
print(duration1, duration2)
# 1.0414706510000542 0.7595879010000317
you can also use str.translate():
def repr3(e):
table = str.maketrans("[],", "() ")
return str(e).translate(table)
repr3 makes double whitespaces, which could be removed with .replace(" ", " "). I was also looking for Python pprint module if it could do the job...