Tukukkk

Given a dictionary and a limit for the number of keys in a new dictionary, I would like the new dictionary to contain the keys with the highest values.

The given dict is:

dict = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1 }

I want to get a new dictionary that has the keys with the highest values of length limit.

For instance for limit=1 the new dict is

{'apple':5} 

if the limit=2

{'apple':5, 'pears':4}

I tried this:

return dict(sorted(dictation.items(),key=lambda x: -x[1])[:limit])

but when I try limit=3, I get

{'apple':5, 'pears':4, 'orange':3}

But it shouldn't include orange:3 because orange and kiwi have same priority if we include kiwi and orange it will exceed the limit so it shouldn't include both. I should return

{'apple':5, 'pears':4}

The way to go would be to use a collections.Counter and most_common(n). Then you can take one more as needed and keep popping until the last value changes:

from collections import Counter



dct = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}

n = 3



items = Counter(dictation).most_common(n+1)

last_val = items[-1][1]

if len(items) > n:

    while items[-1][1] == last_val:

        items.pop()



new = dict(items)

# {'apple': 5, 'pears': 4}

This is computationally not very good, but it works. It creates a Counter object to get the sorted output for your data and a inverted defaultdict that holds list that match to a score - it creates the result using both and some math:

from collections import defaultdict, Counter



def gimme(d,n):

    c = Counter(d)

    grpd = defaultdict(list)

    for key,value in c.items():

        grpd[value].append(key)





    result = {}

    for key,value in c.most_common():

        if len(grpd[value])+len(result) <= n:

            result.update( {k:value for k in grpd[value] } )

        else:

            break

    return result

Test:

data = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1 }



for k in range(10):

    print(k, gimme(data,k))

Output:

0 {}

1 {'apple': 5}

2 {'apple': 5, 'pears': 4}

3 {'apple': 5, 'pears': 4}

4 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3}

5 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3}

6 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}

7 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}

8 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}

9 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}

As you note, filtering by the top n doesn't exclude by default all equal values which exceed the stated cap. This is by design.

The trick is to consider the (n+1) th highest value and ensure the values in your dictionary are all higher than this number:

from heapq import nlargest



dictation = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}



n = 3

largest_items = nlargest(n+1, dictation.items(), key=lambda x: x[1])

n_plus_one_value = largest_items[-1][1]



res = {k: v for k, v in largest_items if v > n_plus_one_value}



print(res)



{'apple': 5, 'pears': 4}

We assume here len(largest_items) < n, otherwise you can just take the input dictionary as the result.

The dictionary comprehension seems expensive. For larger inputs, you can use bisect, something like:

from heapq import nlargest

from operator import itemgetter

from bisect import bisect



dictation = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}



n = 3

largest_items = nlargest(n+1, dictation.items(), key=lambda x: x[1])

n_plus_one_value = largest_items[-1][1]



index = bisect(list(map(itemgetter(1), largest_items))[::-1], n_plus_one_value)



res = dict(largest_items[:len(largest_items) - index])



print(res)



{'apple': 5, 'pears': 4}