Какова эффективность key = dictionary.get? - PullRequest
Новая
       18

Какова эффективность key = dictionary.get?

3 голосов
/ 06 мая 2020

У меня есть словарь, и я хотел бы найти элегантный и эффективный способ найти пару key:value, где значение минимально по словарю (одно из минимальных, если их много). Помимо очевидных подходов for l oop, я нашел несколько других в StackOverflow:

1-й подход: 

  temporary = [x for x in myDictionary.items()] # list is created just for using sorted()
  foundKey, minimalValue = sorted(temporary, key=lambda x: x[1]) [0]

2-й подход: 

  minimalValue = min(myDictionary.values())
  foundKey = min(myDictionary, key=myDictionary.get)

Второй работает немного быстрее для myDictionary из тысяч элементов, но ... Я не могу найти объяснения конструкции key=myDictionary.get. Разве нельзя соединить две минуты в одну foundKey, minimalValue = ...?

1 Ответ

4 голосов
/ 06 мая 2020

Второй подход можно лучше перефразировать как 

foundKey = min(myDictionary, key=myDictionary.get)
minValue = myDictionary[foundKey]

Метод get извлекает значение, соответствующее проверяемому ключу, поэтому вместо сравнения key1, key2 вы сравниваете myDictionary.get[key1], myDictionary.get[key2].

Вы также можете использовать __getitem__. Вероятно, он будет быстрее, но не будет выглядеть так красиво: 

foundKey = min(myDictionary, key=myDictionary.__getitem__)

Кстати, первый подход имеет два возможных улучшения: 

temporary = list(myDictionary.items())
foundKey, minimalValue = sorted(temporary, key=lambda x: x[1])[0]

OR 

temporary = [x[::-1] for x in myDictionary.items()]
foundKey, minimalValue = min(temporary)

OR 

foundKey, minimalValue = min(zip(myDictionary.values(), myDictionary.keys()))

Время

Давайте сделаем словарь размером n: 

from random import shuffle

values = list(range(n))
shuffle(values)
myDictionary = dict(zip(map('{:08d}'.format, range(n)), values))

Время для n=10000: 

%%timeit
... temporary = [x for x in myDictionary.items()]
... foundKey, minimalValue = sorted(temporary, key=lambda x: x[1])[0]
5.76 ms ± 32.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
... minimalValue = min(myDictionary.values())
... foundKey = min(myDictionary, key=myDictionary.get)
1.85 ms ± 3.57 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Очевидно, что работа min (O(n)) быстрее, чем sorted (O(n log n)). 

%%timeit
... foundKey = min(myDictionary, key=myDictionary.get)
... minValue = myDictionary[foundKey]
1.36 ms ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Так работает min и поиск выполняется быстрее, чем запуск min дважды. 

%timeit foundKey, minimalValue = min(zip(myDictionary.values(), myDictionary.keys()))
1.32 ms ± 6.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Запуск min без поиска еще быстрее. 

%%timeit
... foundKey = min(myDictionary, key=myDictionary.__getitem__)
... minValue = myDictionary[foundKey]
1.27 ms ± 2.77 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Использование __getitem__ с поиском еще быстрее.

TL; DR

Кажется, что самый быстрый подход из представленных здесь - 

foundKey = min(myDictionary, key=myDictionary.__getitem__)
minValue = myDictionary[foundKey]
...