[Tutor] Projects (fwd)

[John Fouhy]

On 24/01/2008, Ricardo Aráoz <ricaraoz at gmail.com> wrote:
> Isn't dictionary access faster than list access? Why are three lists
> 'much more efficient'?

Well, not necessarily.

If you want a dictionary, you could use a list of tuples:

myDict = [('a', 'one'), ('b', 'two), ('c', 'three')]

Then you could do lookup as:

def lookup(key, listDict):
    for k, v in listDict:
        if k == key:
            return v

But, as you say, this would be a lot slower than using a dict (lookup
time is proportional to the length of the list for this naive
dictionary, whereas lookup time is essentially constant with a dict).

However, in this case, the keys are integers starting from 0 with no
holes.  Instead of having to search, our lookup is just:

    return digits[i]

which is also constant time.

If you really want to know which is faster, the timeit module is your
friend.  Here's what my computer says:

Morpork:~ repton$ python -m timeit -s 'd = {0:"zero", 1:"one",
2:"two", 3:"three", 4:"four", 5:"five", 6:"six", 7:"seven", 8:"eight",
9:"nine"}' 'd[5]'
10000000 loops, best of 3: 0.127 usec per loop
Morpork:~ repton$ python -m timeit -s 'd = ["zero", "one", "two",
"three", "four", "five", "six", "seven", "eight", "nine"]' 'd[5]'
10000000 loops, best of 3: 0.102 usec per loop

So, if that extra 25 nanoseconds is important to you, definitely go
with the list!

-- 
John.