sorting a dictionary

Alex Martelli aleax at aleax.it
Tue Feb 4 10:36:16 CET 2003


Laura Creighton wrote:
   ...
> This will work, but there may be faster ways.
> 
>>>> def get_highest(d):
> ...     l = []
> ...     for k in d.keys():
> ...             l.append([d[k], k])
> ...     l.sort()
> ...     return l[-1][1]
> ...

There's an O(N) solution -- sorting is O(N log N),
therefore the O(N) solution WILL be faster for
large-enough dictionaries.  For example:

def get_highest_in_linear_time(d):
    iterator = d.iteritems()
    maxkey, maxval = iterator.next()
    for curkey, curval in iterator:
        if curval>maxval: maxkey, maxval = curkey, curval
    return maxkey


Alex





More information about the Python-list mailing list