Python: List vs Dict for look up table

Asked 2009-02-04T23:28:41.203

213

I have about 10 million values that I need to put in some type of look up table, so I was wondering which would be more efficient a list or dict?

I know you can do something like this for both:

if something in dict_of_stuff:
    pass

and

if something in list_of_stuff:
    pass

My thought is the dict will be faster and more efficient.

Thanks for your help.

EDIT
Little more info on what I'm trying to do. Euler Problem 92. I'm making a look up table to see if a value calculated has all ready been calculated.

EDIT 2
Efficiency for look up.

EDIT 3
There are no values associated with the value...so would a set be better?

python performance

Edit Report

2 Answers

A dict is a hash table, so it is really fast to find the keys. So between dict and list, dict would be faster. But if you don't have a value to associate, it is even better to use a set. It is a hash table, without the "table" part.

EDIT: for your new question, YES, a set would be better. Just create 2 sets, one for sequences ended in 1 and other for the sequences ended in 89. I have sucessfully solved this problem using sets.

answered 2009-02-04T23:31:41.587

set() is exactly what you want. O(1) lookups, and smaller than a dict.

answered 2009-02-23T19:24:39.140

Python: List vs Dict for look up table

2 Answers

Your Answer