8000 Initial sort() by support and complex sort() change by vrakesh · Pull Request #16700 · numpy/numpy · GitHub
[go: up one dir, main page]
Skip to content

Initial sort() by support and complex sort() change #16700

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 6 commits into from
Closed

Initial sort() by support and complex sort() change #16700

Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
fd0dc75
WIP: Initial keys() support and complex sort() change
vrakesh Jun 26, 2020
4d1ede2
Make a long axis, implementation in C
vrakesh Jul 10, 2020
94417b2
By as parameter
vrakesh Jul 12, 2020
347bf6d
keysort() C function to sort 1D slice at a time
vrakesh Jul 15, 2020
0abf3a8
Iterate on Keysort() copy mechanism, simplify
vrakesh Jul 22, 2020
ab2214b
CodeReview suggestions
vrakesh Sep 5, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Make a long axis, implementation in C
  • Loading branch information
@vrakesh
vrakesh committed Sep 4, 2020
commit 4d1ede21188d9592bc26fd71ad37eccea66ab881
150 changes: 129 additions & 21 deletions numpy/core/src/multiarray/methods.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -28,7 +28,7 @@

#include "methods.h"
#include "alloc.h"

#include "mapping.h"
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
#include "mapping.h"


/* NpyArg_ParseKeywords
*
Expand Down Expand Up @@ -1224,6 +1224,121 @@ array_choose(PyArrayObject *self, PyObject *args, PyObject *kwds)
}
}

static PyObject*
_make_along_axis_idx(npy_intp *arr_shape, int arr_size, PyObject* indices, int axis) {

PyObject *dest_dims = NULL;
PyObject *fancy_index = NULL;
int smaller = 0;
int indices_ndim = PyArray_NDIM((PyArrayObject*)indices);
if (!PyArray_ISINTEGER((PyArrayObject*)indices)) {
PyErr_SetString(PyExc_IndexError, "indices must be an integer array");
return NULL;
}

if (arr_size != indices_ndim) {
PyErr_SetString(PyExc_ValueError, "indices and array must have same number of dimensions");
return NULL;
}
dest_dims = PyList_New(0);
if (dest_dims == NULL) {
goto fail;
}
for (int i=0; i < axis; i++){
PyObject *tmp = Py_BuildValue("i", i);
if( PyList_Append(dest_dims, tmp) < -1) {
Py_DECREF(tmp);
goto fail;
}
Py_DECREF(tmp);
}

if (PyList_Append(dest_dims, Py_None) < 0) {
Py_DECREF(Py_None);
goto fail;
}
Py_DECREF(Py_None);
for (int i=axis+1; i < indices_ndim; i++){
PyObject *tmp = Py_BuildValue("i", i);
if( PyList_Append(dest_dims, tmp) < -1) {
Py_DECREF(tmp);
goto fail;
}
Py_DECREF(tmp);
}

fancy_index = PyList_New(0);
if (fancy_index == NULL) {
goto fail;
}
smaller = arr_size < PyList_Size(dest_dims) ? arr_size : PyList_Size(dest_dims);
for (int i=0; i < smaller; i++) {
PyObject *dim = PyList_GET_ITEM(dest_dims, i);
if (dim == Py_None) {
if (PyList_Append(fancy_index, indices) < -1) {
goto fail;
}

}
else {
// Define index shape of ones
PyObject *ind_shape = PyList_New(0);
if (ind_shape == NULL){
goto fail;
}
for (int j=0;j<PyLong_AsLong(dim); j++){
if (PyList_Append(ind_shape, Py_BuildValue("i", 1)) < -1) {
Py_DECREF(ind_shape);
goto fail;
}
}
if (PyList_Append(ind_shape, Py_BuildValue("i", -1)) < -1) {
Py_DECREF(ind_shape);
goto fail;
}
for (int j=PyLong_AsLong(dim)+1;j<indices_ndim; j++){
if (PyList_Append(ind_shape, Py_BuildValue("i", 1)) < -1) {
Py_DECREF(ind_shape);
goto fail;
}
}
PyObject *ind_shape_tuple = PyList_AsTuple(ind_shape);
Py_DECREF(ind_shape);
if (ind_shape_tuple == NULL) {
goto fail;
}
PyObject *range_arr = PyArray_Arange(0.0,(double)arr_shape[i],1.0, NPY_INT64);
range_arr = PyArray_Reshape((PyArrayObject*)range_arr, ind_shape_tuple);
if (range_arr == NULL) {
Py_DECREF(ind_shape_tuple);
Py_DECREF(dim);
goto fail;
}
if (PyList_Append(fancy_index, range_arr) < -1){
Py_DECREF(ind_shape_tuple);
Py_DECREF(range_arr);
Py_DECREF(dim);
goto fail;
}
Py_DECREF(ind_shape_tuple);
Py_DECREF(range_arr);
}
Py_DECREF(dim);
}
PyObject *fancy_tuple = PyList_AsTuple(fancy_index);
if (fancy_tuple == NULL) {
goto fail;
}
Py_DECREF(dest_dims);
Py_DECREF(fancy_index);
return fancy_tuple;

fail:
Py_XDECREF(dest_dims);
Py_XDECREF(fancy_index);
return NULL;
}

static PyObject *
array_sort(PyArrayObject *self, PyObject *args, PyObject *kwds)
{
Expand Down Expand Up @@ -1270,36 +1385,29 @@ array_sort(PyArrayObject *self, PyObject *args, PyObject *kwds)
*/
if (keys != Py_None && keys != NULL) {
PyObject *indices_obj = PyArray_LexSort(keys, axis);
Py_DECREF(keys);
PyArrayObject *sorted_out = NULL;
if (indices_obj == NULL) {
return NULL;
}
PyObject *_numpy_shape_base;
_numpy_shape_base = PyImport_ImportModule("numpy.lib.shape_base");
if(_numpy_shape_base == NULL) {
Py_DECREF(indices_obj);
if (axis == -1) {
axis = PyArray_NDIM(self)-1;
}
PyObject *fancy_tuple = _make_along_axis_idx(PyArray_SHAPE(self),
PyArray_NDIM(self), indices_obj, axis);
if (fancy_tuple == NULL) {
return NULL;
}
/* TODO:This parts needs to be replaced with equivalent C function
* Needs to be in-place
*/
PyArrayObject *key_sorted_obj = (PyArrayObject*)
PyObject_CallMethod(_numpy_shape_base, "take_along_axis",
"OOi", self, indices_obj, axis);

Py_DECREF(_numpy_shape_base);
sorted_out = (PyArrayObject *) array_subscript_asarray(self, fancy_tuple);
Py_DECREF(indices_obj);
//end TODO
if (key_sorted_obj == NULL) {
if (sorted_out == NULL) {
return NULL;
}
if (PyArray_CopyInto(self, key_sorted_obj) < 0) {
Py_DECREF(key_sorted_obj);
if (PyArray_CopyInto(self, sorted_out) < 0) {
Py_DECREF(sorted_out);
return NULL;
}
Py_DECREF(key_sorted_obj);
Py_RETURN_NONE;

Py_DECREF(sorted_out);
Py_RETURN_NONE;
}
if (order == Py_None) {
order = NULL;
Expand Down
0