Производительность поиска максимального значения в словаре по сравнению с массивом numpy - PullRequest
Новая
       22

Производительность поиска максимального значения в словаре по сравнению с массивом numpy

2 голосов
/ 01 января 2012

У меня есть большая (в тысячах) коллекция пар слово: значение (число с плавающей запятой).Мне нужно найти лучшее из значения и извлечь соответствующее связанное слово.Например, у меня есть (a, 2.4), (b, 5.2), (c, 1.2), (d, 9.2), (e, 6.3), (f, 0.4).Я хотел бы (d, 9.2) в качестве вывода.

В настоящее время я использую словарь для хранения этих кортежей и использую оператор max, чтобы получить максимальное значение ключа в словаре.Мне было интересно, если бы NumPy массив был бы более эффективным.Запрашивать мнения экспертов здесь.

Ответы [ 2 ]

4 голосов
/ 01 января 2012

Я не понимаю, как в этом случае вам поможет массив numpy.

В частности, любое преобразование структуры данных в другую (в вашем случае список кортежей в массиве NumPy или heapq) будет намного медленнее, чем поиск максимального значения, повторяющегося в каждом кортеже). Это связано с тем, что для преобразования структуры данных также потребуется выполнить итерации по сравнению с исходной, создать экземпляр объекта для новой структуры, сохранить значение в новой структуре и использовать новую структуру для получения запрошенного значения.

Использование встроенной функции или метода из вашего списка, скорее всего, приведет к более быстрым вычислениям. Самая тривиальная реализация, которую я могу придумать: 

>>> li = [('a',  10), ('b', 30), ('c', 20)]
>>> max(li, key=lambda e : e[1])[0]
'b'

Другие возможные варианты, если вас также интересуют такие вещи, как наименьшее значение или удаление из списка найденного значения, которое может пройти через сортировку (поэтому вы проверяете исходный список только один раз!): 

>>> li = [('a',  10), ('b', 30), ('c', 20)]
>>> li.sort(key=lambda e : e[1])
>>> li
[('a', 10), ('c', 20), ('b', 30)]
>>> li[-1][0]
'b'

Или: 

>>> sorted(li, key=lambda e: e[1])[-1][0]
'b'

НТН!

2 голосов
/ 01 января 2012

Использование здесь Numpy предполагает сохранение значений с плавающей запятой в отдельном ndarray.Найдите индекс максимального значения, используя argmax, и получите слово из отдельного списка.Это очень быстро, но построить ndarray только для того, чтобы найти максимум, нет.Пример: 

import numpy as np
import operator

names = [str(x) for x in xrange(10000)]
values = [float(x) for x in xrange(10000)]
tuples = zip(names, values)
dic = dict(tuples)
npvalues = np.fromiter(values, np.float)

def fa():
    return names[npvalues.argmax()]

def fb():
    return max(tuples, key=operator.itemgetter(1))[0]

def fc():
    return max(dic, key=dic.get)

def fd():
    v = np.fromiter((x[1] for x in tuples), np.float)
    return tuples[v.argmax()][0]

Время: fa 67 мкс, fb 2300 мкс, fc 2580 мкс, fd 3780 мкс.

Таким образом, использование Numpy (fa) более чем в 30 раз быстрее, чем использованиепростой список (fb) или словарь (fc), когда время для построения массива Numpy не учитывается.(ФД учитывает это)

...