sorting a dictionary

[Alex Martelli]

Alex Martelli wrote:
   ...
> Heh -- sorry, I see the OP wanted the *key of the highest
> value*, NOT the highest key, which is what dsavitsk's
> solution, and max(d), would give.  For the OP's problem,
> you can't get any faster than O(N logN).

Silly me, of COURSE you can -- see my other post on this
thread.  Here's an alternate implementation as penance;

def get_highest_in_linear_time_without_explicit_iterators(d):
    for k in d:
        maxkey, maxval = k, d[k]
        break
    else:
        raise ValueError, "empty dictionary has no highest key"
    for k in d:
        v = d[k]
        if v>maxval: maxkey, maxval = k, v
    return maxkey

Point is, of course, that given any sequence (and a dict
is easy to treat as such, either with explicit iterators
or for statements), finding its maximum is O(N), while
sorting it is O(N logN).  If all you need is the maximum,
sorting first is sensible only for SMALL sequences.

While one wouldn't notmally worry about performance, O()
issues may be different, IMHO -- there's nearly no upper
bound to the performance one may lose by choosing the
wrong-big-O kind of algorithm somewhere; and they're
tricky in that profiling may NOT show the bottleneck if
you profile with too-small data (it's normal to profile
with small-ish inputs, since profiling slows a program
down SO much -- although hotshot helps with that!) --
but when the program is run on data sets that are much
larger, the wrong-big-O algorithm may easily become the
performance bottleneck.  Which is why I'm so keen about
this...


Alex