find minimum associated values

[Alan Isaac]

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

[Steven Bethard]

Alan Isaac wrote:
> 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...
>

[snip]

>
> # 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
>

[snip]

>
> 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

This is definitely the approach I'd use. Seems "pretty" enough to me. ;-)

STeVe

[Alan Isaac]

Steven Bethard wrote:
> [3rd approach] Seems "pretty" enough to me. ;-)

I find it most attractive of the lot.
But its costs would rise if the number
of values per object were large.

Anyway, I basically agree.

Thanks,
Alan

[Paul Rubin]

Alan Isaac <ais...@american.edu> writes:
> print "method 2: groupby"
> t=time.clock()
> d = dict()
> kv_sorted = sorted(kv, key=lambda x: id(x[0]))

How about something like:

kv_sorted = sorted(kv, key=lambda x: (id(x[0]), x[1]))

Now do your groupby and the first element of each group is the minimum
for that group.

[bearoph...@lycos.com]

I find the first and third solutions simpler to read, and the first
solution requires less memory, it probably works quite well with
Psyco, and it's easy to translate to other languages (that is
important for programs you want to use for a lot of time or in
different situations), so I'd use the first solution.

Bye,
bearophile

[John Machin]

The first solution, once one changes "d = dict()" to "d = {}", is
quite free of any impediments to ease of reading, uses the minimum
necessary memory to build the required dict [and it's quite obvious by
inspection that this is so], and is the easiest to "translate" to
earlier versions of Python.

[Alan Isaac]

Paul Rubin wrote:
> How about something like:
>
> kv_sorted = sorted(kv, key=lambda x: (id(x[0]), x[1]))

You mean like this?

#sort by id and then value

kv_sorted = sorted(kv, key=lambda x: (id(x[0]),x[1]))

#groupby: first element in each group is object and its min value
d =dict( g.next() for k,g in groupby( kv_sorted, key=lambda x: x[0] ) )

Yes, that appears to be fastest and is
pretty easy to read.

Thanks,
Alan

[Alan Isaac]

Alan Isaac wrote:

> #sort by id and then value
> kv_sorted = sorted(kv, key=lambda x: (id(x[0]),x[1]))
> #groupby: first element in each group is object and its min value
> d =dict( g.next() for k,g in groupby( kv_sorted, key=lambda x: x[0] ) )
>
> Yes, that appears to be fastest and is
> pretty easy to read.

On average.
For the specified problem.
;-)

[Alan Isaac]

bearoph...@lycos.com wrote:
> I'd use the first solution.

It can be speeded up a bit with
a try/except:

for k,v in kv:
try:

if d[k] > v:
d[k] = v

except KeyError:
d[k] = v

Cheers,
Alan Isaac