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

Question

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

3

我有一个包含成千上万个单词：值（浮点数）对的大型集合。我需要找到最佳值并提取相应的相关单词。例如，我有(a,2.4),(b,5.2),(c,1.2),(d,9.2),(e,6.3),(f,0.4)。我希望输出为(d,9.2)。

目前，我正在使用字典来存储这些元组，并使用max运算符在字典中检索最大键值。我想知道是否可以使用numpy数组更有效。在这里征求专家意见。

- Dexter

你需要将元组存储在一个结构中，还是可以动态生成它们？如果你需要多个最大项，可以使用 'heapq' http://docs.python.org/library/heapq.html。你正在解决什么样的问题，你确定这部分是问题的源头吗？ - Luka Rahne

我需要将元组存储在一个结构中。我只想找到最大的数字值和相应的“键”。 - Dexter

2个回答

3

使用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考虑了这一点）

- Janne Karila

“我在想使用NumPy数组是否更有效率”... 答案是什么？ - mac

@mac 在答案中添加了结论。 - Janne Karila

我们真的需要更多的信息才能回答这个问题。他说他目前正在使用一个字典存储这些单词值对，他是否愿意改为在ndarray中存储它们呢？ - Bi Rico

Bago，是的，我愿意将它存储在ndarray中。我对Janne的问题是，如果考虑Numpy数组构建，Numpy > List/Dict是否仍然成立？ - Dexter

1

@Denzil 不要使用Numpy数组，如果只是用于取最大值。在我的示例中，fd函数就是这样做的，而且它是最慢的。 - Janne Karila

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mac · Accepted Answer

我不认为在这种情况下使用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'

HTH!