numpy  2.0.0
src/private/npy_partition.h.src File Reference
#include "npy_sort.h"
#include <Python.h>
#include <numpy/npy_common.h>
#include <numpy/ndarraytypes.h>

Data Structures

struct  part_map

Defines

#define __NPY_PARTITION_H__
#define NPY_MAX_PIVOT_STACK   50

Functions

NPY_VISIBILITY_HIDDEN int
introselect_ 
suff (@type @*v, npy_intp num, npy_intp kth, npy_intp *pivots, npy_intp *npiv, void *NOT_USED)
NPY_VISIBILITY_HIDDEN int
aintroselect_ 
suff (@type @*v, npy_intp *tosort, npy_intp num, npy_intp kth, npy_intp *pivots, npy_intp *npiv, void *NOT_USED)
static NPY_INLINE
PyArray_PartitionFunc
get_partition_func (int type, NPY_SELECTKIND which)
static NPY_INLINE
PyArray_ArgPartitionFunc
get_argpartition_func (int type, NPY_SELECTKIND which)

Variables

static part_map _part_map []

Define Documentation

#define NPY_MAX_PIVOT_STACK   50
Python include is for future object sorts

Referenced by store_pivot().


Function Documentation

static NPY_INLINE PyArray_ArgPartitionFunc* get_argpartition_func ( int  type,
NPY_SELECTKIND  which 
) [static]
static NPY_INLINE PyArray_PartitionFunc* get_partition_func ( int  type,
NPY_SELECTKIND  which 
) [static]
NPY_VISIBILITY_HIDDEN int introselect_ suff ( @type @*  v,
npy_intp  num,
npy_intp  kth,
npy_intp pivots,
npy_intp npiv,
void *  NOT_USED 
)
begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE#
suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong, half, float, double, longdouble, cfloat, cdouble, clongdouble#
#type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong, npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat, npy_cdouble, npy_clongdouble#

</blockquote>

iterative median of 3 quickselect with cutoff to median-of-medians-of5 receives stack of already computed pivots in v to minimize the partition size were kth is searched in
area that needs partitioning in [...] kth 0: [8 7 6 5 4 3 2 1 0] -> med3 partitions elements [4, 2, 0]

System Message: ERROR/3 (<string>, line 7) Unexpected indentation.

<blockquote> 0 1 2 3 4 8 7 5 6 -> pop requested kth -> stack [4, 2]</blockquote>

System Message: WARNING/2 (<string>, line 8) Block quote ends without a blank line; unexpected unindent.
kth 3: 0 1 2 [3] 4 8 7 5 6 -> stack [4] kth 5: 0 1 2 3 4 [8 7 5 6] -> stack [6] kth 8: 0 1 2 3 4 5 6 [8 7] -> stack []
pivot larger than kth set it as upper bound
kth was already found in a previous iteration -> done
pop from stack
use a faster O(n*kth) algorithm for very small kth e.g. for interpolating percentile
useful to check if NaN present via partition(d, (x, -1))
guarantee three elements
if we aren't making sufficient progress with median of 3 fall back to median-of-median5 pivot for linear worst case med3 for small sizes is required to do unguarded partition
median of 3 pivot strategy, swapping for efficient partition
FIXME: always use pivots to optimize this iterative partition
adapt for the larger partition than med3 pivot
find place to put pivot (in low): previous swapping removes need for bound checks pivot 3-lowest [x x x] 3-highest
move pivot into position
kth pivot stored later
two elements

References IDX, and TYPE.

NPY_VISIBILITY_HIDDEN int aintroselect_ suff ( @type @*  v,
npy_intp tosort,
npy_intp  num,
npy_intp  kth,
npy_intp pivots,
npy_intp npiv,
void *  NOT_USED 
)

Variable Documentation

part_map _part_map[] [static]
Initial value:
 {

    {
        NPY_@TYPE@,
        {
            (PyArray_PartitionFunc *)&introselect_@suff@,
        },
        {
            (PyArray_ArgPartitionFunc *)&aintroselect_@suff@,
        }
    },

}