Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficiently find the range of an array in python?

Is there an accepted efficient way to find the range (ie. max value - min value) of a list of numbers in python? I have tried using a loop and I know I can use the min and max functions with subtraction. I am just wondering if there is some kind of built-in that is faster.

like image 351
dinkelk Avatar asked Dec 01 '22 05:12

dinkelk


2 Answers

If you really need high performance, try Numpy. The function numpy.ptp computes the range of values (i.e. max - min) across an array.

like image 82
nneonneo Avatar answered Dec 05 '22 16:12

nneonneo


You're unlikely to find anything faster than the min and max functions.

You could possibly code up a minmax function which did a single pass to calculate the two values rather than two passes but you should benchmark this to ensure it's faster. It may not be if it's written in Python itself but a C routine added to Python may do it. Something like (pseudo-code, even though it looks like Python):

def minmax (arr):
    if arr is empty:
        return (None, None)
    themin = arr[0]
    themax = arr[0]
    for each value in arr[1:]:
        if value < themin:
            themin = value
        else:
            if value > themax:
                themax = value
    return (themin, themax)

Another possibility is to interpose your own class around the array (this may not be possible if you want to work on real arrays directly). This would basically perform the following steps:

  • mark the initial empty array clean.
  • if adding the first element to an array, set themin and themax to that value.
  • if adding element to a non-empty array, set themin and themax depending on how the new value compares to them.
  • if deleting an element that is equal to themin or themax, mark the array dirty.
  • if requesting min and max from a clean array, return themin and themax.
  • if requesting min and max from a dirty array, calculate themin and themax using loop in above pseudo-code, then set array to be clean.

What this does is to cache the minimum and maximum values so that, at worst, you only need to do the big calculation infrequently (after deletion of an element which was either the minimum or maximum). All other requests use cached information.

In addition, the adding of elements keep themin and themax up to date without a big calculation.

And, possibly even better, you could maintain a dirty flag for each of themin and themax, so that dirtying one would still allow you to use the cached value of the nother.

like image 28
paxdiablo Avatar answered Dec 05 '22 15:12

paxdiablo