[aklug] Re: Lists

* Michael Fowler <michael@shoebox.net> [110726 14:44]:
> On Tue, Jul 26, 2011 at 12:17:02PM -0800, Tim Johnson wrote:
> > > Python lists are really well implemented
> > I haven't done any performance tests on lists vs dictionaries -
> > it is really a bit like comparing apples and oranges -
> > I believe python dictionaries are implemented from C linked lists.
>
> dicts in Python are implemented as a hash structure; a given key is run
> through a function to obtain an integer, and that integer is used to
> index into a block of memory. A linked list would be wholly unsuited, as
> lookup time would be horrible.
 I stand corrected. I've been using python since the 'early' part of
 the century, and I do believe that I was at one time informed that
 they were coded in C as linked lists and at that time I was using
 a lot of link-list implementation in C, so the idea (right or
 wrong) stuck or perhaps the original implementation changed.

 Nevertheless, for me, it is very seldom necessary for me to think
 "under the hood" about the underlying source. The one exception
 that comes to mind for me is referencing vs. copying.

 If any explanation is required, I'll explain further ...

> Like most languages implementing a hashing data structure there are
> buckets; when two keys hash to the same value, you can't simply discard
> them, so you make the value a bucket of all the hash collisions.
> Buckets are sometimes implemented as linked lists, sometimes as just an
> array; I'm not sure which Python uses.
>
> --
> Michael Fowler
> www.shoebox.net
> ---------
> To unsubscribe, send email to <aklug-request@aklug.org>
> with 'unsubscribe' in the message body.
>

-- 
Tim 
tim at johnsons-web dot com or akwebsoft dot com
http://www.akwebsoft.com
---------
To unsubscribe, send email to <aklug-request@aklug.org>
with 'unsubscribe' in the message body.