find minimum associated values

Alan Isaac aisaac at american.edu
Fri Jan 25 17:56:44 CET 2008


I have a small set of objects associated with a larger
set of values, and I want to map each object to its
minimum associated value.  The solutions below work,
but I would like to see prettier solutions...

Thank you,
Alan Isaac

===================================================================

import time, random
from itertools import groupby
from collections import defaultdict

class Pass:
    pass

# arbitrary setup
keys = [Pass() for i in range(10)]*3
vals = [random.random() for i in range(30)]
kv = zip(keys,vals)
random.shuffle(kv)

#OBJECTIVE:
# find minimum val associated with each "key" in kv

print "method 1: brute force"
t=time.clock()
d = dict()
for k,v in kv:
    if k in d:
        if d[k] > v:
            d[k] = v
    else:
        d[k] = v
print time.clock()-t
print d
print

print "method 2: groupby"
t=time.clock()
d = dict()
kv_sorted = sorted(kv, key=lambda x: id(x[0]))
for k, g in groupby( kv_sorted, key=lambda x: x[0] ):
    d[k] = min(gi[1] for gi in g)
print time.clock()-t
print d
print

print "method 3: defaultdict"
t=time.clock()
d = defaultdict(list)
for k,v in kv:
    d[k].append(v)
for k in d:
    d[k] = min(d[k])
print time.clock()-t
print d





More information about the Python-list mailing list