在字典和numpy数组中寻找最大值的性能比较

Question

我有一大堆成千上万的单词和对应的数值（浮点数）对。现在我需要找出这些数值中最大的那个，并提取出它对应的单词。比如说，我有这些对：(a,2.4)、(b,5.2)、(c,1.2)、(d,9.2)、(e,6.3)、(f,0.4)。我想要的结果是(d,9.2)。

目前，我是用字典来存储这些数据对，然后用最大值操作来找出字典中最大的数值。我在想，使用numpy数组会不会更高效一些。希望能听听专家的意见。

Answer 1

我觉得在这种情况下，使用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'

希望对你有帮助！

Answer 2

在这里使用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数组的时间时，使用Numpy（fa）比使用普通列表（fb）或字典（fc）快了超过30倍。（fd是考虑了这个时间的）