numpy/numpy — pull request #5012 by jaimefrio (2014-08-28 06:29:14+00:00)
Title: ENH: Speed up `unique` with `return_inverse`

This replaces a sort with fancy indexing assignment in the calculation of the `return_inverse` indices.

If `n` is the number of unique elements and `N` the number of items in the array, function calls to `np.unique(arr, return_inverse=True)` on arrays generated as `arr = np.random.randint(n, size=N)`, yield speed-ups for all tested sizes of up to 2x:

```
before after
n: 1, N: 10, t: 2.0526e-05 t: 1.9295e-05
n: 1, N: 100, t: 2.1347e-05 t: 2.0116e-05
n: 1, N: 1000, t: 4.6389e-05 t: 3.6536e-05
n: 1, N: 10000, t: 4.7826e-04 t: 2.1922e-04
n: 1, N: 100000, t: 5.6726e-03 t: 2.6963e-03
n: 1, N: 1000000, t: 6.7456e-02 t: 3.3005e-02
n: 3, N: 10, t: 1.9295e-05 t: 1.8473e-05
n: 3, N: 100, t: 2.2989e-05 t: 1.9705e-05
n: 3, N: 1000, t: 6.5273e-05 t: 3.7357e-05
n: 3, N: 10000, t: 7.6439e-04 t: 2.9516e-04
n: 3, N: 100000, t: 9.1004e-03 t: 3.5699e-03
n: 3, N: 1000000, t: 1.1095e-01 t: 4.4587e-02
n: 10, N: 10, t: 1.9705e-05 t: 1.9705e-05
n: 10, N: 100, t: 2.1758e-05 t: 2.0116e-05
n: 10, N: 1000, t: 7.5125e-05 t: 3.8178e-05
n: 10, N: 10000, t: 9.1464e-04 t: 3.8384e-04
n: 10, N: 100000, t: 1.1146e-02 t: 4.4915e-03
n: 10, N: 1000000, t: 1.4205e-01 t: 6.1260e-02
n: 30, N: 100, t: 2.2168e-05 t: 2.0526e-05
n: 30, N: 1000, t: 8.5388e-05 t: 4.1052e-05
n: 30, N: 10000, t: 9.8402e-04 t: 4.3803e-04
n: 30, N: 100000, t: 1.2810e-02 t: 5.2128e-03
n: 30, N: 1000000, t: 1.7536e-01 t: 7.8217e-02
n: 100, N: 100, t: 2.2168e-05 t: 2.0526e-05
n: 100, N: 1000, t: 9.4009e-05 t: 4.8442e-05
n: 100, N: 10000, t: 1.0813e-03 t: 5.1767e-04
n: 100, N: 100000, t: 1.3261e-02 t: 5.9316e-03
n: 100, N: 1000000, t: 1.9072e-01 t: 8.7818e-02
n: 300, N: 1000, t: 1.0468e-04 t: 6.0757e-05
n: 300, N: 10000, t: 1.1503e-03 t: 5.8705e-04
n: 300, N: 100000, t: 1.4205e-02 t: 6.6188e-03
n: 300, N: 1000000, t: 2.0918e-01 t: 9.8711e-02
n: 1000, N: 1000, t: 1.0838e-04 t: 6.3631e-05
n: 1000, N: 10000, t: 1.2344e-03 t: 6.7120e-04
n: 1000, N: 100000, t: 1.4969e-02 t: 7.4403e-03
n: 1000, N: 1000000, t: 2.2965e-01 t: 1.1241e-01
n: 3000, N: 10000, t: 1.3178e-03 t: 7.3648e-04
n: 3000, N: 100000, t: 1.5677e-02 t: 8.0906e-03
n: 3000, N: 1000000, t: 2.3833e-01 t: 1.1867e-01
n: 10000, N: 10000, t: 1.3436e-03 t: 7.7547e-04
n: 10000, N: 100000, t: 1.6471e-02 t: 9.0643e-03
n: 10000, N: 1000000, t: 2.4718e-01 t: 1.2636e-01
```