numpy 如何找到 array/list 中的中位数？

Question

我读到，numpy 使用 introselect 来查找数组/列表中的中位数（https://www.researchgate.net/publication/303755458_Fast_Deterministic_Selection) [page 2; last 5 lines]. But I couldn't find any hints for that in the numpy source code: https://github.com/numpy/numpy/blob/v1.19.0/numpy/lib/function_base.py#L3438-L3525

有谁知道我在哪里可以找到 introselect 的 numpy 实现？或者，如果 numpy 不使用 introselect，则使用哪种算法来查找中位数？

非常感谢:)

Answer 1

第3528行好像是主要的中位函数。如果我们删除所有多维和 nan 的东西，我们会得到类似

的东西

def _median(a, axis=None, out=None, overwrite_input=False):
    # can't be reasonably be implemented in terms of percentile as we have to
    # call mean to not break astropy

    # Set the partition indexes
    sz = a.shape
    if sz % 2 == 0:
        szh = sz // 2
        kth = [szh - 1, szh]
    else:
        kth = [(sz - 1) // 2]

    part = partition(a, kth, axis=None)

    return mean(part[indexer], axis=None, out=out)

所以分区完成了所有工作并且来自

from numpy.core.fromnumeric import (
    ravel, nonzero, partition, mean, any, sum
    )

如果我们转到 numpy 代码，我们将得到以下 C code。

NPY_SELECTKIND sortkind = NPY_INTROSELECT;

和

val = PyArray_Partition(self, ktharray, axis, sortkind);

实现了here并使用了

mid = ll + median_of_median5_@suff@(v + ll, hh - ll, NULL, NULL);

所以是introselect。

一旦达到递归深度的两倍，算法就会更改为使用中位数中位数 5，直到分区小于 5。

numpy 如何找到 array/list 中的中位数？

how does numpy find the median in an array/list?

python

algorithm

numpy

median