title: Efficient memoization in Python
body: <p>I have some task to solve and the most important part at the moment is to make the script as time-efficient as possible. One of the elements I am trying to optimize is memoization within one of the functions.</p>
  
  <p>So my question is: <strong>Which of the following 3-4 methods is the most efficient / fastest method of implementing memoization in Python?</strong></p>
  
  <p>I have provided code only as an example - if one of the methods is more efficient, but not in the case I mentioned, please share what you know.</p>
  
  <h2>Solution 1 - using mutable variable from outer scope</h2>
  
  <p>This solution is often shown as the example memoization, but I am not sure how efficient it is. I have heard that using global variables (in this case it is variable from outer, not global scope) is less efficient.</p>
  
  <pre><code>def main():
      memo = {}
      def power_div(n):
          try:
              return memo[n]
          except (KeyError):
              memo[n] = (n ** 2) % 4  # example expression, should not matter
              return memo[n]
      # extensive usage of power_div() here
  </code></pre>
  
  <h2>Solution 2 - using default, mutable argument</h2>
  
  <p>I have found somewhere that using default mutable arguments has been used in the past to pass variables from outer scope, when Python searched the variable first in the local scope, then in the global scope, skipping the nonlocal scope (in this case the scope within function <code>main()</code>). Because default argument is initialized only at the time function is defined and is accessible only inside the inner function, maybe it is thus more efficient?</p>
  
  <pre><code>def main():
      def power_div(n, memo={}):
          try:
              return memo[n]
          except (KeyError):
              memo[n] = (n ** 2) % 4  # example expression, should not matter
              return memo[n]
      # extensive usage of power_div() here
  </code></pre>
  
  <p>Or maybe the following version (being in fact a combination of solutions 1&amp;2) is more efficient?</p>
  
  <pre><code>def main():
      memo = {}
      def power_div(n, memo=memo):
          try:
              return memo[n]
          except (KeyError):
              memo[n] = (n ** 2) % 4  # example expression, should not matter
              return memo[n]
      # extensive usage of power_div() here
  </code></pre>
  
  <h2>Solution 3 - function's attribute</h2>
  
  <p>This is another quite common example of memoization in Python - the memoization object is stored as an attribute of the function itself.</p>
  
  <pre><code>def main():
      def power_div(n):
          memo = power_div.memo
          try:
              return memo[n]
          except (KeyError):
              memo[n] = (n ** 2) % 4  # example expression, should not matter
              return memo[n]
      # extensive usage of power_div() here
  </code></pre>
  
  <h2>Summary</h2>
  
  <p>I am very interested in your opinions about the four above solutions for memoization. It is important also, that the function that uses memoization is within another function.</p>
  
  <p>I know that there are also other solutions for memoization (such as <a href="http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize"><code>Memoize</code> decorator</a>), but it is hard for me to believe that this is more efficient solution than these listed above. Correct me if I am wrong.</p>
  
  <p>Thanks in advance.</p>