Why aren't OrderedDicts comparable with < etc?
Mark Summerfield
I'm just wondering why <, <=, >=, and > are not supported by
collections.OrderedDict:
>>> d1 = collections.OrderedDict((("a",1),("z",2),("k",3)))
>>> d2 = d1.copy()
>>> d2["z"] = 4
>>> d1 == d2
False
>>> d1 < d2
Traceback (most recent call last):
File "<pyshell#6>", line 1, in <module>
d1 < d2
TypeError: unorderable types: OrderedDict() < OrderedDict()
It just seems to me that since the items in ordered dictionaries are
ordered, it would make sense to do an item by item comparison from
first to last item in exactly the same way that Python compares lists
or tuples?
Jack Diederich
>>> import this
In the face of ambiguity, refuse the temptation to guess.
It isn't an OrderedDict thing, it is a comparison thing. Two regular
dicts also raise an error if you try to LT them. What does it mean
for a dict to be greater than or less than its peer? Nothing, so we
refuse to guess.
-Jack
Mark
You are right that it doesn't make sense to compare two dicts.
But OrderedDicts can be viewed logically as lists of (key,value)
tuples so they are much more like lists or tuples when it comes to
comparisons.
For example:
>>> l = [("a", 1), ("z", 2), ("k", 3)]
>>> l1 = l[:]
>>> l1[1] = ("z", 5)
>>> l < l1
True
But if you do:
>>> d = collections.OrderedDict(l)
>>> d1 = collections.OrderedDict(l1)
You can't use <, <=, =>, or >, even though ordered dictionaries
preserve the order and their items are just as comparable as those in
a list or tuple of tuples.
Chris Rebert
Steven D'Aprano
Surely it would be the same use case as for comparing two lists? There
doesn't need to be a special "OrderedDict use case" beyond "an
OrderedDict is just like a list of (key,value) tuples, but searches are
faster".
Or maybe not. If OrderedDicts are sequences as well as mappings, then we
should be able to sort them. And that seems a bit much even for me.
--
Steven
Piet van Oostrum
>M> You are right that it doesn't make sense to compare two dicts.
>M> But OrderedDicts can be viewed logically as lists of (key,value)
>M> tuples so they are much more like lists or tuples when it comes to
>M> comparisons.
>M> For example:
>>>>> l = [("a", 1), ("z", 2), ("k", 3)]
>>>>> l1 = l[:]
>>>>> l1[1] = ("z", 5)
>>>>> l < l1
>M> True
>M> But if you do:
>>>>> d = collections.OrderedDict(l)
>>>>> d1 = collections.OrderedDict(l1)
>M> You can't use <, <=, =>, or >, even though ordered dictionaries
>M> preserve the order and their items are just as comparable as those in
>M> a list or tuple of tuples.
But why should the order be as if the OrderedDict was a list of tuples.
A dict can be considered as a mapping and then you might want to treat
either the key or the value as contravariant (the key I guess). So there
is ambiguity. Why would the view as a list of tuples for the ordering be
the `natural' view?
Maybe you may expect some kind of monotonicity such that d1<d2 implies
d1[x]<d2[x], but that doesn't work for d1 = {1:10, 2:20} and d2 = {1:15,
2:5}. So maybe there is only a partial ordering?
--
Piet van Oostrum <pi...@cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: pi...@vanoostrum.org
Mark
OK, that seems to me to be a convincing argument against supporting
ordering.
Mark
<ste...@REMOVE.THIS.cybersource.com.au> wrote:
> On Thu, 16 Jul 2009 00:30:26 -0700, Chris Rebert wrote:
One thing that I've just noticed is that you can use <, <=, >=, and >
with sets:
>>> s1 = {1,2,3}
>>> s2 = {1,2,4}
>>> s1 == s2
False
>>> s1 < s2
False
>>> s1 <= s2
False
>>> s2 < s1
False
>>> s2 <= s1
False
>>> s1 != s2
True
It seems a bit inconsistent that with sets you always get False when
using an ordering operator but with an ordered dict you get an
exception?
Mark
Ooops---disregard the above---I forgot that these do subset and
superset comparisions!
Terry Reedy
To put the above in a slightly different way. OrderedDicts are a
recently added niche class that Raymond added to what is mostly his
collections module because there are enough few use cases. There was
pydev discussion which included the idea, I believe, that they should
fundamentally be dicts, not lists. Regardless, the justifying use cases
did not include a need to compare OrderedDicts. The small fraction of
the few use cases for OrderedDicts that do require comparision can be
met by extracting the needed sequences and comparing *them* in the
appropriate manner. The 'appropriate manner' is not likely to always be
the same. This point may have come up in the discussion, but I would let
you check for sure if curious.
'Consistency' is a Python design principle, but it is balanced with
others, so that it is not sufficient reason to add nearly useless
features. There is a cost to every addition.
Terry Jan Reedy
Nobody
>> > Or maybe not. If OrderedDicts are sequences as well as mappings, then we
>> > should be able to sort them. And that seems a bit much even for me.
>> One thing that I've just noticed is that you can use <, <=, >=, and >
>> with sets:
>> It seems a bit inconsistent that with sets you always get False when
>> using an ordering operator but with an ordered dict you get an
>> exception?
>
> Ooops---disregard the above---I forgot that these do subset and
> superset comparisions!
Which is an argument for dictionaries (ordered or not) doing likewise,
except that the comparison would be subfunction rather than subset,
i.e. d1<d2 = all(k in d2 and d2[k] == d1[k] for k in d1).
Sion Arrowsmith
>It isn't an OrderedDict thing, it is a comparison thing. Two regular
>dicts also raise an error if you try to LT them.
Since when?
Python 2.5.2 (r252:60911, Jan 4 2009, 17:40:26)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> d1 = dict((str(i), i) for i in range (10))
>>> d2 = dict((str(i), i) for i in range (20))
>>> d1 < d2
True
>>>
(Don't have a 2.6 or 3 to hand.)
Mind you, it makes even less sense for a regular dict than an
OrderedDict. And it's not like d1.items() < d2.items() is a
huge burden, if that's what you want dictionary comparison to
mean.
--
\S
under construction
Terry Reedy
> Jack Diederich <jack...@gmail.com> wrote:
>> It isn't an OrderedDict thing, it is a comparison thing. Two regular
>> dicts also raise an error if you try to LT them.
>
> Since when?
>
> Python 2.5.2 (r252:60911, Jan 4 2009, 17:40:26)
> [GCC 4.3.2] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
>>>> d1 = dict((str(i), i) for i in range (10))
>>>> d2 = dict((str(i), i) for i in range (20))
>>>> d1 < d2
> True
Try reversing the definitions of d1 and d2. The dicts are probably being
compared by id (address), which is the 2.x CPython default.
> (Don't have a 2.6 or 3 to hand.)
2.6 same. 3.1
>>> d1,d2 = {},{}
>>> d1 < d2
Traceback (most recent call last):
File "<pyshell#16>", line 1, in <module>
d1 < d2
TypeError: unorderable types: dict() < dict()
Sion Arrowsmith
>Sion Arrowsmith wrote:
>> Jack Diederich <jack...@gmail.com> wrote:
>>> It isn't an OrderedDict thing, it is a comparison thing. Two regular
>>> dicts also raise an error if you try to LT them.
>>>>> d1 = dict((str(i), i) for i in range (10))
>>>>> d2 = dict((str(i), i) for i in range (20))
>>>>> d1 < d2
>> True
>Try reversing the definitions of d1 and d2. The dicts are probably being
>compared by id (address), which is the 2.x CPython default.
Like this?
>>> d1 = dict((str(i), i) for i in range (20))
>>> d2 = dict((str(i), i) for i in range (10))
>>> d1 < d2
False
>>> id(d1) < id(d2)
True
I didn't know that comparison for anything other than equality
defaulted to using id. That really is rather broken, and I'm
glad 3.0 fixed it.
--
\S
under construction
Steven D'Aprano
I don't think comparisons other than equality use id. That would be
rather insane. If anyone can demonstrate such comparisons in a built-in
or standard library class, I'd like to see it.
For the record, dicts have been comparable with < and > since at least
Python 1.5:
$ python1.5
Python 1.5.2 (#1, Apr 1 2009, 22:55:54) [GCC 4.1.2 20070925 (Red Hat
4.1.2-27)] on linux2
Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>>
>>> {1: 'a', 2: 'b'} < {2: 'b', 3: 'a'}
1
Reading the docs:
http://docs.python.org/library/stdtypes.html#comparisons
http://docs.python.org/library/stdtypes.html#mapping-types-dict
I can only suggest that dicts compare in an arbitrary but consistent
fashion. What that is based on, I don't know, but based on some very
limited testing, I'd guess it is like this:
If the two dicts have unequal length, the longer dict compares greater
than the shorter dict.
If the two dicts are equal in length, (key, item) pairs are compared,
probably in lexicographic order, because the order of insertion of keys
doesn't appear to matter.
--
Steven
Jack Diederich
I should have specified 3.x but since we were talking about
OrderedDicts (only in 3.1) I didn't say it explicitly. Earlier
versions of python were very permissive with comparisons -- it was
rare that any cmp() raised an error and the ultimate fallback was on
the object's id. This is one of the non-backwards compatible changes
in 3k. Now comparing two of the same thing that don't have an obvious
ordering is an error. Is a dict "greater than" if it has a larger
size? if its max key is larger? what does "max key" mean when the
keys aren't even comparable?. Comparing things that aren't extremely
similar is an error now also.
-Jack
Albert van der Horst
Jack Diederich <jack...@gmail.com> wrote:
>On Mon, Jul 20, 2009 at 10:00 AM, Steven
>D'Aprano<st...@remove-this-cybersource.com.au> wrote:
>> On Mon, 20 Jul 2009 09:34:24 +0000, Sion Arrowsmith wrote:
>>
>>>>>> It isn't an OrderedDict thing, it is a comparison thing. =A0Two regul=
>ar
>>>>>> dicts also raise an error if you try to LT them.
>>>>> Python 2.5.2
>)
>>>>>>>> for i in range (20)) d1 < d2
>>>>> True
>>>>Try reversing the definitions of d1 and d2. The dicts are probably being
>>>>compared by id (address), which is the 2.x CPython default.
>>>
>>> Like this?
>>>
>>>>>> d2 =3D dict((str(i), i) for i in range (10))
>>>>>> d1 < d2
>>> False
>>>>>> id(d1) < id(d2)
>>> True
>>>
>>> I didn't know that comparison for anything other than equality defaulted
>>> to using id. That really is rather broken, and I'm glad 3.0 fixed it.
>>
>>
>> I don't think comparisons other than equality use id. That would be
>> rather insane. If anyone can demonstrate such comparisons in a built-in
>> or standard library class, I'd like to see it.
>>
>>
>> For the record, dicts have been comparable with < and > since at least
>> Python 1.5:
>>
>> $ python1.5
>t
>> 4.1.2-27)] on linux2
>> Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>>>>
>>>>> {1: 'a', 2: 'b'} < {2: 'b', 3: 'a'}
>> 1
>>
>>
>> Reading the docs:
>>
>> http://docs.python.org/library/stdtypes.html#comparisons
>> http://docs.python.org/library/stdtypes.html#mapping-types-dict
>>
>> I can only suggest that dicts compare in an arbitrary but consistent
>> fashion.
>
>I should have specified 3.x but since we were talking about
>OrderedDicts (only in 3.1) I didn't say it explicitly. Earlier
>versions of python were very permissive with comparisons -- it was
>rare that any cmp() raised an error and the ultimate fallback was on
>the object's id. This is one of the non-backwards compatible changes
>in 3k. Now comparing two of the same thing that don't have an obvious
>ordering is an error. Is a dict "greater than" if it has a larger
>size? if its max key is larger? what does "max key" mean when the
>keys aren't even comparable?. Comparing things that aren't extremely
>similar is an error now also.
With regard to < and > you are right.
But I think there is a sensible == w.r.t. dict's.
It is to mean that for each key dict1(key) == dict2(key)
(implying that their key set must be the same)
[I could have used that for one of the euler problems.
You have a 4 by 4 field containing a red or blue square.
That is naturally a mapping of (1,1) ..(4,4) tuples to one
of the objects `blue' `red'. After moving a square you
want to know whether this is a map you already have encountered.]
>
>-Jack
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Piet van Oostrum
>AvdH> With regard to < and > you are right.
>AvdH> But I think there is a sensible == w.r.t. dict's.
>AvdH> It is to mean that for each key dict1(key) == dict2(key)
>AvdH> (implying that their key set must be the same)
>AvdH> [I could have used that for one of the euler problems.
>AvdH> You have a 4 by 4 field containing a red or blue square.
>AvdH> That is naturally a mapping of (1,1) ..(4,4) tuples to one
>AvdH> of the objects `blue' `red'. After moving a square you
>AvdH> want to know whether this is a map you already have encountered.]
So what's the problem?
piet$ python3
Python 3.1 (r31:73578, Jun 27 2009, 21:49:46)
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import OrderedDict
>>> a = OrderedDict()
>>> b = OrderedDict()
>>> a[1]=2
>>> b[1]=2
>>> a[3]=4
>>> b[3]=4
>>> a==b
True
>>> b[5]=6
>>> a==b
False
>>> d1 = dict((str(i), i) for i in range (10))
>>> d2 = dict((str(i), i) for i in range (10))
>>> d1 == d2
True