most efficent way of finding the minimum float in a python list

Question

Quick question, which is more efficient for finding the smallest number (float) in a long list (10000+ elements)

is it

min(mylist)

or

mylist.sort() 

and then returning

mylist[0]

or something else...

thanks!

Answer 1

Frst, if you care about performance in Python (which isn't always a sensible thing to care about, but that's another conversation), you should be using the timeit module. Even in C it's hard to predict how certain functions will behave after compilation, and it's harder in Python. People are often confidently expressing opinions about which functions are faster which are data-dependent. Then -- by using timeit, I mean -- you could've found out yourself.

Second, if you really care about performance on lists of floats, you shouldn't be using lists at all, but numpy arrays. Using IPython here, under Python 2.7.2, which makes timing things easy:

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

And we note a few things. (1) Python's sort (timsort) works very well on data which has sorted runs, so sorting an already sorted list has almost no penalty. (2) Sorting a random list, on the other hand, is very much slower, and this will only get worse as the data gets larger. (3) Numpy.min() on a float array works sixty times faster than min on a Python list, because it doesn't have to be as general.

Answer 2

If the list is already populated, min() is the most efficient way.

There are some tricks you might use in special scenarios:

• If you build the list from scratch, simply keep the smallest item yet in an external variable, so that the answer will be given in O(1).
• If there are only Floats in the list, use an Array which gives better performance.
• You can keep the list sorted using bisect.
• Use a Python Heap, which even has an efficient implementation of min(). Make sure you understand the effects, mainly a slower insertion. (credit: interjay)