CODEWITHSUNDEEP
pythonlistdictionarylist-comprehension
dobero
dobero

Reputation: 71

Comprehension to find the min in a dict

I am curious about a thing:

I have a dict, for example with a car as key and a value regarding its speed. Now, I want to find the key with the lowest value.

car_dict = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}

I know this code works with O(1)

car_value = list(car_dict.values())
car_key = list(car_dict.keys())
min_stats = min(car_value)
print(car_key[car_value.index(min_stats)])

and this one too with O(n)

keys = []
values = []
for name, value in car_dict.items():
    keys.append(name)
    values.append(value)

min_value = min(values)
print(keys[values.index(min_value)])

I am currently trying to better understand comprehensions, therefore, my question is if there would be a possible approach to this problem with list comprehensions.

I was thinking about something like this

worst = {name for name, stats in car_dict if min(stats)}

However, I guess that I still misunderstand something in the if part.

BTW correct me if I am wrong with my belief in the Big O complexity above.

Thanks a lot!

Upvotes: 1

Views: 904

Answers (6)

jpp
jpp

Reputation: 164773

I know this code works with O(1):

car_value = list(car_dict.values())

This is incorrect. To form a list from a view you must iterate over all values. This operation will have time complexity of O(n).

In general, creating a list of keys and values is not necessary. Avoid these operations as they are expensive.

Note that min can work directly on dict.items, which is a view of key-value pairs. This is only advisable if you only have a single car with the minimum value:

car, value = min(car_dict.items(), key=lambda x: x[1])  # (fiat, 100)

Since dictionaries are not considered ordered (unless you are using Python 3.7), for duplicate minima the result will not be certain. In this case, you can calculate the minimum value and then use a list comprehension:

min_val = min(car_dict.values())
min_cars = [car for car, value in car_dict.items() if value == min_val]  # ['fiat']

You can also use next with a generator expression to extract the first such car:

min_car_first = next(car for car, value in car_dict.items() if value == min_val)

Of course, in the case of a single car with the minimum value, this will give the same result as the first solution min(car_dict.items(), ...).

Upvotes: 2

Manu Valdés
Manu Valdés

Reputation: 2372

The thing is you shouldn't solve this problem with a comprehension because you can't do assignment in a comprehension. Iterating the dictionary you can find the minimum in a single pass:

car_iterator = iter(car_dict.items())
slowest_car, min_speed = next(car_list)
for car, speed in car_iterator:
    if speed < min_speed:
        slowest_car = car

Upvotes: 0

user2575725
user2575725

Reputation:

How about this:

car_dict = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}
min_car = {}
for car in car_dict:
    if not min_car or car_dict[car] < min_car['speed']:
        min_car['name'] = car
        min_car['speed'] = car_dict[car]
print(min_car)

Upvotes: 0

Moh Sawas
Moh Sawas

Reputation: 11

well I'm not sure what is the run time of this one but you can try it it works for me : 

>>> d = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}
>>> d.items()
[('mercedes', 200), ('fiat', 100), ('porsche', 300) , ('rocketcar',600)]
>>> # find the minimum by comparing the second element of each tuple
>>> min(d.items(), key=lambda x: x[1]) 
('fiat', 100)

Upvotes: 0

vash_the_stampede
vash_the_stampede

Reputation: 4606

This would do you can compare the key's value to the min of the values

worst = [i for i in car_dict if car_dict[i] == min(car_dict.values())]

Upvotes: 0

DYZ
DYZ

Reputation: 57085

You cannot solve this problem in faster than linear time, but you can solve it in linear time in one pass:

min_speed = None
that_car = None
for car,speed in car_dict.items():
    if min_speed is None or speed < min_speed:
        that_car, min_speed = car, speed
that_car
#'fiat'

Upvotes: 0

Related Questions