8000 BUG: `numpy.array_api.argsort(stable=True, descending=True)` does not respect relative order · Issue #20778 · numpy/numpy · GitHub
[go: up one dir, main page]
Skip to content

BUG: numpy.array_api.argsort(stable=True, descending=True) does not respect relative order #20778

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

Jump to bottom
Closed
honno opened this issue Jan 10, 2022 · 0 comments · Fixed by #20788
Closed

BUG: numpy.array_api.argsort(stable=True, descending=True) does not respect relative order #20778

honno opened this issue Jan 10, 2022 · 0 comments · Fixed by #20788
Labels
00 - Bug

Comments

@honno
Copy link
Contributor
honno commented Jan 10, 2022 •
edited
Loading

The implementations of xp.sort() and xp.argsort() in numpy.array_api currently flip the resulting array when descending=True.

For stable=True scenarios, this leads to incorrect behaviour as a stable sort should be respecting an equivalent element's relative order of whatever comparison is being used (i.e. < and > operators). To be fair, the concept of respecting relative order of a descending sort is nonsensical for NumPy as there's no actual descending sort to use, but this is an area of non-compliance and might trip array consuming libraries.

This only really affects xp.argsort() as there's no way to distinguish relative order of equivalent elements in xp.sort().

cc @asmeurer @pmeier @lezcano

An example of NumPy acting erroneously:

>>> from numpy import array_api as xp
>>> x = xp.asarray([0, 1, 0])
>>> xp.argsort(x, stable=True)
Array([0, 2, 1], dtype=int64)  # correct
>>> xp.argsort(x, stable=True, descending=True)
Array([1, 2, 0], dtype=int64)  # should be [1, 0, 2]

PyTorch's sort() and the Python sorted() builtin are examples of respecting relative order when descending:

>>> a = [0, 1, 0]
>>> sorted(range(len(a)), key=a.__getitem__)
[0, 2, 1]
>>> sorted(range(len(a)), key=a.__getitem__, reverse=True)
[1, 0, 2]
...
>>> import torch
>>> t = torch.as_tensor([0, 1, 0])
>>> torch.sort(t, stable=True).indices
tensor([0, 2, 1])
>>> torch.sort(t, stable=True, descending=True).indices
tensor([1, 0, 2])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
00 - Bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

BUG: array_api.argsort(descending=True) respects relative sort order honno/numpy
1 participant
@honno
0