Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #89456 > unrolled thread

Wrote a memoize function: I do not mind feedback

Back to article view | Back to comp.lang.python

Contents

  Wrote a memoize function: I do not mind feedback Cecil Westerhof <Cecil@decebal.nl> - 2015-04-27 15:35 +0200
    Re: Wrote a memoize function: I do not mind feedback Peter Otten <__peter__@web.de> - 2015-04-27 16:28 +0200
    Re: Wrote a memoize function: I do not mind feedback Albert-Jan Roskam <fomcl@yahoo.com> - 2015-04-27 20:35 +0000
      Re: Wrote a memoize function: I do not mind feedback Cecil Westerhof <Cecil@decebal.nl> - 2015-04-29 08:06 +0200
        Re: Wrote a memoize function: I do not mind feedback Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-29 01:02 -0600
          Re: Wrote a memoize function: I do not mind feedback Cecil Westerhof <Cecil@decebal.nl> - 2015-04-29 10:04 +0200
            Re: Wrote a memoize function: I do not mind feedback Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-29 09:58 +0100
              Re: Wrote a memoize function: I do not mind feedback Cecil Westerhof <Cecil@decebal.nl> - 2015-04-29 13:52 +0200

#89456 — Wrote a memoize function: I do not mind feedback

I started again with Python. In Clojure you have memoize. I thought it
nice to have this in Python also. So I wrote it. With a Fibonacci
function to show the usefulness.
You can find it here:
    https://github.com/CecilWesterhof/PythonLibrary

I love to hear what you think of it.

And ideas for other functionalities are welcome also. Übung macht den
Meister.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [next] | [standalone]

#89459

Cecil Westerhof wrote:

> I started again with Python. In Clojure you have memoize. I thought it
> nice to have this in Python also. So I wrote it. With a Fibonacci
> function to show the usefulness.
> You can find it here:
>     https://github.com/CecilWesterhof/PythonLibrary
> 
> I love to hear what you think of it.
> 
> And ideas for other functionalities are welcome also. Übung macht den
> Meister.

See also: 

https://docs.python.org/dev/library/functools.html#functools.lru_cache

A bit hard to find unless you already know it's there.

[toc] | [prev] | [next] | [standalone]

#89469

----- Original Message -----
> From: Peter Otten <__peter__@web.de>
> To: python-list@python.org
> Cc: 
> Sent: Monday, April 27, 2015 4:28 PM
> Subject: Re: Wrote a memoize function: I do not mind feedback
> 
> Cecil Westerhof wrote:
> 
>>  I started again with Python. In Clojure you have memoize. I thought it
>>  nice to have this in Python also. So I wrote it. With a Fibonacci
>>  function to show the usefulness.
>>  You can find it here:
>>     https://github.com/CecilWesterhof/PythonLibrary
>> 
>>  I love to hear what you think of it.
>> 
>>  And ideas for other functionalities are welcome also. Übung macht den
>>  Meister.
> 
> See also: 
> 
> https://docs.python.org/dev/library/functools.html#functools.lru_cache
> 
> A bit hard to find unless you already know it's there.

If you Google for memoization decorator, you will easily find many more implementations. Not 100 percent sure, but I think the LRU cache decorator was not exactly light weight. I also like this one from Martelli's Python Cookbook, where he uses a mutable default argument {a dictionary} to implement memoization. I believe I went like this:


def some_func(arg, _memoize={}):
    try:
        return _memoize[arg]
    except KeyError:
        result = some_expensive_operation(arg)
        _memoize[arg] = result
        return result

[toc] | [prev] | [next] | [standalone]

#89518

Op Monday 27 Apr 2015 22:35 CEST schreef Albert-Jan Roskam:

> ----- Original Message -----
>> From: Peter Otten <__peter__@web.de>
>> To: python-list@python.org
>> Cc: 
>> Sent: Monday, April 27, 2015 4:28 PM
>> Subject: Re: Wrote a memoize function: I do not mind feedback
>>
>> Cecil Westerhof wrote:
>>
>>> I started again with Python. In Clojure you have memoize. I
>>> thought it nice to have this in Python also. So I wrote it. With a
>>> Fibonacci function to show the usefulness. You can find it here:
>>> https://github.com/CecilWesterhof/PythonLibrary
>>>
>>> I love to hear what you think of it.
>>>
>>> And ideas for other functionalities are welcome also. Übung macht
>>> den Meister.
>>
>> See also: 
>>
>> https://docs.python.org/dev/library/functools.html#functools.lru_cache
>>
>> A bit hard to find unless you already know it's there.
>
> If you Google for memoization decorator, you will easily find many
> more implementations. Not 100 percent sure, but I think the LRU
> cache decorator was not exactly light weight. I also like this one
> from Martelli's Python Cookbook, where he uses a mutable default
> argument {a dictionary} to implement memoization. I believe I went
> like this:
>
>
> def some_func(arg, _memoize={}):
> try:
> return _memoize[arg]
> except KeyError:
> result = some_expensive_operation(arg)
> _memoize[arg] = result
> return result

That is in a way the same as what I do, except I do not use an
exception. Iunderstand it is not as expensive as it was anymore, but I
do not like to use an exception (when not necessary).

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#89526

On Wed, Apr 29, 2015 at 12:06 AM, Cecil Westerhof <Cecil@decebal.nl> wrote:
> Op Monday 27 Apr 2015 22:35 CEST schreef Albert-Jan Roskam:
>> def some_func(arg, _memoize={}):
>> try:
>> return _memoize[arg]
>> except KeyError:
>> result = some_expensive_operation(arg)
>> _memoize[arg] = result
>> return result
>
> That is in a way the same as what I do, except I do not use an
> exception. Iunderstand it is not as expensive as it was anymore, but I
> do not like to use an exception (when not necessary).

It's useful to keep in mind which case it is that you're trying to
optimize. The expensive case for exceptions is when one actually gets
raised. A try that doesn't raise an exception is pretty cheap,
probably cheaper than looking up the key in the dict twice as the code
you linked does. Compare:

>>> from timeit import timeit
>>> timeit("if x in y: y[x]", setup="x = 1; y = {1: 2}")
0.2224265851985905
>>> timeit("""
... try:
...     y[x]
... except KeyError:
...     pass
... """, setup="x = 1; y = {1: 2}")
0.15237198271520924

On the other hand, if the KeyError does get raised, then it will be
more expensive, but that would already be the expensive case for
memoized function, and if that computation isn't significantly more
expensive than the cost of raising an exception, then it probably
isn't worth memoizing in the first place.

Regardless of which way you write it, this sort of micro-optimization
hardly ever matters, and in the situations where it does matter,
you'll gain much more performance by rewriting in C than by
obsessively tuning your Python code.

[toc] | [prev] | [next] | [standalone]

#89528

Op Wednesday 29 Apr 2015 09:02 CEST schreef Ian Kelly:

> On Wed, Apr 29, 2015 at 12:06 AM, Cecil Westerhof <Cecil@decebal.nl> wrote:
>> Op Monday 27 Apr 2015 22:35 CEST schreef Albert-Jan Roskam:
>>> def some_func(arg, _memoize={}):
>>> try:
>>> return _memoize[arg]
>>> except KeyError:
>>> result = some_expensive_operation(arg)
>>> _memoize[arg] = result
>>> return result
>>
>> That is in a way the same as what I do, except I do not use an
>> exception. Iunderstand it is not as expensive as it was anymore,
>> but I do not like to use an exception (when not necessary).
>
> It's useful to keep in mind which case it is that you're trying to
> optimize. The expensive case for exceptions is when one actually
> gets raised. A try that doesn't raise an exception is pretty cheap,
> probably cheaper than looking up the key in the dict twice as the
> code you linked does. Compare:

It is not only performance wise, I find the code without the try also
better looking. But that is very personally I suppose.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#89531

On 29/04/2015 09:04, Cecil Westerhof wrote:
> Op Wednesday 29 Apr 2015 09:02 CEST schreef Ian Kelly:
>
>> On Wed, Apr 29, 2015 at 12:06 AM, Cecil Westerhof <Cecil@decebal.nl> wrote:
>>> Op Monday 27 Apr 2015 22:35 CEST schreef Albert-Jan Roskam:
>>>> def some_func(arg, _memoize={}):
>>>> try:
>>>> return _memoize[arg]
>>>> except KeyError:
>>>> result = some_expensive_operation(arg)
>>>> _memoize[arg] = result
>>>> return result
>>>
>>> That is in a way the same as what I do, except I do not use an
>>> exception. Iunderstand it is not as expensive as it was anymore,
>>> but I do not like to use an exception (when not necessary).
>>
>> It's useful to keep in mind which case it is that you're trying to
>> optimize. The expensive case for exceptions is when one actually
>> gets raised. A try that doesn't raise an exception is pretty cheap,
>> probably cheaper than looking up the key in the dict twice as the
>> code you linked does. Compare:
>
> It is not only performance wise, I find the code without the try also
> better looking. But that is very personally I suppose.
>

You might find this interesting 
http://www.jeffknupp.com/blog/2013/02/06/write-cleaner-python-use-exceptions/

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#89545

Op Wednesday 29 Apr 2015 10:58 CEST schreef Mark Lawrence:

>> It is not only performance wise, I find the code without the try
>> also better looking. But that is very personally I suppose.
>>
>
> You might find this interesting
> http://www.jeffknupp.com/blog/2013/02/06/write-cleaner-python-use-exceptions/

I certainly agree in the print_object case. Well maybe I have to get
used to python again. ;-)

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web