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/ -- http://mail.python.org/mailman/listinfo/python-list
