Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #67054 > unrolled thread

intersection, union, difference, symmetric difference for dictionaries

Back to article view | Back to comp.lang.python

Contents

  intersection, union, difference, symmetric difference for dictionaries mauro <mauro@gmail.com> - 2014-02-25 20:32 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries Nick Timkovich <prometheus235@gmail.com> - 2014-02-25 14:37 -0600
    Re: intersection, union, difference, symmetric difference for dictionaries Skip Montanaro <skip@pobox.com> - 2014-02-25 14:40 -0600
    Re: intersection, union, difference, symmetric difference for dictionaries Peter Otten <__peter__@web.de> - 2014-02-25 21:53 +0100
    Re: intersection, union, difference, symmetric difference for dictionaries Peter Otten <__peter__@web.de> - 2014-02-25 21:58 +0100
    Re: intersection, union, difference, symmetric difference for dictionaries Tim Chase <python.list@tim.thechases.com> - 2014-02-25 15:03 -0600
      Re: intersection, union, difference, symmetric difference for dictionaries Duncan Booth <duncan.booth@invalid.invalid> - 2014-02-25 22:21 +0000
        Re: intersection, union, difference, symmetric difference for dictionaries Tim Chase <tim@thechases.com> - 2014-02-25 16:35 -0600
        Re: intersection, union, difference, symmetric difference for dictionaries Tim Chase <python.list@tim.thechases.com> - 2014-02-25 16:36 -0600
        Re: intersection, union, difference, symmetric difference for dictionaries Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-25 22:58 +0000
      Re: intersection, union, difference, symmetric difference for dictionaries Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-25 23:10 +0000
        Re: intersection, union, difference, symmetric difference for dictionaries Tim Chase <python.list@tim.thechases.com> - 2014-02-25 20:21 -0600
    Re: intersection, union, difference, symmetric difference for dictionaries Ben Finney <ben+python@benfinney.id.au> - 2014-02-26 08:27 +1100
    Re:intersection, union, difference, symmetric difference for dictionaries Dave Angel <davea@davea.name> - 2014-02-25 16:35 -0500
    Re: intersection, union, difference, symmetric difference for dictionaries Peter Otten <__peter__@web.de> - 2014-02-25 22:54 +0100
    Re: intersection, union, difference, symmetric difference for dictionaries mauro <mauro@gmail.com> - 2014-02-25 22:02 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries mauro <mauro@gmail.com> - 2014-02-25 22:03 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries Tim Chase <python.list@tim.thechases.com> - 2014-02-25 16:10 -0600
    Re: intersection, union, difference, symmetric difference for dictionaries mauro <mauro@gmail.com> - 2014-02-25 22:11 +0000
      Re: intersection, union, difference, symmetric difference for dictionaries Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-25 22:35 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries MRAB <python@mrabarnett.plus.com> - 2014-02-25 23:07 +0000
      Re: intersection, union, difference, symmetric difference for dictionaries Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-26 00:37 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries Ben Finney <ben+python@benfinney.id.au> - 2014-02-26 10:14 +1100
    Re: intersection, union, difference, symmetric difference for dictionaries MRAB <python@mrabarnett.plus.com> - 2014-02-25 23:25 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries Grant Edwards <invalid@invalid.invalid> - 2014-02-25 20:44 +0000
    Re: intersection, union, difference, symmetric difference for dictionaries John Gordon <gordon@panix.com> - 2014-02-25 20:44 +0000
      Re: intersection, union, difference, symmetric difference for dictionaries Chris Angelico <rosuav@gmail.com> - 2014-03-02 09:29 +1100

Page 1 of 2  [1] 2  Next page →

#67054 — intersection, union, difference, symmetric difference for dictionaries

 Dictionaries and sets share a few properties:
- Dictionaries keys are unique as well as sets items
- Dictionaries and sets are both unordered
- Dictionaries and sets are both accessed by key
- Dictionaries and sets are both mutables

So I wonder why operations such us intersection, union, difference, 
symmetric difference that are available for sets and are not available 
for dictionaries without going via key dictviews. 

[toc] | [next] | [standalone]

#67055

On Tue, Feb 25, 2014 at 2:32 PM, mauro <mauro@gmail.com> wrote:
>
> So I wonder why operations such us intersection, union, difference,
> symmetric difference that are available for sets and are not available
> for dictionaries without going via key dictviews.

How would the set operations apply to the dictionary values?

[toc] | [prev] | [next] | [standalone]

#67056

On Tue, Feb 25, 2014 at 2:32 PM, mauro <mauro@gmail.com> wrote:
> So I wonder why operations such us intersection, union, difference,
> symmetric difference that are available for sets and are not available
> for dictionaries without going via key dictviews.

What's the correct result of evaluating this expression?

{'A': 1} | {'A': 2}

I can see (at least) two possible "correct" answers.

Skip

[toc] | [prev] | [next] | [standalone]

#67058

mauro wrote:

>  Dictionaries and sets share a few properties:

> - Dictionaries keys are unique as well as sets items
> - Dictionaries and sets are both unordered
> - Dictionaries and sets are both accessed by key

but sets have no values

> - Dictionaries and sets are both mutables

but frozensets also have the operations mentioned in the subject.

> So I wonder why operations such us intersection, union, difference,
> symmetric difference that are available for sets and are not available
> for dictionaries without going via key dictviews.

How would you define them? 

E. g.

{1, 2} & {2, 3} == {2}

but

{1:"a", 2:"b", 3:"c"} & {2:"b", 3:"e", 4:"f"} == ???

The most obvious result is probably the empty dict {2:"b"}, i. e.

a & b is defined as dict(a.items() & b.items())

Frankly, I don't do that a lot. So what's your use-case?

[toc] | [prev] | [next] | [standalone]

#67059

Peter Otten wrote:

> the empty dict {2:"b"}

Make that half-empty ;)

[toc] | [prev] | [next] | [standalone]

#67060

On 2014-02-25 14:40, Skip Montanaro wrote:
> What's the correct result of evaluating this expression?
> 
> {'A': 1} | {'A': 2}
> 
> I can see (at least) two possible "correct" answers.

I would propose at least four:

  {'A': 1}   # choose the LHS
  {'A': 2}   # choose the RHS
  {'A': (1,2)} # a resulting pair of both
  set(['A']) # you did set-ops, so you get a set

If dicts were to support set ops, the last one would be my preferred
result.

I just had to perform set operations on a pair of dicts earlier this
week, shrugged, and did things the manual/explicit way:

  a_dict = dict(...)
  b_dict = dict(...)
  a_set = set(a_dict)
  b_set = set(b_dict)
  added_keys = b_set - a_set
  removed_keys = a_set - b_set
  same_keys = a_set & b_set
  diff_keys = a_set ^ b_set
  all_keys = a_set | b_set

It would save some space if I didn't have to duplicate all the keys
into sets (on the order of 10-100k small strings), instead being able
to directly perform the set-ops on the dicts.  But otherwise, it was
pretty readable & straight-forward.

-tkc

[toc] | [prev] | [next] | [standalone]

#67069

Tim Chase <python.list@tim.thechases.com> wrote:

>   a_dict = dict(...)
>   b_dict = dict(...)
>   a_set = set(a_dict)
>   b_set = set(b_dict)
>   added_keys = b_set - a_set
>   removed_keys = a_set - b_set
>   same_keys = a_set & b_set
>   diff_keys = a_set ^ b_set
>   all_keys = a_set | b_set
> 
> It would save some space if I didn't have to duplicate all the keys
> into sets (on the order of 10-100k small strings), instead being able
> to directly perform the set-ops on the dicts.  But otherwise, it was
> pretty readable & straight-forward.
> 
It doesn't matter whether they were small strings or full-length novels, 
creating a set from a dict doesn't duplicate any strings.


-- 
Duncan Booth http://kupuguy.blogspot.com

[toc] | [prev] | [next] | [standalone]

#67071

On 2014-02-25 22:21, Duncan Booth wrote:
> > It would save some space if I didn't have to duplicate all the
> > keys into sets (on the order of 10-100k small strings), instead
> > being able to directly perform the set-ops on the dicts.  But
> > otherwise, it was pretty readable & straight-forward.
> >   
> It doesn't matter whether they were small strings or full-length
> novels, creating a set from a dict doesn't duplicate any strings.

pre-my-new-learning-about .viewkeys() it sounds like set(my_dict)
would have the overhead of storing an additional reference to a
string per set-entry (rather than duplicating every string).
With .viewkeys()/.keys(), it sounds like that overhead would go away.

-tkc

[toc] | [prev] | [next] | [standalone]

#67072

On 2014-02-25 22:21, Duncan Booth wrote:
> > It would save some space if I didn't have to duplicate all the
> > keys into sets (on the order of 10-100k small strings), instead
> > being able to directly perform the set-ops on the dicts.  But
> > otherwise, it was pretty readable & straight-forward.
> >     
> It doesn't matter whether they were small strings or full-length
> novels, creating a set from a dict doesn't duplicate any strings.  

pre-my-new-learning-about .viewkeys() it sounds like set(my_dict)
would have the overhead of storing an additional reference to a
string per set-entry (rather than duplicating every string).
With .viewkeys()/.keys(), it sounds like that overhead would go away.

-tkc

[toc] | [prev] | [next] | [standalone]

#67073

On 25 February 2014 22:36, Tim Chase <python.list@tim.thechases.com> wrote:
> On 2014-02-25 22:21, Duncan Booth wrote:
>> > It would save some space if I didn't have to duplicate all the
>> > keys into sets (on the order of 10-100k small strings), instead
>> > being able to directly perform the set-ops on the dicts.  But
>> > otherwise, it was pretty readable & straight-forward.
>> >
>> It doesn't matter whether they were small strings or full-length
>> novels, creating a set from a dict doesn't duplicate any strings.
>
> pre-my-new-learning-about .viewkeys() it sounds like set(my_dict)
> would have the overhead of storing an additional reference to a
> string per set-entry (rather than duplicating every string).
> With .viewkeys()/.keys(), it sounds like that overhead would go away.

You lose the redundant hash-table by using the keys view. The set hash
table takes 20-40 bytes per entry on this computer (according to
sys.getsizeof). On the same system a short string takes a similar
amount of memory. The .keys() view object apparently takes 24 bytes in
total so yes it's a reasonable memory saving if the dicts or of any
significant size.

However the .keys() objects are not necessarily as well optimised so
it may be faster to convert to sets for some operations. One example I
found some time ago is that for sets A & B will iterate over the
smaller set but for dicts A.keys() & B.keys() would always go over the
left-hand set (or right-hand - I don't remember). This makes a
considerable difference if one set is significantly larger than the
other.


Oscar

[toc] | [prev] | [next] | [standalone]

#67075

On Tue, 25 Feb 2014 15:03:51 -0600, Tim Chase wrote:

> On 2014-02-25 14:40, Skip Montanaro wrote:
>> What's the correct result of evaluating this expression?
>> 
>> {'A': 1} | {'A': 2}
>> 
>> I can see (at least) two possible "correct" answers.
> 
> I would propose at least four:
> 
>   {'A': 1}   # choose the LHS
>   {'A': 2}   # choose the RHS
>   {'A': (1,2)} # a resulting pair of both 

Should that value be a tuple, a list or a set?


>   set(['A']) # you did set-ops, so you get a set

Option 5: raise an exception if the values are different.

Option 6: "or" the values, so that the LHS value is used only if it is 
truthy, otherwise the RHS value is used. That is:

    {'A': leftdict['A'] or rightdict['A']}


I don't really understand the use-case behind Option 6, but there is a 
recent thread on python-ideas@python.org where somebody proposed that as 
the Obviously One True And Correct behaviour for dict intersection.



> If dicts were to support set ops, the last one would be my preferred
> result.

What, getting a set back?

No, I disagree. If you want a set, it's easy to do:

dicta.keys() | dictb.keys()

(In Python 2, use viewkeys instead.)


gives you a set of the intersection of the keys. The only point of having 
dicts support set-like operations directly is if you get a dict back.

All of these operations are quite simple to write, so personally I would 
recommend people just add their own helper function with the behaviour 
they prefer.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#67082

On 2014-02-25 23:10, Steven D'Aprano wrote:
> On Tue, 25 Feb 2014 15:03:51 -0600, Tim Chase wrote:
> 
> > On 2014-02-25 14:40, Skip Montanaro wrote:
> >> What's the correct result of evaluating this expression?
> >> 
> >> {'A': 1} | {'A': 2}
> >> 
> >> I can see (at least) two possible "correct" answers.
> > 
> > I would propose at least four:
> > 
> >   {'A': 1}   # choose the LHS
> >   {'A': 2}   # choose the RHS
> >   {'A': (1,2)} # a resulting pair of both 
> 
> Should that value be a tuple, a list or a set?

I'd say a tuple: it has order (thus not a set), and it's a fixed
record of (LHS, RHS), not mutable as a list would suggest.

> Option 5: raise an exception if the values are different.

Inconvenient in many use cases, but certainly another possibility

> Option 6: "or" the values, so that the LHS value is used only if it
> is truthy, otherwise the RHS value is used. That is:
> 
>     {'A': leftdict['A'] or rightdict['A']}
> 
> 
> I don't really understand the use-case behind Option 6

I can imagine a use case for it, but certainly not the *default*
behavior.  Yick.

> > If dicts were to support set ops, the last one would be my
> > preferred result.
> 
> What, getting a set back?
> 
> No, I disagree. If you want a set, it's easy to do:
> 
> dicta.keys() | dictb.keys()
> 
> (In Python 2, use viewkeys instead.)

Now that I'm aware of .viewkeys()/.keys() (herein "vk/k" for brevity)
thanks to Peter Otten's post, that does what I most commonly want for
set-ops-on-dicts.  I'd just consider this a promotion, since

  for k in my_dict:
    pass

is the same as

  for k in my_dict.keys(): # or .iterkeys() in 2.x
    pass

I'd find it intuitive to have set-ops behave similarly, defaulting
to vk/k.

> All of these operations are quite simple to write, so personally I
> would recommend people just add their own helper function with the
> behaviour they prefer.

And with vk/k, I now fall pretty firmly in agreement with you (except
for the aforementioned possibility of having a dict's currently-unused
set-ops use the results of vk/k as well).

-tkc

[toc] | [prev] | [next] | [standalone]

#67061

Peter Otten <__peter__@web.de> writes:

> mauro wrote:
>
> > - Dictionaries and sets are both accessed by key
>
> but sets have no values

Or rather, sets *only* have values. Dictionaries have keys, sets do not
have keys.

-- 
 \         “If nature has made any one thing less susceptible than all |
  `\    others of exclusive property, it is the action of the thinking |
_o__)                          power called an idea” —Thomas Jefferson |
Ben Finney

[toc] | [prev] | [next] | [standalone]

#67062

 mauro <mauro@gmail.com> Wrote in message:
>  Dictionaries and sets share a few properties:
> - Dictionaries keys are unique as well as sets items
> - Dictionaries and sets are both unordered
> - Dictionaries and sets are both accessed by key
> - Dictionaries and sets are both mutables
> 
> So I wonder why operations such us intersection, union, difference, 
> symmetric difference that are available for sets and are not available 
> for dictionaries without going via key dictviews. 
> 

I certainly wouldn't be able to guess what they should be defined
 to do, since there are several equally obnoxious possibilities.
 

For instance,  take union for example.  What should be the result
 when you union two dicts that have the same key but different
 values for that key?


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#67064

Tim Chase wrote:

> On 2014-02-25 14:40, Skip Montanaro wrote:
>> What's the correct result of evaluating this expression?
>> 
>> {'A': 1} | {'A': 2}
>> 
>> I can see (at least) two possible "correct" answers.
> 
> I would propose at least four:
> 
>   {'A': 1}   # choose the LHS
>   {'A': 2}   # choose the RHS
>   {'A': (1,2)} # a resulting pair of both
>   set(['A']) # you did set-ops, so you get a set
> 
> If dicts were to support set ops, 

They do in 2.7 and 3.x.

> the last one would be my preferred
> result.
> 
> I just had to perform set operations on a pair of dicts earlier this
> week, shrugged, and did things the manual/explicit way:
> 
>   a_dict = dict(...)
>   b_dict = dict(...)
>   a_set = set(a_dict)
>   b_set = set(b_dict)
>   added_keys = b_set - a_set
>   removed_keys = a_set - b_set
>   same_keys = a_set & b_set
>   diff_keys = a_set ^ b_set
>   all_keys = a_set | b_set

>>> a = dict.fromkeys("ab")
>>> b = dict.fromkeys("bc")
>>> a.viewkeys() - b.viewkeys()
set(['a'])
>>> a.viewkeys() & b.viewkeys()
set(['b'])
>>> a.viewkeys() ^ b.viewkeys()
set(['a', 'c'])
>>> a.viewkeys() | b.viewkeys()
set(['a', 'c', 'b'])

For 3.x replace viewkeys() with keys().

> It would save some space if I didn't have to duplicate all the keys
> into sets (on the order of 10-100k small strings), instead being able
> to directly perform the set-ops on the dicts.  But otherwise, it was
> pretty readable & straight-forward.
> 
> -tkc

[toc] | [prev] | [next] | [standalone]

#67065

> 
> {'A': 1} | {'A': 2}
>
> I would propose at least four:
> 
>   {'A': 1}   # choose the LHS 
>   {'A': 2}   # choose the RHS 
>   {'A': (1,2)} # a resulting pair of both 
>   set(['A']) # you did set-ops, so you get a set

The implementation should define if LHS or RHS and user should change the 
order of operands depending on what he wants. 

Your example (as well as a many questions in stackoverflow.com) shows 
that there is some need for these operations, that implemented in C in 
python library will be by far more CPU and memory efficient than 
implemented as you did. 

[toc] | [prev] | [next] | [standalone]

#67066

Il Tue, 25 Feb 2014 22:02:01 +0000, mauro ha scritto:


>> {'A': 1} | {'A': 2}
>>
>> I would propose at least four:
>> 
>>   {'A': 1}   # choose the LHS {'A': 2}   # choose the RHS {'A': (1,2)}
>>   # a resulting pair of both set(['A']) # you did set-ops, so you get a
>>   set
> 
> The implementation should define if LHS or RHS and user should change
> the order of operands depending on what he wants.
> 
> Your example (as well as a many questions in stackoverflow.com) shows
> that there is some need for these operations, that implemented in C in
> python library will be by far more CPU and memory efficient than
> implemented as you did.

posting error, this entry was supposed to be a reply to Tim Chase's 
comment.

[toc] | [prev] | [next] | [standalone]

#67067

On 2014-02-25 22:54, Peter Otten wrote:
> Tim Chase wrote:
> > If dicts were to support set ops, 
> 
> They do in 2.7 and 3.x.
> 
> >>> a.viewkeys() - b.viewkeys()
> set(['a'])
> >>> a.viewkeys() & b.viewkeys()
> set(['b'])
> >>> a.viewkeys() ^ b.viewkeys()
> set(['a', 'c'])
> >>> a.viewkeys() | b.viewkeys()
> set(['a', 'c', 'b'])
> 
> For 3.x replace viewkeys() with keys().

I missed this getting added in the 2.7 release.  Thanks for the
introduction to .viewkeys()/.keys() as they could prove quite handy.

-tkc

[toc] | [prev] | [next] | [standalone]

#67068

> 
> {1, 2} & {2, 3} == {2}
> 
In my mind the intersection is evaluated on keys, so the resulting dict 
should be the empty one
> but
> 
> {1:"a", 2:"b", 3:"c"} & {2:"b", 3:"e", 4:"f"} == ???
my output will be
{2:"b", 3:"e"} 
or
{2:"b", 3:"c"} 

depending on the implementation choice.  
> 
> The most obvious result is probably the empty dict {2:"b"}, i. e.
> 
> a & b is defined as dict(a.items() & b.items())
> 
> Frankly, I don't do that a lot. So what's your use-case?
I do not have an use case, but I've seen that many people ask for these 
operations for example in stackoverflow.com

[toc] | [prev] | [next] | [standalone]

#67070

On 25/02/2014 22:11, mauro wrote:
>
>>
>> {1, 2} & {2, 3} == {2}
>>
> In my mind the intersection is evaluated on keys, so the resulting dict
> should be the empty one
>> but
>>
>> {1:"a", 2:"b", 3:"c"} & {2:"b", 3:"e", 4:"f"} == ???
> my output will be
> {2:"b", 3:"e"}
> or
> {2:"b", 3:"c"}
>
> depending on the implementation choice.
>>
>> The most obvious result is probably the empty dict {2:"b"}, i. e.
>>
>> a & b is defined as dict(a.items() & b.items())
>>
>> Frankly, I don't do that a lot. So what's your use-case?
> I do not have an use case, but I've seen that many people ask for these
> operations for example in stackoverflow.com
>

Please ask one of the many people on stackoverflow to raise an 
enhancement request here bugs.python.org complete with a patch that 
changes code, docs and tests and then everybody will be happy, won't they.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web