dict order

[Robert Bossy]

Hi,

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

Note that I'm not trying to rely on this order. I'm building a
domain-specific language where there's a data structure similar to
python dict and I need an source of inspiration for implementing
comparisons.

Thanks
RB

 

[cokofreedom]

Hi,

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

Note that I'm not trying to rely on this order. I'm building a
domain-specific language where there's a data structure similar to
python dict and I need an source of inspiration for implementing
comparisons.

Thanks
RB

I'm a little confused as to what you want. Are you asking whether two
dictionary objects have the same keys AND values, or just the Keys?

As dictionaries are unordered the best technique is to go through one
dictionary and take out a key, then see if that key exists in the
other dictionary, and if so do they share the same values.

# untested 2.5
for keys in dict_one.items():
if keys in dict_two:
if dict_one[keys] != dict_two[keys]:
# values are different
else:
# key is not present

This probably isn't the most efficient way, but can quickly find
differences...

 

[cokofreedom]

Hi,

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

Note that I'm not trying to rely on this order. I'm building a
domain-specific language where there's a data structure similar to
python dict and I need an source of inspiration for implementing
comparisons.

Thanks
RB

I'm a little confused as to what you want. Are you asking whether two
dictionary objects have the same keys AND values, or just the Keys?

As dictionaries are unordered the best technique is to go through one
dictionary and take out a key, then see if that key exists in the
other dictionary, and if so do they share the same values.

# untested 2.5
for keys in dict_one.items():
if keys in dict_two:
if dict_one[keys] != dict_two[keys]:
# values are different
else:
# key is not present

This probably isn't the most efficient way, but can quickly find
differences...

Whoops

for keys, values in dict_one.items():
if keys in dict_two:
if values == dict_two[keys]:

should also work...

 

[Lie]

Hi,

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

Note that I'm not trying to rely on this order. I'm building a
domain-specific language where there's a data structure similar to
python dict and I need an source of inspiration for implementing
comparisons.

Thanks
RB

Why not consider them as equal, it's simple and is basically telling
people not to rely on them because one day A might be lower than B and
the other day, A and B that hasn't been modified at all might switch
sides without warning.

Or you could just use any arbitrary way of comparison (Python Zen: In
the face of ambiguity, refuse the temptation to guess.).

 

[Lie]

I'm a little confused as to what you want. Are you asking whether two
dictionary objects have the same keys AND values, or just the Keys?

As dictionaries are unordered the best technique is to go through one
dictionary and take out a key, then see if that key exists in the
other dictionary, and if so do they share the same values.

# untested 2.5
for keys in dict_one.items():
  if keys in dict_two:
    if dict_one[keys] != dict_two[keys]:
      # values are different
  else:
    # key is not present

This probably isn't the most efficient way, but can quickly find
differences...

Whoops

for keys, values in dict_one.items():
  if keys in dict_two:
    if values == dict_two[keys]:

should also work...

Whoops, I think I misunderstood the question. If what you're asking
whether two dictionary is equal (equality comparison, rather than
sorting comparison). You could do something like this:

a = [...]
b = [...]

s = set()

for bk, bv in b.iteritems():
s.add((bk, bv))

for ak, av in a.iteritems():
if not((ak, av) in s):
print 'Difference Found!'

 

[Peter Otten]

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

If I interpret the comments in

http://svn.python.org/view/python/trunk/Objects/dictobject.c?rev=64048&view=markup

correctly it's roughly

def characterize(d, e):
return min(((k, v) for k, v in d.iteritems() if k not in e or e[k] != v),
key=lambda (k, v): k)

def dict_compare(d, e):
result = cmp(len(d), len(e))
if result:
return result
try:
ka, va = characterize(d, e)
except ValueError:
return 0
kb, vb = characterize(e, d)
return cmp(ka, kb) or cmp(va, vb)

Peter

 

[Robert Bossy]

Testing for equality and finding differences are trivial tasks indeed.
It is the sort order I'm interested in. The meaning of the order is not
really an issue, I'm rather looking for a consistent comparison function
(in the __cmp__ sense) such as:
if d1 > d2 and d2 > d3,
then d1 > d3

I'm not sure the hashing method suggested by Albert guarantees that.

Cheers

 

[Robert Bossy]

Robert Bossy wrote:

I wish to know how two dict objects are compared. By browsing the
archives I gathered that the number of items are first compared, but if
the two dict objects have the same number of items, then the comparison
algorithm was not mentioned.

If I interpret the comments in

http://svn.python.org/view/python/trunk/Objects/dictobject.c?rev=64048&view=markup

correctly it's roughly

def characterize(d, e):
return min(((k, v) for k, v in d.iteritems() if k not in e or e[k] != v),
key=lambda (k, v): k)

def dict_compare(d, e):
result = cmp(len(d), len(e))
if result:
return result
try:
ka, va = characterize(d, e)
except ValueError:
return 0
kb, vb = characterize(e, d)
return cmp(ka, kb) or cmp(va, vb)

Thanks, Peter! That was exactly what I was looking for. Quite clever, I
might add.

RB

 

[cokofreedom]

# untested 2.5
for keys in dict_one.items():
if keys in dict_two:
if dict_one[keys] != dict_two[keys]:
# values are different
else:
# key is not present

That fails if there is an item in dict_two that's not in dict_one.

True

 

[Aahz]

Whoops

for keys, values in dict_one.items():
if keys in dict_two:
if values == dict_two[keys]:

Except that "keys" implies a plural (meaning more than one thing); in a
for loop, each iteration will have only one key.