Avoid variable recomputation?

Question

I have a line code like this -

while someMethod(n) < length and List[someMethod(n)] == 0:
    # do something
    n += 1

where someMethod(arg) does some computation on the number n. The problem with this code is that I'm doing the same computation twice, which is something I need to avoid.

One option is to do this -

x = someMethod(n)
while x < length and List[x] == 0:
    # do something
    x = someMethod(n + 1)

I am storing the value of someMethod(n) in a variable x and then using it later. However, the problem with this approach is that the code is inside a recursive method which is called multiple times. As a result, a lot of excess instances of variables x are being created which slows the code down.

Here's the snipped of the code -

def recursion(x, n, i):
    while someMethod(n) < length and List[someMethod(n)] == 0:
        # do something
        n += 1
    # some condition
    recursion(x - 1, n, someList(i + 1))

and this recursion method is called many times throughout the code and the recursion is quite deep. Is there some alternative available to deal with a problem like this?

Please try to be language independent if possible.

An int on the stack doesn't slow anything down, not in Java, not in C, not in C++, not in FORTRAN, not in Pascal, not in ALGOL 60, not in... — laune
– laune, Commented Nov 9, 2015 at 11:12
It's hard to understand this without a complete example... in particular, the claim that "excess instances of variables x are being created which slows the code down" really requires a bit more justification... — Jon Skeet
– Jon Skeet, Commented Nov 9, 2015 at 11:13
I have edited the question. It's still quite hard to justify my code because it quite complex. Hope the new edit help. — Arulx Z
– Arulx Z, Commented Nov 9, 2015 at 11:20
If you want a language independent answer why did you tag it with python? (if someone else added that tag, perhaps you should roll back that edit). — John Coleman
– John Coleman, Commented Nov 9, 2015 at 11:35

Illarion Kovalchuk · Accepted Answer · 2015-11-09 11:19:05Z

1

You can use memoization with decorators technique:

def memoize(f):
    memo = dict()
    def wrapper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return wrapper

@memoize
def someMethod(x):
    return <your computations with x>

answered Nov 9, 2015 at 11:19

Illarion Kovalchuk

5,9028 gold badges46 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dmitry Zagorulkin Over a year ago

OP says that "please be language agnostic"

Arulx Z Over a year ago

Firstly, thanks for the answer. Memoization like this is not really useful for me because the code is called so many times that the memoization itself slows the code down.

Erwin Bolwidt Over a year ago

@ZagorulkinDmitry the OP's request in this regard is not appropriate for SO - then he should have asked it on programmers or cs - SO is about concrete programming problems

Dmitry Zagorulkin · Accepted Answer · 2015-11-09 11:18:47Z

0

As i understand your code correctly you are looking for some sort of memorization.

https://en.wikipedia.org/wiki/Memoization

it means that on every recursive call you have to save as mush as possible past calculations to use it in current calculation.

answered Nov 9, 2015 at 11:18

Dmitry Zagorulkin

8,5684 gold badges39 silver badges63 bronze badges

4 Comments

Arulx Z Over a year ago

Thanks for your answer. I tried using memoization but with no luck. The code is called so many times that memoization itself slows down the code.

Dmitry Zagorulkin Over a year ago

@ArulxZ i did't see any form of memorization in your code

Arulx Z Over a year ago

I mean I tried it but I removed it later because it wasn't really useful. The results for someMethod(n) and someMethod(m) are almost never same.

John Coleman Over a year ago

@ArulxZ memoization isn't a panacea which magically converts bad recursive algorithms into good recursive algorithms. It can lead to dramatic improvements -- but can also lead to degradation due to overhead. If it doesn't help you then it doesn't help you, though in that case it seems odd that you asked about it. If you have a subcase of input for which it would be helpful, perhaps you could create a memoized helper function to handle the subcase.

Collectives™ on Stack Overflow

Avoid variable recomputation?

2 Answers 2

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related