Skip to content

np.unique(arr, axis) slow for axis=0 #15713

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.

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

Open
mganahl opened this issue Mar 5, 2020 · 8 comments
Open

np.unique(arr, axis) slow for axis=0 #15713

mganahl opened this issue Mar 5, 2020 · 8 comments
Labels
33 - Question Question about NumPy usage or development component: numpy.lib

Comments

@mganahl
Copy link

mganahl commented Mar 5, 2020

Numpy's unique function is about 10 times slower when acting on arrays with ndim=2 as
compared to ndim=1 arrays. This is even true if the 2d array is a trivial expansion of an original 1d array (see below).

Reproducing code example:

import numpy as np
import time
arr = np.random.randint(0,20,1000)
mat = np.expand_dims(arr,1)
t1 = time.time()
for _ in range(100):
    u = np.unique(arr)
print((time.time() - t1)/100)
t1 = time.time()
for _ in range(100):
    u2 = np.unique(mat, axis=0)
print((time.time() - t1)/100) #this is ~10 times slower
assert np.all(np.squeeze(u2)==u)

Numpy/Python version information:

1.18.1

@seberg
Copy link
Member

seberg commented Mar 5, 2020

This is probably expected, since the implementation has to first ensure that the "elements" being compared are contiguous in memory. In other words it makes "elements" out of the subarrays which are being compared.

This requires a copy of the array in one case but not in the others where the axis is the "slowest in memory". NumPy may not be as fast as it could be (in some cases a copy may not be necessary in general), but memory order matters for speed, and a certain slowdown has to be expected in either case. In most cases, doing the copy is likely the fastest approach we can do... (although the copy could be optimized possible, that would be a pretty large endevour).

That being said, I will not rule out that there is more to this, but it seems unlikely to me. Sorry, if this is a bit too technical. Memory order and speed are not trivial concepts.

@mganahl mganahl changed the title np.unique(arr, axis) slow for axis=1 np.unique(arr, axis) slow for axis=0 Mar 5, 2020
@seberg seberg added 33 - Question Question about NumPy usage or development component: numpy.lib labels Mar 5, 2020
@mganahl
Copy link
Author

mganahl commented Mar 5, 2020

thanks for the quick answer. In fact, I just noticed that the title of the issue was wrong, it should be axis=0. Not sure why one needs to copy memory in this case. It seems that at least the case ndim=2 with arr.shape[1]=1 should perform just as fast as the case where arr is a 1d array, since the order of the elements in memory is identical. This is also related to #11136

@seberg
Copy link
Member

seberg commented Mar 5, 2020

Ah sorry, yeah... I did not realize you were just creating a single element along the other axis. I am not sure whether this copies, but it mainly adds a large chunk of overhead due to using structured dtype defined comparison/sorting, which does not optimize for the trivial case you got here.

As to gh-11136 there is a reason we have been careful about doing such tricks. They seem nice, but are also dangerous in general.

@rossbar
Copy link
Contributor

rossbar commented Mar 10, 2020

Thanks for bringing this up @mganahl . I'm not sure there is anything actionable here - do you feel like your question has been sufficiently answered?

@mganahl
Copy link
Author

mganahl commented Mar 17, 2020

I'm wondering if it may be worth adding a unique_interger routine. If I understand correctly, the concerns in #11136 are related to using float dtype.

@seberg
Copy link
Member

seberg commented Mar 17, 2020

@mganahl as well as sorting being inconsistent depending on the byte-order.

@eric-wieser
Copy link
Member

There would be no reason to add a new routine.

The original optimization was removed in the lines here: https://github.com/numpy/numpy/pull/10588/files#diff-9e06c7b7bcc8e8153f5c2df57283b4cbL238.

We can almost certainly reintroduce the same optimization, but with a stricter whitelist of types than before.

@DominicAntonacci
Copy link

I had a similar use-case where I wanted to find unique 2D points in a list. I found it was much faster to manually sort the array and then find the transitions rather than call np.unique(arr, axis=0) and wrote the following function to speed it up. On my machine, it's faster for NxM arrays so long as M < 10.

def unique_axis0(arr):
    """
    Equivalent to np.unique(arr, axis=0). Based on numpy.lib.arraysetops._unique1d.
    """
    arr = np.asanyarray(arr)
    idxs = np.lexsort(arr.T)
    arr = arr[idxs]
    unique_idxs = np.empty(len(arr), dtype=np.bool_)
    unique_idxs[:1] = True
    unique_idxs[1:] = np.any(arr[:-1, :] != arr[1:, :], axis=-1)
    return arr[unique_idxs]

The function is asymptotically worse than np.unique so it's not a good candidate for a merge request. However, others may also find it a useful speedup in some situations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
33 - Question Question about NumPy usage or development component: numpy.lib
Projects
None yet
Development

No branches or pull requests

5 participants