gozzilli - 1 year ago 102

Python Question

I'm trying to do the same as

Python: get key with the least value from a dictionary, where we want to get the key corresponding to the minimum value in a dictionary.

The best way appears to be:

`min(d, key=d.get)`

`d = {'a' : 1, 'b' : 2, 'c' : 1}`

Note that the answer from the above would be:

`>>> min(d, key=d.get)`

'a'

However, I need

`a`

`c`

What would be the best approach?

(Ultimately I want to pick one of the two at random, but I don't think this is relevant).

Answer Source

One simple option is to first determine the minimum value, and then select all keys mapping to that minimum:

```
min_value = min(d.itervalues())
min_keys = [k for k in d if d[k] == min_value]
```

For Python 3 use `d.values()`

instead of `d.itervalues()`

.

This needs two passes through the dictionary, but should be one of the fastest options to do this anyway.

Using reservoir sampling, you can implement a single pass approach that selects one of the items at random:

```
it = d.iteritems()
min_key, min_value = next(it)
num_mins = 1
for k, v in it:
if v < min_value:
num_mins = 1
min_key, min_value = k, v
elif v == min_value:
num_mins += 1
if random.randrange(num_mins) == 0:
min_key = k
```

After writing down this code, I think this option is of rather theoretical interestâ€¦ :)