Thomas Mlynarczyk <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list