My first Python program -- a lexer
Arnaud Delobelle
arnodel at googlemail.com
Mon Nov 24 15:25:10 EST 2008
Thomas Mlynarczyk <thomas at mlynarczyk-webdesign.de> writes:
> 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?
As I understand it, in theory it's not O(1) - I guess it's O(n). But
for any non-cunningly crafted data it's as if it was O(1).
Dictionaries are implemented as hashtables, not as trees.
>> 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?
Depends what you want to do!
--
Arnaud
More information about the Python-list
mailing list