Structures

Aaron Brady castironpi at gmail.com
Tue Nov 4 02:06:07 CET 2008


On Nov 3, 6:33 pm, George Sakkis <george.sak... at gmail.com> wrote:
> On Nov 3, 6:32 pm, "Paulo J. Matos" <pocma... at gmail.com> wrote:
>
> > Even though I can use dicts where the keys are strings (as if it were
> > the name of the field), it seems to heavy, since a structure doesn't
> > need to be resizable (and dicts are) and it has constant time access
> > (which depending on the implementation I would guess dicts don't
> > have).
>
> > Can someone please clarify?
>
> For all practical purposes, dicts have almost constant access time (at
> least with any half-decent __hash__  method).

Hash tables are slick, but their hash function is their weakest link.

>>> [ hash( 2**x ) for x in range( 0, 256, 32 ) ]
[1, 1, 1, 1, 1, 1, 1, 1]

Such an index gives you linear-time performance in finding elements.
Ha!  Plus, your worst-case insertion will cause a copy of the entire
table.  There aren't any mappings based on balanced trees,
unfortunately.



More information about the Python-list mailing list