Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; b=XeqB6+mVQDMeSLiuZ0ikPN3KK1IRpismwOWvoaubHSDPzmOw/F1Q4w9EPylHETm2L/ kWHGoyRSrzqzCJ4Akam+u9OQFMWPnvCUT+m5R5LxT4XMTfGEfTxetGUK3EU3uUlfYp4I JSMs50N8VU82Nk/8JnHL5U46Y/SaPq21lKrOI=
MIME-Version: 1.0
In-Reply-To: <BANLkTikQ8cR72PPqxrv5ajFrQnDBg5NN5A@mail.gmail.com>
References: <cec1aa77-86b3-4bff-8286-a84c823750d2@glegroupsg2000goo.googlegroups.com> <BANLkTikQ8cR72PPqxrv5ajFrQnDBg5NN5A@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 30 May 2011 10:32:27 -0600
Subject: Re: searching in list
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2274.1306773179.9059.python-list@python.org>
Lines: 40
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:6666

On Mon, May 30, 2011 at 7:41 AM, Chris Angelico <rosuav@gmail.com> wrote:
> If you're always going to look them up by the argument, the best way
> would be to use a dictionary:
> cache=3D{arg1: res1, arg2: res2, ...}
>
> Then you can search with a simple: cache[arg135]
>
> You can add things with: cache[arg135]=3Dres135
>
> This works best if the argument is an immutable and fairly simple
> type. For instance, you could calculate Fibonacci numbers in a naive
> and straightforward way:
>
> def fib(n,cache=3D{}):
> =A0if n in cache: return cache[n]
> =A0ret=3Dn if n<2 else fib(n-1)+fib(n-2) # This bit actually calculates f=
ib(n)
> =A0cache[n]=3Dret
> =A0return ret
>
> Of course, this is a poor algorithm for calculating Fibonacci numbers,
> but it does demonstrate the cache. It's recursive, meaning that if it
> has fib(50) in its cache and it is asked for fib(60), it will find and
> make use of the cached element.
>
> (Note the sneaky way of storing a cache dictionary. A function's
> default arguments are evaluated once, so this will use the same
> dictionary for every call.)

If you're using Python 3.2, the functools.lru_cache decorator will do
the caching for you, and without modifying the function arguments.  By
default it stores only the 100 most recent results, but you can make
the storage unbounded by passing in the argument maxsize=3DNone.  Then
the Fibonacci example becomes:

@functools.lru_cache(maxsize=3DNone)
def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)