Specifying a sort order when returning unique values

[kgryte]

As discussed #25 (comment), we need to resolve if, and how, we should specify a sort order when returning unique values.

A corollary issue is, if we support an optional keyword to return sorted unique values, whether we should also support specifying the sort direction (ascending vs descending).

We could limit sorting to ascending order, but that this may be considered an arbitrary restriction may lend support for the argument of not returning ascending/descending sorted output at all. Instead, punting sorting to userland, where sort order can be specified via sort(). However, as discussed in the OP, combining unique/sort may allow implementation perf optimizations which cannot be replicated when performed as two separate steps.

[rgommers]

Most relevant comment from gh-25:
Regarding sorting, that's an annoying one. Even if TensorFlow would add a sorting option, it probably couldn't easily default to sorted=True. The tf.experimental.numpy namespace doesn't have unique yet, maybe that would have sorted return values for compatibility?

@agarwal-ashish or @edloper do you have an opinion on this one?

[agarwal-ashish]

Unless we believe sorted order is almost always desired, it will be better to not enforce sorting and leave the API simpler. We could expect frameworks to perform operator fusion if this becomes a common performance bottleneck.

[rgommers]

Unless we believe sorted order is almost always desired

I don't think it is. Just wanting to know the number of unique values for example is common enough that pandas offers a separate nunique method. And I've heard requests for an unsorted (and hence faster) version in NumPy before.

So then to write portable code, users should explicitly write sort(unique(x)). Which if unique already sorts is cheap, so it shouldn't matter much performance-wise.

So the right resolution then is probably:

• Document that element order in output array is unspecified.
• Remove the sorted keyword from https://data-apis.github.io/array-api/latest/API_specification/set_functions.html

However, as discussed in the OP, combining unique/sort may allow implementation perf optimizations which cannot be replicated when performed as two separate steps.

In practice this is probably not so relevant. NumPy sorts anyway, and most other libraries have the ability (at least in principle) to do operator fusion.

[asmeurer]

Sorting is also not well defined for complex dtypes (potentially for other advanced dtypes as well if those were ever added). See #102 (comment). I'm not clear what the final resolution of that is, but it sounds like the sort function and friends require additional complexity to properly handle complex numbers (e.g., a key parameter). So it would probably be a good idea to omit sorted from any non-sorting API functions, as they would also have to support those additional parameters to be usable with complex dtypes.

[rgommers]

Makes sense, thanks @asmeurer. There are no other sorted keywords at the moment other than in unique (which gh-104 removes).