在python列表中找到最小浮点数的最有效方法

Question

快速问题,更有效的查找长列表中的最小数字(浮点数)(10000+元素)

是吗

min(mylist)

要么

mylist.sort() 

然后回来

mylist[0]

或者是其他东西...

谢谢!

Answer 1

首先,如果你关心Python中的性能(这并不总是一件值得关注的事情,但这是另一个对话),你应该使用timeit模块.即使在C语言中,很难预测某些函数在编译后会如何表现,而且在Python中更难.人们常常自信地表达哪些功能更快,哪些是数据依赖的.那么 - 通过使用timeit,我的意思是 - 你可以找到自己.

其次,如果你真的关心浮点数列表的性能,你根本不应该使用列表,而是使用numpy数组.在这里使用IPython,在Python 2.7.2下,这使得计时变得简单:

In [41]: import random, numpy
In [42]: a = [0.1*i for i in range(10**5)]
In [43]: timeit min(a)
100 loops, best of 3: 4.55 ms per loop
In [44]: timeit sorted(a)[0]
100 loops, best of 3: 4.57 ms per loop
In [45]: random.shuffle(a)
In [46]: timeit min(a)
100 loops, best of 3: 6.06 ms per loop
In [47]: timeit min(a) # to make sure it wasn't a fluke
100 loops, best of 3: 6.07 ms per loop
In [48]: timeit sorted(a)[0]
10 loops, best of 3: 65.9 ms per loop
In [49]: b = numpy.array(a)
In [50]: timeit b.min()
10000 loops, best of 3: 97.5 us per loop

我们注意到一些事情.(1)Python的sort(timsort)对已经排序的运行的数据非常有效,因此对已排序的列表进行排序几乎没有任何惩罚.(2)另一方面,对随机列表进行排序要慢得多,而且随着数据变大,这种情况只会变得更糟.(3)浮点数组上的Numpy.min()在Python列表上的运行速度比min小60倍,因为它不必像一般情况那样.

Answer 2

如果已填充列表,min()则是最有效的方法.

在特殊情况下可能会使用一些技巧:

• 如果您从头开始构建列表,只需将最小的项保留在外部变量中,以便给出答案O(1).
• 如果列表中只有Floats,请使用可提供更好性能的Array.
• 您可以使用bisect保持列表排序.
• 使用Python堆,它甚至可以有效地实现min().确保您了解效果,主要是插入速度较慢.(信用:interjay)