Repository: numba/numba
Pull request: Support for np.unique
closes #2884 

Fairly minimal, just the single array argument is supported,, not any of the return options or the axis argument.

Problem statement:
Feature request `numpy.unique`
Platform: Ubuntu 16.04
Python version: 3.6
Numba version: 0.37.0



I was trying to get a speedup in my code where I use `numpy.unique()` to find unique elements in an n-dimensional array. If I use this:

`x = np.unique(arr)`

this works fine and returns the expected results. But if I do this:

```
@jit(nogil=True, nopython=True)
def find_unique(arr):
    return np.unique(arr)

x = find_unique(arr)
```
This throws an error with the following message:

```
UntypedAttributeError: Failed at nopython (nopython frontend)
Unknown attribute 'unique' of type Module(<module 'numpy' from '/opt/conda/lib/python3.6/site-packages/numpy/__init__.py'>)
File "<ipython-input-15-bd84a508a624>", line 5
[1] During: typing of get attribute at <ipython-input-15-bd84a508a624> (5)

```

Hints from issue discussion:
Thanks for the report. You are seeing that message because Numba does not yet support `numpy.unique`. Functions that are supported are listed [here](http://numba.pydata.org/numba-doc/latest/reference/numpysupported.html). I'm editing the title and making this a feature request. Thanks.
Thanks for the response. Is there any particular timeline for that? The current numpy version takes too long to compute things and if it's in a loop, you can assign hours for the completion of the loop over thousands of n-dimensional arrays.
No problem. I don't have a time line for implementation I'm afraid. The fastest way to get support is to contribute a patch/implementation, the high level extending API `@overload` decorator is probably the place to start (http://numba.pydata.org/numba-doc/latest/extending/high-level.html#implementing-functions). I think it'd just be a memory flatten, sort and then loop to extract unique elements, I'd expect the sort to dominate so you may not get much of a speed up over NumPy.

```python
In [1]: import numpy as np

In [2]: x=np.random.rand(10000000)

In [3]: %timeit np.sort(x)
1.09 s ± 11.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [4]: %timeit np.unique(x)
1.17 s ± 4.11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```
Okay. I will look into it. Thanks
FYI (not sure if you get a notification on mentions), there's a fix in #2902. You can just copy the function decorated with `@overload` into your program (look for it in the diff) and it'll work.

Commit message: support and test for empty array

Patch to review:
diff --git a/docs/source/reference/numpysupported.rst b/docs/source/reference/numpysupported.rst
index 9295fe3ff15..67a039379d1 100644
--- a/docs/source/reference/numpysupported.rst
+++ b/docs/source/reference/numpysupported.rst
@@ -286,6 +286,7 @@ The following top-level functions are supported:
 * :func:`numpy.stack`
 * :func:`numpy.take` (only the 2 first arguments)
 * :func:`numpy.transpose`
+* :func:`numpy.unique` (only the first argument)
 * :func:`numpy.vstack`
 * :func:`numpy.where`
 * :func:`numpy.zeros` (only the 2 first arguments)
diff --git a/numba/targets/arrayobj.py b/numba/targets/arrayobj.py
index bf2ef9178ca..9da40afb13b 100644
--- a/numba/targets/arrayobj.py
+++ b/numba/targets/arrayobj.py
@@ -1825,6 +1825,14 @@ def imp(nd, dims, strides, old_itemsize, new_itemsize, layout):
     return res
 
 
+@overload(np.unique)
+def np_unique(a):
+    def np_unique_impl(a):
+        b = np.sort(a.flatten())
+        return np.array([x for x in b[:1]] + [x for i, x in enumerate(b[1:]) if b[i] != x])
+    return np_unique_impl
+
+
 @lower_builtin('array.view', types.Array, types.DTypeSpec)
 def array_view(context, builder, sig, args):
     aryty = sig.args[0]
diff --git a/numba/tests/test_array_methods.py b/numba/tests/test_array_methods.py
index f0c51d7ad32..663b9b39c69 100755
--- a/numba/tests/test_array_methods.py
+++ b/numba/tests/test_array_methods.py
@@ -177,6 +177,9 @@ def array_real(a):
 def array_imag(a):
     return np.imag(a)
 
+def np_unique(a):
+    return np.unique(a)
+
 
 class TestArrayMethods(MemoryLeakMixin, TestCase):
     """
@@ -857,6 +860,18 @@ def test_imag(self):
         z = x + 1j*y
         np.testing.assert_equal(pyfunc(z), cfunc(z))
 
+    def test_unique(self):
+        pyfunc = np_unique
+        cfunc = jit(nopython=True)(pyfunc)
+
+        def check(a):
+            np.testing.assert_equal(pyfunc(a), cfunc(a))
+
+        check(np.array([[1, 1, 3], [3, 4, 5]]))
+        check(np.array(np.zeros(5)))
+        check(np.array([[3.1, 3.1], [1.7, 2.29], [3.3, 1.7]]))
+        check(np.array([]))
+
 
 class TestArrayComparisons(TestCase):
 


Code review comments:
diff_hunk: @@ -1825,6 +1825,14 @@ def imp(nd, dims, strides, old_itemsize, new_itemsize, layout):
     return res
 
 
+@overload(np.unique)
+def np_unique(a):
+    def np_unique_impl(a):
+        b = np.sort(a.flatten())
path: numba/targets/arrayobj.py
text: @user1:
Performance nitpick: use `.ravel()` instead of `.flatten()` so you can save one copying.