Structures
Aaron Brady
castironpi at gmail.com
Mon Nov 3 20:06:07 EST 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