Python: using custom comparator for sort in OrderedDict

Question

I have a dictionary which has the following content :

dict = {'P1' :361 , 'P2' : 361, 'P3' : 391, 'P6' : 361, 'P4':361, 'P5' :361}

which needs to be sorted on basis of value in descending order. For any given item if the value is same to the item it is compared, it is to be sorted on the ascending order of key. Hence, the resultant value of the dict should be this.

{'P3' : 391 , 'P1' : 361, 'P2': 361, 'P4': 361, 'P5': 361,'P6' : 361}

I have achieved the first part using this :

sorted_dict = OrderedDict(sorted(dict.items(), key=lambda t: t[1],reverse=True))

However, I am uncertain how to go beyond that. I am assuming the comparator function typically can be something like this

def comparator(item1,item2):
    if item1.value() == item2.value():
        if item1.key()<item2.key():
            return -1
        if item1.key()>item2.key():
            return 1
        if item1.key() == item2.key():
            return 0
    if item1.value() < item2.value():
        return -1
    if item1.value() > item2.value():
        return 1

I am unsure of how to implement this. Pardon my naiveté, I am a beginner in Python and have little knowledge of the programming constructs in the language.

What do you consider descending order? Is `"P100"` > `"P2"` or `<`? — Padraic Cunningham, Jun 25 '16 at 21:54
I asked for `"P100" vs "P2"` as P2 would be considered greater using a lexicographical sort, if you don't want that then there is a lot more involved — Padraic Cunningham, Jun 25 '16 at 22:11
No worries, people often get caught with that, that is why I asked. — Padraic Cunningham, Jun 25 '16 at 22:34

score 3 · Answer 1 · edited May 23 '17 at 10:29

You can just use a slightly different lambda expression as the key for sorting.

sorted_dict = OrderedDict(sorted(dict.items(), key=lambda x: (-x[1], x[0])))

Outputs:

OrderedDict([('P3', 391), ('P1', 361), ('P2', 361), ('P4', 361), ('P5', 361), ('P6', 361)])

Supplying a key is supplying a function to transform each item before comparison. So here, the anonymous lambda function supplies a sequence transformation used for sorting - sequences are sorted by comparing each element in turn. So we sort by the negative of the number (to invert the natural ascending -> descending), and should that compare equal we move on to the string for sorting, which sorts normally the way you intend it to (at least for the sample provided). You might need to make use of string natural sorting for larger numbers in your string, if lexicographic sort won't give you intended results.

Padraic Cunningham · Accepted Answer · 2016-06-25T22:37:48.350

If the keys do not conatin all single digits and you don't want a lexicographical sort then you will need to add more logic:

d = {'P1000': 361, 'P200': 361, 'P3': 391, 'P6': 361, 'P4': 361, 'P5': 361,"P100":361}
import re

patt = re.compile("[^\d]")


def cmp(x):
     letts = patt.search(x).group()
     return patt.search(x).group(), int(x[len(letts):])

You can see the different behaviour using the example below:

In [1]: d = {'P1000': 361, 'P200': 361, 'P3': 391, 'P6': 361, 'P4': 361, 'P5': 361,"P100":361}

In [2]: import re

In [3]: patt =  re.compile("[^\d]")

In [4]: def cmp(x):
   ...:         return patt.search(x).group(), int(patt1.search(x).group())
   ...: print(sorted(d.items(), key=lambda x: (-x[1], cmp(x[0]))))
   ...: print(sorted(d.items(), key=lambda x: (-x[1], x[0])))
   ...: 
[('P3', 391), ('P4', 361), ('P5', 361), ('P6', 361), ('P100', 361), ('P200', 361), ('P1000', 361)]
[('P3', 391), ('P100', 361), ('P1000', 361), ('P200', 361), ('P4', 361), ('P5', 361), ('P6', 361)]

An itertools alternative to a regex presuming the chars are always alphas:

from itertools import  takewhile

def cmp(x):
    take = "".join(takewhile(str.isalpha, x))
    return take, int(x[len(take):])
print(sorted(d.items(), key=lambda x: (-x[1], (cmp(x[0])))))

If it is always 1 letter then n digits, it can be simplified to:

sorted(d.items(), key=lambda x: (-x[1], (x[0][0], int(x[0][1:])))

Python: using custom comparator for sort in OrderedDict

2 Answers2