numpy:同时max()和min()的函数

Question

numpy.amax()将在数组中找到最大值,numpy.amin()对最小值执行相同的操作.如果我想找到max和min,我必须调用这两个函数,这需要两次遍历(非常大)数组,这似乎很慢.

numpy API中是否有一个函数可以通过数据只传递一次max和min？

Answer 1

numpy API中是否有一个函数可以通过数据只传递一次max和min？

不.在撰写本文时,没有这样的功能.(是的,如果出现了这样的功能,其性能将是显著比调用更好地numpy.amin()和numpy.amax()一个大阵上先后).

Answer 2

我不认为两次传递数组是一个问题. 考虑以下伪代码:

minval = array[0]
maxval = array[0]
for i in array:
    if i < minval:
       minval = i
    if i > maxval:
       maxval = i

虽然这里只有1个循环,但仍有2个检查.(而不是有2个循环,每个1检查).真的,你唯一能节省的就是1循环的开销.如果数组真的很大,就像你说的那样,与实际循环的工作负载相比,这种开销很小.(注意,这都是用C实现的,所以循环或多或少都是免费的).

编辑对你们4个赞成我并对我有信心的人表示抱歉.你绝对可以优化这一点.

这里有一些可以编译成python模块的fortran代码f2py(可能是一个Cythonguru可以出现并将其与优化的C版本进行比较......):

subroutine minmax1(a,n,amin,amax)
  implicit none
  !f2py intent(hidden) :: n
  !f2py intent(out) :: amin,amax
  !f2py intent(in) :: a
  integer n
  real a(n),amin,amax
  integer i

  amin = a(1)
  amax = a(1)
  do i=2, n
     if(a(i) > amax)then
        amax = a(i)
     elseif(a(i) < amin) then
        amin = a(i)
     endif
  enddo
end subroutine minmax1

subroutine minmax2(a,n,amin,amax)
  implicit none
  !f2py intent(hidden) :: n
  !f2py intent(out) :: amin,amax
  !f2py intent(in) :: a
  integer n
  real a(n),amin,amax
  amin = minval(a)
  amax = maxval(a)
end subroutine minmax2

通过以下方式编译:

f2py -m untitled -c fortran_code.f90

现在我们在一个可以测试它的地方:

import timeit

size = 100000
repeat = 10000

print timeit.timeit(
    'np.min(a); np.max(a)',
    setup='import numpy as np; a = np.arange(%d, dtype=np.float32)' % size,
    number=repeat), " # numpy min/max"

print timeit.timeit(
    'untitled.minmax1(a)',
    setup='import numpy as np; import untitled; a = np.arange(%d, dtype=np.float32)' % size,
    number=repeat), '# minmax1'

print timeit.timeit(
    'untitled.minmax2(a)',
    setup='import numpy as np; import untitled; a = np.arange(%d, dtype=np.float32)' % size,
    number=repeat), '# minmax2'

结果对我来说有点惊愕:

8.61869883537 # numpy min/max
1.60417699814 # minmax1
2.30169081688 # minmax2

我不得不说,我不完全理解它.只是比较np.min与minmax1和minmax2仍然是一场败仗,所以它不只是一个内存问题...

注意 - 增加一个因子10**a并将重复减少一个因子10**a(保持问题大小不变)确实会改变性能,但不会以看似一致的方式显示内存性能和函数调用开销之间存在一些相互作用.蟒蛇.甚至将minfortran中的简单实现与numpy的比较大约为2 ...

Answer 3

有一个函数可以找到(max-min)numpy.ptp,如果它对你有用:

>>> import numpy
>>> x = numpy.array([1,2,3,4,5,6])
>>> x.ptp()
5

但我不认为有一种方法可以通过一次遍历找到最小值和最大值.

编辑: ptp只是在引擎盖下调用min和max

Answer 4

鉴于以下方法，只是为了获得一些关于人们可以预期的数字的想法：

import numpy as np


def extrema_np(arr):
    return np.max(arr), np.min(arr)

import numba as nb


@nb.jit(nopython=True)
def extrema_loop_nb(arr):
    n = arr.size
    max_val = min_val = arr[0]
    for i in range(1, n):
        item = arr[i]
        if item > max_val:
            max_val = item
        elif item < min_val:
            min_val = item
    return max_val, min_val

import numba as nb


@nb.jit(nopython=True)
def extrema_while_nb(arr):
    n = arr.size
    odd = n % 2
    if not odd:
        n -= 1
    max_val = min_val = arr[0]
    i = 1
    while i < n:
        x = arr[i]
        y = arr[i + 1]
        if x > y:
            x, y = y, x
        min_val = min(x, min_val)
        max_val = max(y, max_val)
        i += 2
    if not odd:
        x = arr[n]
        min_val = min(x, min_val)
        max_val = max(x, max_val)
    return max_val, min_val

%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True


import numpy as np


cdef void _extrema_loop_cy(
        long[:] arr,
        size_t n,
        long[:] result):
    cdef size_t i
    cdef long item, max_val, min_val
    max_val = arr[0]
    min_val = arr[0]
    for i in range(1, n):
        item = arr[i]
        if item > max_val:
            max_val = item
        elif item < min_val:
            min_val = item
    result[0] = max_val
    result[1] = min_val


def extrema_loop_cy(arr):
    result = np.zeros(2, dtype=arr.dtype)
    _extrema_loop_cy(arr, arr.size, result)
    return result[0], result[1]

%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True


import numpy as np


cdef void _extrema_while_cy(
        long[:] arr,
        size_t n,
        long[:] result):
    cdef size_t i, odd
    cdef long x, y, max_val, min_val
    max_val = arr[0]
    min_val = arr[0]
    odd = n % 2
    if not odd:
        n -= 1
    max_val = min_val = arr[0]
    i = 1
    while i < n:
        x = arr[i]
        y = arr[i + 1]
        if x > y:
            x, y = y, x
        min_val = min(x, min_val)
        max_val = max(y, max_val)
        i += 2
    if not odd:
        x = arr[n]
        min_val = min(x, min_val)
        max_val = max(x, max_val)
    result[0] = max_val
    result[1] = min_val


def extrema_while_cy(arr):
    result = np.zeros(2, dtype=arr.dtype)
    _extrema_while_cy(arr, arr.size, result)
    return result[0], result[1]

（extrema_loop_*()方法类似于此处提出的extrema_while_*()方法，而方法基于此处的代码）

以下时间：

表示extrema_while_*()速度最快，extrema_while_nb()速度最快。在任何情况下，extrema_loop_nb()和extrema_loop_cy()解决方案也优于仅使用 NumPy 的方法（单独使用np.max()和np.min()）。

最后，请注意，这些都没有np.min()/灵活np.max()（在 n-dim 支持、axis参数等方面）。

（完整代码可在此处获得）

Answer 5

您可以使用Numba,这是一个使用LLVM的NumPy感知动态Python编译器.最终的实现非常简单明了:

import numpy
import numba


@numba.jit
def minmax(x):
    maximum = x[0]
    minimum = x[0]
    for i in x[1:]:
        if i > maximum:
            maximum = i
        elif i < minimum:
            minimum = i
    return (minimum, maximum)


numpy.random.seed(1)
x = numpy.random.rand(1000000)
print(minmax(x) == (x.min(), x.max()))

它也应该比Numpy的min() & max()实现更快.而且无需编写单个C/Fortran代码行.

做自己的性能测试,因为它总是取决于您的架构,数据,包版本......

Answer 6

这是一个老线程,但无论如何,如果有人再次看到这个......

当同时寻找最小值和最大值时,可以减少比较次数.如果它是浮动的你正在比较(我猜它是)这可能会节省你一些时间,虽然不是计算复杂性.

而不是(Python代码):

_max = ar[0]
_min=  ar[0]
for ii in xrange(len(ar)):
    if _max > ar[ii]: _max = ar[ii]
    if _min < ar[ii]: _min = ar[ii]

您可以先比较阵列中的两个相邻值,然后仅将较小的值与当前最小值进行比较,将较大的值与当前最大值进行比较:

## for an even-sized array
_max = ar[0]
_min = ar[0]
for ii in xrange(0, len(ar), 2)):  ## iterate over every other value in the array
    f1 = ar[ii]
    f2 = ar[ii+1]
    if (f1 < f2):
        if f1 < _min: _min = f1
        if f2 > _max: _max = f2
    else:
        if f2 < _min: _min = f2
        if f1 > _max: _max = f1

这里的代码是用Python编写的,显然是为了你使用C或Fortran或Cython的速度,但这样你每次迭代进行3次比较,使用len(ar)/ 2次迭代,给出3/2*len(ar)比较.与此相反,进行比较"显而易见",每次迭代进行两次比较,导致2*len(ar)比较.为您节省25%的比较时间.

也许某人有一天会觉得这很有用.

Answer 7

没有人提到numpy.percentile，所以我想我会的。如果您要求[0, 100]百分位，它将为您提供两个元素的数组，最小（第0个百分位）和最大（第100个百分位）。

但是，它不能满足OP的目的：它不比单独的min和max快。这可能是由于一些机制将允许非极端百分位数（一个困难的问题，这应该需要更长的时间）。

In [1]: import numpy

In [2]: a = numpy.random.normal(0, 1, 1000000)

In [3]: %%timeit
   ...: lo, hi = numpy.amin(a), numpy.amax(a)
   ...: 
100 loops, best of 3: 4.08 ms per loop

In [4]: %%timeit
   ...: lo, hi = numpy.percentile(a, [0, 100])
   ...: 
100 loops, best of 3: 17.2 ms per loop

In [5]: numpy.__version__
Out[5]: '1.14.4'

如果仅[0, 100]要求，Numpy的未来版本可能会出现特殊情况以跳过正常的百分位数计算。在不向接口添加任何内容的情况下，有一种方法可以在一次调用中向Numpy询问最小值和最大值（与接受的答案中所说的相反），但是该库的标准实现没有利用这种情况来实现这一点值得。

Answer 8

通常,您可以通过一次处理两个元素并仅将较小的元素与临时最小值进行比较,将较大的元素与临时最大值进行比较来减少minmax算法的比较量.平均而言,只需要3/4的比较而不是天真的方法.

这可以用c或fortran(或任何其他低级语言)实现,并且在性能方面几乎是无与伦比的.我正在使用numba来说明原理并获得一个非常快速的,与dtype无关的实现:

import numba as nb
import numpy as np

@nb.njit
def minmax(array):
    # Ravel the array and return early if it's empty
    array = array.ravel()
    length = array.size
    if not length:
        return

    # We want to process two elements at once so we need
    # an even sized array, but we preprocess the first and
    # start with the second element, so we want it "odd"
    odd = length % 2
    if not odd:
        length -= 1

    # Initialize min and max with the first item
    minimum = maximum = array[0]

    i = 1
    while i < length:
        # Get the next two items and swap them if necessary
        x = array[i]
        y = array[i+1]
        if x > y:
            x, y = y, x
        # Compare the min with the smaller one and the max
        # with the bigger one
        minimum = min(x, minimum)
        maximum = max(y, maximum)
        i += 2

    # If we had an even sized array we need to compare the
    # one remaining item too.
    if not odd:
        x = array[length]
        minimum = min(x, minimum)
        maximum = max(x, maximum)

    return minimum, maximum

它绝对比Peque提出的朴素方法更快:

arr = np.random.random(3000000)
assert minmax(arr) == minmax_peque(arr)  # warmup and making sure they are identical 
%timeit minmax(arr)            # 100 loops, best of 3: 2.1 ms per loop
%timeit minmax_peque(arr)      # 100 loops, best of 3: 2.75 ms per loop

正如预期的那样,新的minmax实现仅花费大约3/4的时间实现天真的实现(2.1 / 2.75 = 0.7636363636363637)

Answer 9

乍一看，似乎可以解决问题：numpy.histogram

count, (amin, amax) = numpy.histogram(a, bins=1)

......但如果你看看源为该函数，它只是简单地调用a.min()和a.max()独立，因此无法避免业绩的担忧在这个问题解决。:-(

同样的，scipy.ndimage.measurements.extrema看起来像一个可能性，但它也只是调用a.min()和a.max()独立。