numpy  2.0.0
src/multiarray/item_selection.c File Reference
#include <Python.h>
#include "structmember.h"
#include "numpy/arrayobject.h"
#include "numpy/arrayscalars.h"
#include "numpy/npy_math.h"
#include "numpy/npy_cpu.h"
#include "npy_config.h"
#include "npy_pycompat.h"
#include "common.h"
#include "arrayobject.h"
#include "ctors.h"
#include "lowlevel_strided_loops.h"
#include "item_selection.h"
#include "npy_sort.h"
#include "npy_partition.h"
#include "npy_binsearch.h"

Defines

#define PY_SSIZE_T_CLEAN
#define NPY_NO_DEPRECATED_API   NPY_API_VERSION
#define _MULTIARRAYMODULE

Functions

NPY_NO_EXPORT PyObject * PyArray_TakeFrom (PyArrayObject *self0, PyObject *indices0, int axis, PyArrayObject *out, NPY_CLIPMODE clipmode)
NPY_NO_EXPORT PyObject * PyArray_PutTo (PyArrayObject *self, PyObject *values0, PyObject *indices0, NPY_CLIPMODE clipmode)
NPY_NO_EXPORT PyObject * PyArray_PutMask (PyArrayObject *self, PyObject *values0, PyObject *mask0)
NPY_NO_EXPORT PyObject * PyArray_Repeat (PyArrayObject *aop, PyObject *op, int axis)
NPY_NO_EXPORT PyObject * PyArray_Choose (PyArrayObject *ip, PyObject *op, PyArrayObject *out, NPY_CLIPMODE clipmode)
static int _new_sortlike (PyArrayObject *op, int axis, PyArray_SortFunc *sort, PyArray_PartitionFunc *part, npy_intp *kth, npy_intp nkth)
static PyObject * _new_argsortlike (PyArrayObject *op, int axis, PyArray_ArgSortFunc *argsort, PyArray_ArgPartitionFunc *argpart, npy_intp *kth, npy_intp nkth)
NPY_NO_EXPORT int PyArray_Sort (PyArrayObject *op, int axis, NPY_SORTKIND which)
static PyArrayObjectpartition_prep_kth_array (PyArrayObject *ktharray, PyArrayObject *op, int axis)
NPY_NO_EXPORT int PyArray_Partition (PyArrayObject *op, PyArrayObject *ktharray, int axis, NPY_SELECTKIND which)
NPY_NO_EXPORT PyObject * PyArray_ArgSort (PyArrayObject *op, int axis, NPY_SORTKIND which)
NPY_NO_EXPORT PyObject * PyArray_ArgPartition (PyArrayObject *op, PyArrayObject *ktharray, int axis, NPY_SELECTKIND which)
NPY_NO_EXPORT PyObject * PyArray_LexSort (PyObject *sort_keys, int axis)
NPY_NO_EXPORT PyObject * PyArray_SearchSorted (PyArrayObject *op1, PyObject *op2, NPY_SEARCHSIDE side, PyObject *perm)
NPY_NO_EXPORT PyObject * PyArray_Diagonal (PyArrayObject *self, int offset, int axis1, int axis2)
NPY_NO_EXPORT PyObject * PyArray_Compress (PyArrayObject *self, PyObject *condition, int axis, PyArrayObject *out)
static NPY_INLINE npy_intp count_nonzero_bytes_384 (const npy_uint64 *w)
NPY_NO_EXPORT npy_intp count_boolean_trues (int ndim, char *data, npy_intp *ashape, npy_intp *astrides)
NPY_NO_EXPORT npy_intp PyArray_CountNonzero (PyArrayObject *self)
NPY_NO_EXPORT PyObject * PyArray_Nonzero (PyArrayObject *self)
NPY_NO_EXPORT PyObject * PyArray_MultiIndexGetItem (PyArrayObject *self, npy_intp *multi_index)
NPY_NO_EXPORT int PyArray_MultiIndexSetItem (PyArrayObject *self, npy_intp *multi_index, PyObject *obj)

Define Documentation

#define NPY_NO_DEPRECATED_API   NPY_API_VERSION

Function Documentation

static PyObject* _new_argsortlike ( PyArrayObject op,
int  axis,
PyArray_ArgSortFunc argsort,
PyArray_ArgPartitionFunc argpart,
npy_intp kth,
npy_intp  nkth 
) [static]
Check if there is any argsorting to do
For dtype's with objects, copyswapn Py_XINCREF's src and Py_XDECREF's dst. This would crash if called on an uninitialized valbuffer, or leak a reference to each object item if initialized.
So, first do the copy with no refcounting...
...then swap in-place if needed
Out of memory during sorting or buffer creation
static int _new_sortlike ( PyArrayObject op,
int  axis,
PyArray_SortFunc sort,
PyArray_PartitionFunc part,
npy_intp kth,
npy_intp  nkth 
) [static]
These algorithms use special sorting. They are not called unless the underlying sort function for the type is available. Note that axis is already valid. The sort functions require 1-d contiguous and well-behaved data. Therefore, a copy will be made of the data if needed before handing it to the sorting routine. An iterator is constructed and adjusted to walk over all but the desired sorting axis.
Check if there is any sorting to do
For dtype's with objects, copyswapn Py_XINCREF's src and Py_XDECREF's dst. This would crash if called on an uninitialized buffer, or leak a reference to each object if initialized.
So, first do the copy with no refcounting...
...then swap in-place if needed
TODO: If the input array is byte-swapped but contiguous and aligned, it could be swapped (and later unswapped) in-place rather than after copying to the buffer. Care would have to be taken to ensure that, if there is an error in the call to sort or part, the unswapping is still done before returning.
Out of memory during sorting or buffer creation
NPY_NO_EXPORT npy_intp count_boolean_trues ( int  ndim,
char *  data,
npy_intp ashape,
npy_intp astrides 
)
Counts the number of True values in a raw boolean array. This is a low-overhead function which does no heap allocations.
Returns -1 on error.
Use raw iteration with no heap memory allocation
Handle zero-sized array
Special case for contiguous inner loop
Process the innermost dimension
General inner loop
Process the innermost dimension
static NPY_INLINE npy_intp count_nonzero_bytes_384 ( const npy_uint64 *  w) [static]
count number of nonzero bytes in 48 byte block w must be aligned to 8 bytes
even though it uses 64 bit types its faster than the bytewise sum on 32 bit but a 32 bit type version would make it even faster on these platforms
last part of sideways add popcount, first three bisections can be skipped as we are dealing with bytes. multiplication equivalent to (x + (x>>8) + (x>>16) + (x>>24)) & 0xFF multiplication overflow well defined for unsigned types. w1 + w2 guaranteed to not overflow as we only have 0 and 1 data.
bytes not exclusively 0 or 1, sum them individually. should only happen if one does weird stuff with views or external buffers. Doing this after the optimistic computation allows saving registers and better pipelining
reload from pointer to avoid a unnecessary stack spill with gcc
static PyArrayObject* partition_prep_kth_array ( PyArrayObject ktharray,
PyArrayObject op,
int  axis 
) [static]
make kth array positive, ravel and sort it
2013-05-18, 1.8
sort the array of kths so the partitions will not trample on each other
NPY_NO_EXPORT PyObject* PyArray_ArgPartition ( PyArrayObject op,
PyArrayObject ktharray,
int  axis,
NPY_SELECTKIND  which 
)
ArgPartition an array
Use sorting, slower but equivalent
Process ktharray even if using sorting to do bounds checking
NPY_NO_EXPORT PyObject* PyArray_ArgSort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
)
ArgSort an array
NPY_NO_EXPORT PyObject* PyArray_Choose ( PyArrayObject ip,
PyObject *  op,
PyArrayObject out,
NPY_CLIPMODE  clipmode 
)
Convert all inputs to arrays of a common type Also makes them C-contiguous
Broadcast all arrays to each other, index array at the end.
Set-up return array
we need to make sure and get a copy so the input array is not changed before the error is called
NPY_NO_EXPORT PyObject* PyArray_Compress ( PyArrayObject self,
PyObject *  condition,
int  axis,
PyArrayObject out 
)
Compress
Counts the number of non-zero elements in the array. <blockquote> Returns -1 on error.</blockquote>
Special low-overhead version specific to the boolean type
If it's a trivial one-dimensional loop, don't use an iterator
If the array has size zero, return zero (the iterator rejects size zero arrays)
Otherwise create and use an iterator to count the nonzeros.
Get the pointers for inner loop iteration
Iterate over all the elements to count the nonzeros

References NpyIter_Deallocate().

NPY_NO_EXPORT PyObject* PyArray_Diagonal ( PyArrayObject self,
int  offset,
int  axis1,
int  axis2 
)
Diagonal <blockquote> In NumPy versions prior to 1.7, this function always returned a copy of the diagonal array. In 1.7, the code has been updated to compute a view onto 'self', but it still copies this array before returning, as well as setting the internal WARN_ON_WRITE flag. In a future version, it will simply return a view onto self.</blockquote>
Handle negative axes with standard Python indexing rules
Error check the two axes
Get the shape and strides of the two axes
Compute the data pointers and diag_size for the view
Build the new shape and strides for the main data
Create the diagonal view
For numpy 1.9 the diagonal view is not writeable. This line needs to be removed in 1.10.

References c.

NPY_NO_EXPORT PyObject* PyArray_LexSort ( PyObject *  sort_keys,
int  axis 
)
LexSort an array providing indices that will sort a collection of arrays lexicographically. The first key is sorted on first, followed by the second key -- requires that arg"merge"sort is available for each sort_key
Returns an index array that shows the indexes for the lexicographic sort along the given axis.
Now we can check the axis
single element case
Now do the sorting
Out of memory during sorting or buffer creation
NPY_NO_EXPORT PyObject* PyArray_MultiIndexGetItem ( PyArrayObject self,
npy_intp multi_index 
)
Gets a single item from the array, based on a single multi-index array of values, which must be of length PyArray_NDIM(self).
Get the data pointer
NPY_NO_EXPORT int PyArray_MultiIndexSetItem ( PyArrayObject self,
npy_intp multi_index,
PyObject *  obj 
)
Sets a single item in the array, based on a single multi-index array of values, which must be of length PyArray_NDIM(self).
Returns 0 on success, -1 on failure.
Get the data pointer
Nonzero <blockquote> TODO: In NumPy 2.0, should make the iteration order a parameter.</blockquote>
First count the number of non-zeros in 'self'.
Allocate the result as a 2D array
If it's a one-dimensional result, don't use an iterator
nothing to do
avoid function call for bool
use fast memchr variant for sparse data, see gh-4370 the fast bool count is followed by this sparse path is faster than combining the two loops, even for larger arrays
Build an iterator tracking a multi-index, in C order.
Get the pointers for inner loop iteration
Get the multi-index for each non-zero element
avoid function call for bool
Treat zero-dimensional as shape (1,)
Create views into ret, one for each dimension

References check_and_adjust_index(), PyArray_DATA, PyArray_DESCR, PyArray_NDIM, PyArray_SHAPE(), and PyArray_STRIDES.

Referenced by array_sum().

NPY_NO_EXPORT int PyArray_Partition ( PyArrayObject op,
PyArrayObject ktharray,
int  axis,
NPY_SELECTKIND  which 
)
Partition an array in-place
Use sorting, slower but equivalent
Process ktharray even if using sorting to do bounds checking
NPY_NO_EXPORT PyObject* PyArray_PutMask ( PyArrayObject self,
PyObject *  values0,
PyObject *  mask0 
)
Put values into an array according to a mask.

<

zero if null array

Referenced by _pyarray_revert().

NPY_NO_EXPORT PyObject* PyArray_PutTo ( PyArrayObject self,
PyObject *  values0,
PyObject *  indices0,
NPY_CLIPMODE  clipmode 
)
Put values into an array
NPY_NO_EXPORT PyObject* PyArray_Repeat ( PyArrayObject aop,
PyObject *  op,
int  axis 
)
Repeat the array.
Scalar and size 1 'repeat' arrays broadcast to any shape, for all other inputs the dimension must match exactly.
Construct new array
NPY_NO_EXPORT PyObject* PyArray_SearchSorted ( PyArrayObject op1,
PyObject *  op2,
NPY_SEARCHSIDE  side,
PyObject *  perm 
)
Search the sorted array op1 for the location of the items in op2. The

result is an array of indexes, one for each element in op2, such that if the item were to be inserted in op1 just before that index the array would still be in sorted order.

System Message: SEVERE/4 (<string>, line 7)
Unexpected section title.

Parameters
----------
op1 : PyArrayObject *
Array to be searched, must be 1-D.
op2 : PyObject *
Array of items whose insertion indexes in op1 are wanted
side : {NPY_SEARCHLEFT, NPY_SEARCHRIGHT}
If NPY_SEARCHLEFT, return first valid insertion indexes If NPY_SEARCHRIGHT, return last valid insertion indexes
perm : PyObject *
Permutation array that sorts op1 (optional)
System Message: SEVERE/4 (<string>, line 19)
Unexpected section title.

Returns
-------
ret : PyObject *
New reference to npy_intp array containing indexes where items in op2 could be validly inserted into op1. NULL on error.
System Message: SEVERE/4 (<string>, line 25)
Unexpected section title.

Notes
-----

Binary search is used to find the indexes.

Find common type
refs to dtype we own = 1
Look for binary search function
refs to dtype we own = 1
refs to dtype we own = 0
need ap2 as contiguous array and of right type
refs to dtype we own = 1
refs to dtype we own = 2
refs to dtype we own = 1, array creation steals one even on failure
refs to dtype we own = 0
If the needle (ap2) is larger than the haystack (op1) we copy the haystack to a contiguous array for improved cache utilization.
refs to dtype we own = 0, array creation steals one even on failure
need ap3 as a 1D aligned, not swapped, array of right type
convert to known integer size
ret is a contiguous array of intp type to hold returned indexes
do regular binsearch
do binsearch with a sorter array
NPY_NO_EXPORT int PyArray_Sort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
)
Sort an array in-place

References DEPRECATE.

NPY_NO_EXPORT PyObject* PyArray_TakeFrom ( PyArrayObject self0,
PyObject *  indices0,
int  axis,
PyArrayObject out,
NPY_CLIPMODE  clipmode 
)