Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > RE: Dictionary .keys() and .values() should return a set [withPython3000 in mind]

Reply
Thread Tools

RE: Dictionary .keys() and .values() should return a set [withPython3000 in mind]

 
 
Delaney, Timothy (Tim)
Guest
Posts: n/a
 
      07-02-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> This has been bothering me for a while. Just want to find out if it
> just me or perhaps others have thought of this too: Why shouldn't the
> keyset of a dictionary be represented as a set instead of a list?


There has been much discussion of this on the Python-3000 mailing list.
Suggestings included making keys(), etc return an iterator, and getting
rid of iterkeys(), etc.

The eventual consensus was that keys(), etc should return views on the
dictionary. These views would be re-iterable and will have basically the
same behaviour as the lists returned from keys(), etc. However, such a
view could have O(1) __contains__ behaviour, and would not incur the
overhead of creating a list and populating it - they would be backed by
the dictionary. Of course, this introduces the issue of concurrent
modification, but you can always get an independent copy by calling
list(dict.keys()).

Tim Delaney
 
Reply With Quote
 
 
 
 
Paul Rubin
Guest
Posts: n/a
 
      07-03-2006
"Delaney, Timothy (Tim)" <(E-Mail Removed)> writes:
> The eventual consensus was that keys(), etc should return views on the
> dictionary. These views would be re-iterable and will have basically the
> same behaviour as the lists returned from keys(), etc. However, such a
> view could have O(1) __contains__ behaviour, and would not incur the
> overhead of creating a list and populating it - they would be backed by
> the dictionary. Of course, this introduces the issue of concurrent
> modification, but you can always get an independent copy by calling
> list(dict.keys()).


Wait a sec, you're saying

k0 = d.keys()
d['whee'] = 'parrot' # this can change k0???

That sounds broken.
 
Reply With Quote
 
 
 
 
cmdrrickhunter@yaho.com
Guest
Posts: n/a
 
      07-03-2006
Yes, this is what he's saying. Its not "broken," just a bit different.
After all, you dont have a problem with:
lst = [1, 2, 3]
ptr = lst
lst.append(4) # this changes ptr

And a "view" of the dictionary is orders faster than creating a copy of
it (which is required to keep k0 from changing in your example). If
you're LUCKY, copying a dictionary is O(n), and i would expect it to
take longer because hashmaps usually have a lot of empty space in them
(anyone with python specific experiance know if its diffent for python
hashmaps?), and each empty space takes time to iterate across. So a
dictionary is over O(n), while a view takes O(1) time. considering how
often this operation is used, it makes sense to do this optimization

And if you really want an independant list, you can always say
k0 = list(d.keys())

Paul Rubin wrote:
>
> Wait a sec, you're saying
>
> k0 = d.keys()
> d['whee'] = 'parrot' # this can change k0???
>
> That sounds broken.


 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      07-03-2006
"(E-Mail Removed)" <(E-Mail Removed)> writes:
> And a "view" of the dictionary is orders faster than creating a copy of
> it (which is required to keep k0 from changing in your example). If
> you're LUCKY, copying a dictionary is O(n),


There are ways to do it so you don't have to copy, but the dict would
then no longer be a straightforward hash table.
 
Reply With Quote
 
cmdrrickhunter@yaho.com
Guest
Posts: n/a
 
      07-03-2006
Ooh, can you point me to them? This sounds very interesting.

The only way I can think of doing it is to have some fun with pointers
and not make the final copy until a change is made to the table. I'd
love to read about an algoritm which can get around this! I feel so
behind in the times, I still prefer the simpliciy of the redblacktree
sometimes =p
Paul Rubin wrote:
> There are ways to do it so you don't have to copy, but the dict would
> then no longer be a straightforward hash table.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
creating a dictionary from a dictionary with regex james_027 Python 1 08-22-2007 07:39 AM
Dictionary .keys() and .values() should return a set [with Python 3000 in mind] vatamane@gmail.com Python 14 07-04-2006 07:36 AM
RE: Dictionary .keys() and .values() should return a set[withPython3000 in mind] Delaney, Timothy (Tim) Python 2 07-03-2006 09:49 AM
[DICTIONARY] - Copy dictionary entries to attributes Ilias Lazaridis Python 6 02-21-2006 11:27 AM
what value does lack of return or empty "return;" return Greenhorn C Programming 15 03-06-2005 08:19 PM



Advertisments