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

Discussion in 'Python' started by Delaney, Timothy (Tim), Jul 3, 2006.

  1. 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
    Delaney, Timothy (Tim), Jul 3, 2006
    #1
    1. Advertising

  2. Delaney, Timothy (Tim)

    Paul Rubin Guest

    Re: Dictionary .keys() and .values() should return a set [with Python3000 in mind]

    "Delaney, Timothy (Tim)" <> 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.
    Paul Rubin, Jul 3, 2006
    #2
    1. Advertising

  3. Delaney, Timothy (Tim)

    Guest

    Re: Dictionary .keys() and .values() should return a set [with Python3000 in mind]

    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.
    , Jul 3, 2006
    #3
  4. Delaney, Timothy (Tim)

    Paul Rubin Guest

    Re: Dictionary .keys() and .values() should return a set [with Python3000 in mind]

    "" <> 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.
    Paul Rubin, Jul 3, 2006
    #4
  5. Delaney, Timothy (Tim)

    Guest

    Re: Dictionary .keys() and .values() should return a set [with Python3000 in mind]

    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.
    , Jul 3, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Christoph Zwerschke

    Why is dictionary.keys() a list and not a set?

    Christoph Zwerschke, Nov 23, 2005, in forum: Python
    Replies:
    90
    Views:
    1,627
    Mike Meyer
    Nov 29, 2005
  2. Girish Sahani
    Replies:
    11
    Views:
    606
    Roberto Bonvallet
    Jun 7, 2006
  3. Replies:
    14
    Views:
    578
    Antoon Pardon
    Jul 4, 2006
  4. Delaney, Timothy (Tim)
    Replies:
    2
    Views:
    303
  5. ++imanshu
    Replies:
    7
    Views:
    245
Loading...

Share This Page