My first Python program -- a lexer
Steve Holden
steve at holdenweb.com
Mon Nov 24 14:07:51 EST 2008
Thomas Mlynarczyk wrote:
> John Machin schrieb:
>
>> *IF* you need to access the regex associated with a token in O(1)
>> time, a dict is indicated.
>
> O(1) - Does that mean `mydict[mykey]` takes the same amount of time, no
> matter if mydict has 10 or 1000000000 entries? How does this magic work?
> O(log n) I would understand, but constant time?
>
Basically it hashes the key values to locate the corresponding value.
This is a drastic simplification, but if you do a Google search for
"hash tables" you will get the basic idea. Tim Peters, among others, has
spent a lot of time optimizing dict behavior.
>> If you have *both* requirements simultaneously, then *both* list and
>> dict are indicated.
>
> So I would have to duplicate my data and store it once in a list, once
> in a dict? Or should I decide for one way and accept that one type of
> access will not be optimal?
>
Storing the data once in a dict and once in a list doesn't duplicate the
data, since both structures will (optimally: i.e. if you do it right)
refer to the same data objects.
Generally speaking, do what's convenient to do as a programmer, and work
on it if there are serious inadequacies.
regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/
More information about the Python-list
mailing list